The analysis of existing methods of construction of prime numbers is carried out in the presented paper. New concepts related to pseudoprime numbers are introduced. Theorems are formulated and proved on the basis of which such numbers are constructed. Using pseudoprime numbers can significantly reduce the number of candidates viewed as primes. The proposed corollaries of the theorems allow to significantly increase the ranges of unambiguous determination of such candidates. The results of the conducted experiments are presented, their analysis is carried out. The most important result of applying pseudoprime numbers is the estimation of the number of numbers to be checked. For large numbers with a size of more than 200 decimal signs, they make up less than 8 percent of the numbers on a given interval, and as the size of the numbers increases, this percentage decreases. Based on experimental data, basic properties of pseudoprime numbers are formulated.
The development of infocommunication technologies has led to a decrease in the
protection of all high-tech systems. Particularly acute is the issue of ensuring
functional safety in such systems as the Internet of Things, Cloud storages, big data.
Any computer that performs the functions of managing, processing or storing data,
becomes available from anywhere in the world. Ensuring information security, as an
integral part of the functional safety, is extremely reluctant, because it costs a lot of
money, but there is no profit. Numerous materials in the press confirm the necessity
of such works, the most famous became an example of the virus Stuxnet, which
paralyzed the Iranian nuclear program [
One of the areas of information security is ensuring the confidentiality of
information circulating in the system. As the most general way to solve this problem
is cryptographic protection. As is a well-known resistance of cryptosystems is
determined by the secrecy of the key. In asymmetric encryption systems, this secrecy
depends on the size of the key. One of the most general public key systems is the
RSA system, which is based on the factorization problem, which belongs to the class
of NP-complete tasks [
In number theory, the problem of finding and proving the primality of a number is one of the main. The complexity of finding prime numbers is due to the fact that there is no function of their distribution on the number axis.
To build large prime numbers the following method is used in many sources [
Another group of methods [
In papers [
The next step in the search for a prime number is the definition of the primality of
the number being checked. As mentioned above, none of the existing exact algorithms
can solve this problem within an acceptable time. It should be noted that in [
Let us consider the concept of a pseudoprime number. This concept was introduced for numbers successfully passing the Fermat test. Depending on the primality tests that check numbers for primality, there are different types of pseudo-prime numbers. These types include pseudoprime numbers of Fermat, Fibonacci, Lucas, Euler-Jacobi. What is common to all these numbers? All these numbers, being composite, successfully pass the corresponding tests for primality.
Definition of the pseudoprime number. The pseudoprime is a number N whose primality is not proved.
Definition of a cardinality of the pseudoprime number. Let us introduce the concept of the cardinality of the pseudoprime number. The cardinality P of a pseudoprime number N is the guaranteed number of prime numbers that is not divisible by a given number. Obviously, the greater cardinality of such number, the greater the probability that this number will be prime.
Definition of a prime number. Based on the cardinality of the pseudoprime number, we can formulate the concept of the prime number. The pseudoprime number N will be proved as prime if and only if its cardinality is equal to P = (N1/2) on the interval of natural numbers from 1 to N1/2. In this definition, a (N) refers, as in the theory of numbers, the number of primes on the interval of natural numbers from 1 to N.
Definition of a factorial of the prime number. Let us introduce the concept of the
«factorial of the prime numbers» and denote it as follows π(n)!. This entry denotes the
product of all primes not greater than n. For example, π(7)!= π(8)!= π(9)!=
π(10)!=2*3*5*7=210. In fact, the π(n)! means the number of prime numbers in the
product. This term in its meaning coincides with a term primorial, introduced by H
Harvey Dubner in 1987 and received pn# designation [
Theorem 1. The sum (difference) of products of two disjoint sets of prime numbers is a prime number with each of the elements of these sets.
k l gcd ai b j , x X A B 1,
i 1 j1 where a A; A k; b B; B l; A P; B P; A B 0;
P – a set of prime numbers.
Proof of the theorem 1.
Consider any element а belonging to the set А (а А). It is obvious that for any a, the following expressions are true:
k gcd ai , a A a,
i 1 l gcd b j , a A 1.
j 1 Therefore, based on the above arguments,
k l gcd ai b j , a A 1 .
i 1 j1 k l gcd ai b j , b B 1 .
i 1 j1
A similar proof can be given for any element b belonging to the set В (b В) and, as a result, we get that
Since the element х belongs to the union of two disjoint sets of primes A and B, then it can be stated that
k l gcd ai b j , x X A B 1.
i 1 j1
A corollary of Theorem 1. If we take π(n)! and add 1 to it, the resulting number will be relatively prime with all prime numbers not greater than n. As a matter of fact, this formulation almost completely repeats Euclid's theorem on the infinity of primes. On the basis of the Theorem 1, the next relatively prime is the number obtained as the sum of π(n)! and the first prime number that is greater n. If to π(n)! Add the next prime number, and then we get a number that is relatively prime to numbers, taking part in this action.
Repeating this procedure, we can get a set of relatively prime numbers. Given that the obtained numbers are not guaranteed to be divisible by the first π(n) prime numbers, it can be argued that these numbers are pseudoprime with the cardinality π(n) +1.
Theorem 2. On the interval between π(n)! +1 and added to π(n)! prime numbers All numbers will be composite, except for those that have turned out as a result of addition, And the maximum added prime number must be less than the square of the first prime number to be added.
Proof of the theorem 2.
We begin the proof by considering the restrictive part of the theorem. Let us consider a prime number аi, that belongs to the set of primes А.
ai A;
A B; B (n), where В – the cardinality of the set А.
If we consider a number equal to the sum of π(n)! and the product of two primes greater than n, then, according to Theorem 1, it will be a pseudoprime number. The resulting number can be a prime number. Suppose that the minimal prime number, greater than n, is equal to a. Then the minimum product of two prime numbers, greater than the n, the number will be greater а2. Thus, the maximum prime number that can be used to uniquely define a pseudo-prime number must be less than а2. The restrictive part of the theorem is proved.
Consider the interval between numbers π(n)!+1 and π(n)!+а, where а is the nearest to n prime number. The smallest number on this interval is π(n)!+2. It is quite obvious that this number is divided by 2. Similarly with the following number π(n)!+3 that is divided by 3. In the general case, all numbers that are not greater than π(n)!+ n have at least one common divisor with π(n)!. If we consider the following number π(n)!+n+1, then it will always be even, like all the others, which result from the addition of two odd numbers n and k. If we consider numbers of the form π(n)!+n+2k, then they can be either prime or composite.
If the number is composite, then it can be represented, in accordance with the main theorem of arithmetic, in the form of a product of primes, and at least one of the factors is not greater than the number n. If the number π(n)!+n+2k is prime, then it will correspond to the number а. This means that on the interval between the numbers π(n)!+1 are π(n)!+а all numbers are composite.
Let us consider the whole interval indicated in the Theorem 2. Since we consider we consider numbers less than а2, then similar arguments can be applied to all the numbers of the interval under consideration. Thus we can conclude That on the interval between the numbers π(n)!+1 and π(n)!+а2 All numbers will be guaranteed composite, except for those obtained as the sum between π(n)! and prime numbers in the interval from а to а2.
The theorem is proved.
It should be noted that the Theorem 2 can be formulated as follows: «On the interval between π(n)!-1 and subtracted from π(n)! prime numbers, all numbers will be composite except those obtained as a result of subtraction, and the maximum deductible prime number must be less than the square of the first subtrahend prime number». The proof is similar to the above.
A corollary of Theorem 2. The above range concerns the unique definition of pseudoprime numbers. If the added prime number аj is greater than а2, part of numbers which will be within the range between π(n)! + аj and π(n)! + аj+1 can be prime numbers. In order not to miss such locations of prime numbers, It is necessary to construct all possible combinations of primes greater than n, including the value of their degrees. At the same time, these combinations should not be included among which are the factors of π(n)!.
As it is proved in the Theorem 2, to uniquely define a pseudoprime number, the value of the prime number to be added must not exceed the square of the first prime number greater than n. Is this large or small? When considering large numbers n > 200 D this will be a relatively small number. For example, π(1000)! will correspond to the number 416 D. The interval of numbers on which it will be necessary to search for a prime number will be 1018081. There are 79682 pseudoprime numbers on it, which is less than 8 percent of all numbers in this interval. It should be noted the possibility of increasing the checked interval. According to the Theorem 1, by subtracting a prime number from π(n)! it is possible to increase its size to 2036162, and the number of checked numbers to 159364. It is obvious that with the increase of n, the interval will increase rapidly.
Any number can be represented as a sum of two numbers. Proceeding from the fact that all pseudoprime numbers are odd, any of them can be represented as a sum of even and odd numbers. Obviously, there are a lot of variants of representation and the larger the number are, the more such options are.
Each of the terms, according to the main theorem of arithmetic, can be represented as the product of primes.
Theorem 3. If at least in one of the variants of representing a pseudoprime number in the form of two terms, these terms turn out to be not mutually prime numbers, then the considered number is a composite.
Proof of the theorem 2. Let us take two disjoint sets of prime numbers A and B. А ={ai}, B = {bj}.
ai, bj ϵ N.
A∩B = Ø.
gcd (∏ai, ∏ bj) = 1.
Let us consider the products of the set A and B. Obviously, these are two relatively prime numbers.
To ensure that the numbers are not relatively prime, they must have a common divisor. Введем в каждое из произведений по множителю С. In this case gcd (С*∏ai, С*∏ bj) = С.
С*∏ai + С*∏ bj = С (∏ai + ∏ bj).
In this case, the number under investigation will be the composite. As it should be proved. 4
When using primes, two problems usually occur: finding a prime number and
checking the selected number for primality. The main disadvantage of the known
algorithms for finding prime numbers is a simple search of candidates. In the best
case, the numbers multiples of two are discarded. Using pseudoprime numbers, only
the numbers that are obtained as a result of applying theorems 1 and 2 are checked.
Organizing the checking of a number for primality, both deterministic and
probabilistic methods are used. Both groups are well known and described in many
sources [
The range of single-valued definition of pseudo-simple numbers will be denoted as the step of the definition (SD). An SD size can be easily calculated using the theorem 2. Table 1 presents a data that allows evaluating the performance of the proposed method for finding pseudoprime numbers. The table contains the following data: the π(n)! size – Number of decimals in the product; the highest factor (HF) – the greatest prime number in π(n)!; the number of primes (NP) – number of primes on SD; the percentage of the checked numbers (% checked) – ratio of the number of prime numbers in SD to the total number of numbers on the SD.
As can be seen from Table 1, the growth rate of a quantity of the size π(n)! Exceeds the growth rate of the factorial dependence that once again emphasizes the complexity of the problem of finding prime numbers of large dimensions. The most interesting data, which are given in the table, in the opinion of the author, is the percentage of the numbers being checked. For large numbers (D> 200), this index is less than 9% of the total number of numbers on the interval being checked. If you take any algorithm that will only check for numbers ending in 1,3,7,9, then the percentage of the checked numbers will be 40. When the cardinality of a pseudoprime number increases, the percentage of the numbers being checked decreases.
To increase the SD size, it is necessary to multiply the obtained product of prime numbers before their summation with the corresponding prime numbers by all the numbers less than the next prime number for π(n). The obtained results for π(11) are presented in Table 2. Based on the theorem 3, a method of checking numbers for simplicity is proposed. 1. From the given number, the square root is calculated and the result is rounded down.
2. Calculates the difference between the target number and the number obtained. 3. These numbers are decomposed into factors. 4. If the factors have at least one the same number, then go to step 8. 5. From a smaller number, one is subtracted. 6. If the result is bigger than 1, then go to step 2. 7. The number is prime. 8. The number is composite.
By its idea, the presented method is similar to a quadratic sieve. The difference is that the number obtained as a result of the extraction of the square root in the proposed method decreases. This is due to the fact that more than one square root can have a maximum of one efficient, while the remaining ones will be less than the resulting root.
As an example, consider the number 996533. The square root of this number rounded down will be equal to 998. In Table 3t there are numbers equal and less than 998 and their decomposition, according to the main theorem of arithmetic, in columns one and two are. There are the numbers obtained as the difference between the checked number for primality and the numbers in the first column, in the third column. There is the decomposition of numbers from the third column in the fourth column. There is the greatest common divisor in the fifth column.
How effective is this way of confirming the number primality? Obviously, a sufficiently long time will be spent on decomposing a large number into multipliers. Proceeding from the stated problem of finding a common factor, it makes sense to use the well-known Euclidean algorithm for finding the greatest common divisor.
Before proceeding to the use of the Euclidean algorithm, it is necessary to note one more regularity. Most of the pairs under consideration have in their composition the first ten primes from 2 to 29. If we multiply these numbers, the result is 6469693230.
Define gcd of numbers 6469693230 and 996533. gcd (6469693230, 996533) is 1. This means that our investigated number is not divisible without a remainder by any prime number less than or equal to 29, that cardinality of a number 996533 is proved (Р= 10). This means that as soon as the remainder of the division in any iteration becomes equal to or less than the number 29, it is possible to assert unequivocally, that gcd of this numbers will be equal 1. Using the product of the following 10 prime numbers from 31 to 71, it is possible to calculate the gcd of this pair of numbers.
If we consider table 3, then gcd should be searched between the I and II numbers represented in the first and third columns respectively. The result is presented in the fifth column.
The possibility of applying gcd detection methods is quite productive. Although
this is nothing more than a method of trial division, but the speed of the proposed
method is much higher. This can be achieved by first calculating the products of
prime numbers, and their number in the product can be quite large. For example, if we
multiply all the prime numbers that are less than 1000, and there are 169 such
numbers, and gcd = 1, then the probability that the test number is composite, will be
equal 2-169[
Quite interesting results, from the point of view of parallelization of the calculation process, is presented in Table 4. If you take the same number 996533 and repeat the process, the results of which are presented in Table 3, having previously increased the number several times. Table. 4 shows the number steps NS on which the desired result is obtained, depending on the multiplication factor MF.
Obviously, the obtained result will depend on the ratio of the two terms and the greatest common divisor. 5
At this moment, the complexity of constructing prime numbers is due to the absence of the distribution laws of this numbers. Unlike prime numbers for pseudoprime numbers, based on the considered examples, it is possible to reveal some regularities conditioned by the properties of these numbers and the method for their construction.
The first property is repeatability of pseudoprime numbers. This is because it is possible to reuse prime numbers in the product of prime numbers. The cardinality of the pseudoprime number remains unchanged, and its size increases. This property is clearly seen from Table. 2.
The second property is specularity or symmetry. This property follows from the theorem 1. Pseudoprime numbers are symmetric with respect to kπ(n)!. 6
The presented paper is the result of three years works on creating the theory of pseudoprime numbers. In this paper for the first time a definition of some terms is given, some theorems on pseudoprime numbers are formulated or slightly modified, a correct proof is given. All the above theoretical calculations are confirmed by the carried out experiments, which confirm their correctness.
The use of pseudoprime numbers significantly reduces labor costs searching for prime numbers by specifying a location on the numeric axis where they can be located. As the size of the generated number increases, the relative number of the considered options decreases.
Based on the above theorems, it is possible to state quite reliably the possible numbers of twins, although this requires additional studies.
The use of a variety of combinatorial methods for the use of pseudoprime numbers makes it possible to assert a high potential for their use in finding prime numbers.