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

, which by using square root,

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

, that is examined, the square root is computed as follows, where

is the value of the least positive remainder of

.

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

How is the initial estimate

being computed so from

? Thus, please explain clearly.