mersenneforum.org - View Single Post

Raman · 2009-02-27, 16:42

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.

2009-02-27, 16:42	#5
Raman Noodles "Mr. Tuch" Dec 2007 Chennai, India 4E9₁₆ 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