mersenneforum.org - View Single Post

Raman · 2009-02-27, 17:48

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

Quote:

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.