mersenneforum.org - View Single Post

Raman · 2009-02-26, 14:11

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)$
$i=i+1$
$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

Quote:

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.