Thread: Continued Fraction Algorithm View Single Post
2009-02-26, 14:11   #3
Raman
Noodles

"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)$
$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.

Last fiddled with by Raman on 2009-02-26 at 14:17