2010/03/28 by Vibeke Libby, Libby, Vibeke
Computer Science · Mathematics · #11A07 #11D09 #11Y05 #B.2.4 #Cryptography and Residue Arithmetic #D.1.0 #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.1 #FOS: Computer and information sciences #FOS: Mathematics #G.2.0 #History and Theory of Mathematics #Number Theory (math.NT) #Numerical Methods and Algorithms
paper · pdf · doi:10.48550/arxiv.1003.5390
openalex publication_date 2010/03/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that all perfect odd integer squares not divisible by 3, can be usefully written as sqrt(N) = a + 18p, where the constant a is determined by the basic properties of N. The equation can be solved deterministically by an efficient four step algorithm that is solely based on integer arithmetic. There is no required multiplication or division by multiple digit integers, nor does the algorithm need a seed value. It finds the integer p when N is a perfect square, and certifies N as a non-square when the algorithm terminates without a solution. The number of iterations scales approximately as log(sqrt(N)/2) for square roots. The paper also outlines how one of the methods discussed for squares can be extended to finding an arbitrary root of N. Finally, we present a rule that distinguishes products of twin primes from squares.