2019/07/17 by Niels Christian Møller, Niels Möller, Möller, Niels
Computer Science · #11Y16 #Coding theory and cryptography #Cryptography and Residue Arithmetic #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #G.4 #Numerical Methods and Algorithms #acm:11Y16 #cs.DM #cs.DS #msc:11Y16
paper · pdf · doi:10.48550/arxiv.1907.07795
arxiv created 2019/07/17 · openalex publication_date 2019/07/17 · arxiv updated 2019/07/19 · openalex created_date 2019/07/23 · openalex updated_date 2026/07/28
The family of left-to-right GCD algorithms reduces input numbers by repeatedly subtracting the smaller number, or multiple of the smaller number, from the larger number. This paper describes how to extend any such algorithm to compute the Jacobi symbol, using a single table lookup per reduction. For both quadratic time GCD algorithms (Euclid, Lehmer) and subquadratic algorithms (Knuth, Schönhage, Möller), the additional cost is linear, roughly one table lookup per quotient in the quotient sequence. This method was used for the 2010 rewrite of the Jacobi symbol computation in GMP.