View Single Post
Old 2009-02-27, 17:48   #7
Raman's Avatar
"Mr. Tuch"
Dec 2007
Chennai, India

3·419 Posts

The question is how to recognize those primes that do not divide the value of Q_n for any value of n that is being given up.
Besides the fact that we can skip up those primes for which \left( \frac{kN}{p} \right) = -1

In the Quadratic Sieve factoring algorithm,
we need to test those values of x, for a prime p, that satisfies the congruence, for which
x \equiv \pm \sqrt{kN} \ (mod\ p).

It produces two arithmetic progressions, with a common difference of p, for each of the both sequences.

Like that, anything existing for the continued fraction factoring algorithm?
The values of A_{n-1} here,
are produced at random, from the continued fraction expansion of \sqrt{kN}, by using this method.

We have the fact that, this congruence is being satisfied up always
A_{n-1}^2 = (-1)^nQ_n\ (mod\ N)

90% of the time is being spent in 10% of the code. The program spends majority of its execution time within the loops. Likewise, for these class of the algorithms, the program spends the majority of the time for sieving and then factoring the values of the Q_n, of course, for ever.

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