Authors : Bulat G. Mubarakov, Andrey S. Mochalov and Ramilya G. Rubtsova
Abstract: Prime numbers play an important role in modern cryptography. The system of RSA is one of the most well-known cryptographic systems. It uses compound number as a key that is the product of two prime numbers of large dimension. To search for large prime numbers different algorithms of primality tests are used. Note that all existing algorithms of primality testing are divided into two large groups: deterministic and probabilistic tests. Deterministic simplicity tests can accurately say whether, the number is prime or composite. The algorithms of the second group are much faster than deterministic but operate with a certain probability of error. Among the tests of simplicity used in cryptography, the most popular is the probabilistic polynomial primality test of Miller-Rabin. The theoretical probability of an error of this test depends on the number of iterations wherein each iteration decreases the probability of error in 4 times. However, the actual number of errors made by this test is much less than the theoretical. For example, checking simplicity of all odd numbers less than one million with one iteration of Miller-Rabin test with the base of two gives 47 errors with total number of prime numbers of this range of about 78 thousand. We note that the test of Miller-Rabin makes mistakes of one type: it defines some composite numbers as simple. These numbers are called strictly pseudo prime according to the specified reason. The study of the distribution of strictly pseudo prime numbers for various reasons allows to accelerate execution of Miller-Rabin test. This study describes one way to improve the efficiency of the probabilistic Miller-Rabin test. The theoretical basis for this is to search and study the properties of the distribution of strictly pseudo prime numbers.
Bulat G. Mubarakov, Andrey S. Mochalov and Ramilya G. Rubtsova, 2015. Investigation of Distribution of Pseudosimple Numbers. Research Journal of Applied Sciences, 10: 358-364.