IJPAM: Volume 34, No. 1 (2007)

CONTINUED FRACTIONS AND PARALLEL SQUFOF

S. McMath$^1$, F. Crabbe$^2$, D. Joyner$^3$
$^{1,2}$Department of Computer Science
United States Naval Academy
Annapolis, MD 21402, USA
$^2$e-mail: crabbe@usna.edu
$^3$Department of the Navy
United States Naval Academy
121, Blake Road, Annapolis, MD 21402-5000, USA
e-mail: wdj@usna.edu


To the memory of Daniel Shanks (1917-1996)


Abstract.In this partly expository paper, we prove two results.

-- That the two-sided continued fraction of the normalized square root (an important part of the SQUFOF algorithm) has several very attractive properties - periodicity, a symmetry point corresponding to a factorization of $N$, and so on.

-- The infrastructure distance formula.

Finally, we describe a method for parallelization of SQUFOF that maintains its efficiency per procesor as the number of processors increases, and thus is predicted to be useful for very large numbers of processors.

Received: September 1, 2006

AMS Subject Classification: 11A55, 11J70, 30B70

Key Words and Phrases: continued fractions, infrastructure distance formula, parallelization of SQUFOF algorithm, large numbers of processors

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2007
Volume: 34
Issue: 1