2018/10/23 by Hyun Jong Kim, Kim, Hyun Jong
Computer Science · Mathematics · #11T99 (Secondary) #11Y11 (Primary) #11Y16 (Primary) #Coding theory and cryptography #Commutative Algebra and Its Applications #FOS: Mathematics #Number Theory (math.NT) #Polynomial and algebraic computation #math.NT #msc:11T99 #msc:11Y11 #msc:11Y16
paper · pdf · doi:10.48550/arxiv.1810.09651
arxiv created 2018/10/23 · openalex publication_date 2018/10/23 · arxiv updated 2018/10/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 xN + a are equivalent in a residue ring of ℤ/Nℤ[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.