Variations on a Miller-Rabin Theme Ehme, Jeffrey
PRIMUS : problems, resources, and issues in mathematics undergraduate studies,
01/02/2024, Letnik:
34, Številka:
1
Journal Article
Recenzirano
The Miller-Rabin test is a useful probabilistic method for finding large primes. In this paper, we explain the method in detail and give three variations on this test. These variations were ...originally developed as student projects to supplement a course in error correcting codes and cryptography.
In this paper, we investigate the popular Miller–Rabin primality test and study its effectiveness. The ability of the test to determine prime integers is based on the difference of the number of ...primality witnesses for composite and prime integers. Let W ( n ) denote the set of all primality witnesses for odd n. By Rabin’s theorem, if n is prime, then each positive integer a < n is a primality witness for n. For composite n, the power of W ( n ) is less than or equal to φ ( n ) / 4 where φ ( n ) is Euler’s Totient function. We derive new exact formulas for the power of W ( n ) depending on the number of factors of tested integers. In addition, we study the average probability of errors in the Miller–Rabin test and show that it decreases when the length of tested integers increases. This allows us to reduce estimations for the probability of the Miller–Rabin test errors and increase its efficiency.
We investigate the probability that a random odd composite number passes a random Fermat primality test, improving on earlier estimates in moderate ranges. For example, with random numbers to ...2^{200}, our results improve on prior estimates by close to 3 orders of magnitude.
Random prime numbers are an essential resource for many asymmetric cryptographic protocols. However, despite the emerging popularity of quantum random number generators (QRNGs) as sources of secure ...randomness, physical prime number generators have not yet been explored. In this work, we experimentally implement and characterize a vacuum-based probabilistic prime number generation scheme with an error probability of 3.5×10−15. By removing the quantum source (QS), an additional scheme based on electronic noise is derived, and a comparative analysis for increasing prime lengths is made. We observed that the QS significantly outperforms the classical scheme for small prime generation, where increases up to 585.0% in the diversity of unique primes obtained are seen. Moreover, we propose a length-agnostic statistical test for prime number sequences and apply it to the output of the uniformized randomness source, which was successful in revealing underlying biases in the output prime distributions. The resultant sequences were subsequently submitted to the NIST statistical test suite, where the quantum and classical sources passed, respectively, 86.96% and 45.34% of the total test set applied.
The Lucas primality test is a procedure that verifies an odd integer
for primality using the condition
, where
is the Fibonacci series,
is the Legendre symbol. In this paper, we study a modified ...Lucas test called the Lucas–Miller–Rabin primality test (briefly, LMR test) and demonstrate that the LMR test is much more efficient than the original Lucas test. We describe necessary and sufficient conditions for composite integers to pass the LMR test. Composite integers passing it are called LMR-pseudoprimes. We show that the existence of LMR-pseudoprimes divisible by squares depends on the validity of the Wall–Sun–Sun Hypothesis, one of the long-standing problems in the Number Theory.
The problem of testing natural numbers for primality is an important problem for the Theory of Numbers and Cryptography. The main instrument of Cryptography to determine, if a given odd integer is ...prime or composite, is the Miller–Rabin primality test. The latter is a probabilistic iterative algorithm consisting of rounds.At each round a special parameter
is chosen called the base of the round. The authors of Miller–Rabin algorithm do not give any guidance on the choice of
. We propose a heuristic algorithm based on the reinforcement learning approach for a special choice of bases. The proposed method significantly improves the base selection in the Miller–Rabin primality test: the comparison with the state-of-the-art selection strategies demonstrates that the selection procedure based on reinforcement learning is several times more efficient than the baseline strategies. An interesting feature of the algorithm is the ability to perform training on relatively small numbers bounded up to twenty-five bits. The training is performed under the efficient method of proximal policy optimization. Using the graphs of several loss-related metrics, such as entropy, value, and policy losses, we demonstrate that the agent successfully learns from the training data. We assess that the knowledge obtained during the training can be generalized to the larger numbers in the test sample, and the testing procedure demonstrates the high efficiency of the proposed approach. Not in the least turn, the article attempts to connect two areas of mathematical knowledge, namely, number theory and artificial intelligence, which researchers usually consider to stand very far from each other. Meanwhile, the use of reinforcement learning methods in solving problems of classical number theory seems very promising for us, and we hope to draw attention to this opportunity.
This article explores the asymptotic complexity of two problems related to the Miller-Rabin-Selfridge primality test. The first problem is to tabulate strong pseudoprimes to a single fixed base a . ...It is now proven that tabulating up to x requires O ( x ) arithmetic operations and O ( x log x ) bits of space. The second problem is to find all strong liars and witnesses, given a fixed odd composite n . This appears to be unstudied, and a randomized algorithm is presented that requires an expected O ((log n ) 2 + | S ( n )|) operations (here S ( n ) is the set of strong liars). Although interesting in their own right, a notable application is the search for sets of composites with no reliable witnesses.
Prime and Prejudice Albrecht, Martin R.; Massimo, Jake; Paterson, Kenneth G. ...
Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security,
10/2018
Conference Proceeding
This work provides a systematic analysis of primality testing under adversarial conditions, where the numbers being tested for primality are not generated randomly, but instead provided by a possibly ...malicious party. Such a situation can arise in secure messaging protocols where a server supplies Diffie-Hellman parameters to the peers, or in a secure communications protocol like TLS where a developer can insert such a number to be able to later passively spy on client-server data. We study a broad range of cryptographic libraries and assess their performance in this adversarial setting. As examples of our findings, we are able to construct 2048-bit composites that are declared prime with probability (1/16) by OpenSSL's primality testing in its default configuration; the advertised performance is (2-80). We can also construct 1024-bit composites that always pass the primality testing routine in GNU GMP when configured with the recommended minimum number of rounds. And, for a number of libraries (Cryptlib, LibTomCrypt, JavaScript Big Number, WolfSSL), we can construct composites that always pass the supplied primality tests. We explore the implications of these security failures in applications, focusing on the construction of malicious Diffie-Hellman parameters. We show that, unless careful primality testing is performed, an adversary can supply parameters (p,q,g) which on the surface look secure, but where the discrete logarithm problem in the subgroup of order q generated by g is easy. We close by making recommendations for users and developers. In particular, we promote the Baillie-PSW primality test which is both efficient and conjectured to be robust even in the adversarial setting for numbers up to a few thousand bits.
PDF
