On a Modification of the Agrawal-Biswas Primality Test

Hyun Jong KimarXiv 2018 · DOI · arXiv

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

Abstract

We present a variant of the Agrawal-Biswas algorithm, a Monte Carlo algorithm which tests the primality of an integer $N$ by checking whether or not $(x+a)^N$ and $x^N + a$ are equivalent in a residue ring of $\mathbb{Z}/N\mathbb{Z}[x]$. The variant that we present is also a randomization of Lenstra jr. and Pomerance's improvement to the Agrawal-Kayal-Saxena deterministic primality test. We show that our variant of the Agrawal-Biswas algorithm can be used with the Miller-Rabin primality test to yield an algorithm which is slower than the Miller-Rabin test but relatively more accurate.
BibTeX
@misc{kim2018modification,
  author = {Hyun Jong Kim},
  title = {{On a Modification of the Agrawal-Biswas Primality Test}},
  year = {2018},
  eprint = {1810.09651},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1810.09651},
}
Figure