View Single Post
Old 2009-02-27, 16:42   #5
Raman's Avatar
"Mr. Tuch"
Dec 2007
Chennai, India

4E916 Posts

Finally, is the factoring of the different Q_n values for the continued fraction algorithm only by trial division? Of course, we have that for a prime p to be a factor of Q_n, then p should satisfy the Legendre Symbol \left( \frac{kN}{p} \right) = 0 or 1.

Further, we have that properties of dividing by using brute force techniques only upto the Factor Base primes, and then discarding away those relations, whose cofactor is greater than the Upper Bound.

Do we have any other constraints or conditions for the factoring of the various Q_n values for this algorithm?

For the Quadratic Sieve algorithm, we have that if a prime p divides x^2-kN, then x^2=kN\ (mod\ p), hence we need to check for the prime factor p for only those values of x, that which are congruent to the value of
x \equiv \sqrt{kN}\ (mod\ p)

Anything else that is like that case for this continued fraction factoring algorithm? Of course, for the optimizations, for ever.

Last fiddled with by Raman on 2009-02-27 at 16:45
Raman is offline   Reply With Quote