View Single Post
Old 2009-02-26, 14:58   #4
(loop (#_fork))
fivemack's Avatar
Feb 2006
Cambridge, England

18EE16 Posts

The "leading point of kN" is referring to the first few digits of kN (IE, if you know kN is 88 digits long and begins 1.427, so is about 14.27*10^86, a starting estimate for sqrt(kN) would be sqrt(14.27) * 10^43 = 3.77*10^43).

The algorithm you're writing about never tells you to reduce R mod N; you just keep multiplying Qi (which are integers) together until you get an enormous integer, then just take the square root of that integer.

But this code was written to run on amazingly slow computers, and before the FFT-based multiply algorithms had reached the state they're in now, so at the time it was impractical to work with such large integers, and they had to invent a cleverer algorithm which is done in the next section of the paper.
fivemack is offline   Reply With Quote