TL;DR
This paper introduces a modified Agrawal-Biswas primality test that, when combined with the Miller-Rabin test, offers a more accurate primality testing algorithm. While slightly slower than Miller-Rabin alone, this new approach provides a stronger guarantee against falsely identifying composite numbers as prime, especially for larger inputs.
What Problem Does This Paper Address?
Determining whether a large number is prime is a fundamental problem in number theory and cryptography. While deterministic tests like AKS exist, they can be computationally expensive. Probabilistic tests like Miller-Rabin are much faster but have a small chance of error (falsely declaring a composite number as prime). The Agrawal-Biswas algorithm, a probabilistic variant of AKS, also faces similar trade-offs. This paper aims to improve the accuracy of probabilistic primality testing by modifying the Agrawal-Biswas algorithm and combining it with the Miller-Rabin test, seeking a better balance between speed and reliability.
Methods
The core of this work is a modification of the Agrawal-Biswas primality test. The original Agrawal-Biswas test relies on checking the polynomial identity $(x+a)^N \equiv x^N + a \pmod{N}$ in the ring $\mathbb{Z}/N\mathbb{Z}[x]$ modulo a randomly chosen polynomial $f(x)$. This paper's modification involves using a polynomial $f(x)$ that is irreducible modulo the prime factors of $N$ and is chosen with a sufficiently large degree. Instead of checking the identity with $a=1$, they check it with a randomly chosen polynomial $h(x)$ of degree less than $f(x)$.
To achieve stronger accuracy guarantees, the authors propose combining this modified Agrawal-Biswas test with the well-established Miller-Rabin primality test. The proposed algorithm runs the Miller-Rabin test multiple times and the modified Agrawal-Biswas test once. This combination leverages the strengths of both tests: Miller-Rabin is efficient and good at quickly identifying composites, while the modified Agrawal-Biswas test, with its carefully chosen polynomial, provides a more robust check against false positives. The paper also relies on sophisticated techniques from prior work ([8]) to deterministically construct a polynomial $f(x)$ that is irreducible modulo all prime factors of $N$.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Synergistic Combination: The paper demonstrates that combining a modified Agrawal-Biswas test with the Miller-Rabin test can yield an algorithm with superior accuracy guarantees compared to either test used in isolation.
- Irreducible Polynomials are Key: The accuracy of the modified Agrawal-Biswas test hinges on using a polynomial $f(x)$ that is irreducible modulo each prime factor of $N$. This property, derived from prior work, is crucial for the theoretical bounds.
- Trade-off Management: The authors explicitly address the speed-accuracy trade-off. While their combined algorithm is slower than Miller-Rabin alone, it offers a significantly reduced probability of error for composite numbers, making it more suitable when high confidence is paramount.
- Leveraging Advanced Number Theory: The construction of the required irreducible polynomial $f(x)$ relies on advanced concepts like pseudofields and Gaussian periods, highlighting the deep theoretical underpinnings of modern primality testing.
Key Results
The paper presents a Monte Carlo primality testing algorithm that:
- Correctly identifies prime numbers.
- For composite numbers, it falsely indicates primality with a probability of at most $\frac{1}{2^{(r-1) \deg f} N^{\deg f - r}}$, where $r$ is the number of distinct prime factors of $N$ and $\deg f$ is the degree of the constructed polynomial.
- The algorithm runs in $\tilde{O}(\log^{c+2} N)$ time, assuming a suitable choice of $\deg f = O(\log^c N)$.
- It requires $O(\log^{c+1} N)$ random bits.
This is a significant improvement in accuracy over the Miller-Rabin test alone, especially for numbers with many prime factors.
Limitations and Future Work
- Computational Cost: The primary limitation is that the combined algorithm is slower than the Miller-Rabin test alone. The runtime depends on the degree of the constructed polynomial $f(x)$, which needs to be sufficiently large for strong accuracy guarantees.
- Dependence on Prior Work: The construction of the irreducible polynomial $f(x)$ relies heavily on the deterministic algorithm developed by Lenstra Jr. and Pomerance ([8]), which itself has certain prerequisites (e.g., $N$ being sufficiently large).
- Future Work: The paper implicitly suggests that further research could focus on optimizing the construction of the irreducible polynomial or exploring other combinations of primality tests to achieve even better speed-accuracy trade-offs. The theoretical bounds on accuracy are also a key area for future investigation and potential refinement.
Summary updated