View Single Post
Old 2009-02-26, 14:11   #3
Raman's Avatar
"Mr. Tuch"
Dec 2007
Chennai, India

3·419 Posts

Once the matrix has been solved, the history matrix contains the rows which contribute to the dependency. The relations are multiplied to get the value of Q^2\ (mod\ N), which by using square root, Q is resolved.
This is the technique that is being mentioned so, in the paper of Morrison and Brillhart, rather than maintaining a count of each prime power, and then multiplying each prime by half the value of power.

For each relation Q_i, that is examined, the square root is computed as follows, where \overline{Q} is the value of the least positive remainder of Q\ (mod\ N).

i=2,\ \overline{Q}=1,\ R=Q_1
X=GCD(R,\ Q_i)
\overline{Q}=X\overline{Q}\ (mod\ N)
R=\left( \frac{R}{X} \right) \left( \frac{Q_i}{X} \right)
If\ i \le s\ Then\ Goto\ 2
X=\sqrt R
\overline{Q}=X\overline{Q}\ (mod\ N)

Consider the step 7 now. It is given that if R is sufficiently small, then X can be easily computed by taking its square root. I don't understand this fact. Can someone please explain clearly?

If R is greater than N, it will be reduced (mod N). How do we know (by using so the brute force techniques?) what multiple of N should be added up to R, so as to make it a perfect square?

It is somewhat pointed to remark 3.4
One method of calculating g is the following modification of the Newton Raphson recursion: When an initial estimate x_0 > \sqrt{kN} (which can be calculated by using the leading point of kN), successively compute x_{n+1} = \lfloor \frac{(x_n^2+kN)}{2x_n} \rfloor for n \ge 0, where the bracket denotes the greatest integer function. When x_{n+1} - x_n \ge 0, then g=x_{n+1}.
How is the initial estimate x_0 being computed so from \sqrt{kN}? Thus, please explain clearly.

Last fiddled with by Raman on 2009-02-26 at 14:17
Raman is offline   Reply With Quote