implementing the quadratic sieve

From: Marlene Stebbins (marlene_at_mail.com)
Date: 11/01/04 

Date: Mon, 01 Nov 2004 20:44:45 GMT

I am trying to write a toy implementation of the quadratic sieve.
The following has been gleaned from several sources. If any of you
are familiar with the quadratic sieve, I would appreciate you looking
this over and telling me if I've got it right. FYI, I am a 9th grader
with a very limited math background.

Quadratic Sieve factoring algorithm:

to factor n:

1. Select a set of prime numbers called the factor base.
    (Selecting the factor base requires further explanation.)

2. For each integer f close to the square root of n,
    try to factor (f^2)-n(mod n) with the primes in the factor base.
    ("Close to" is defined as an arbitrary range.)

3. If any or all of the primes in the factor base are factors
    of (f^2)-n(mod n), save f.

4. Choose several of the saved f's such that when their squares
    are multiplied together, the prime factors of the product(mod n)
    all have even exponents.

5. Call the product of the f's x.

6. Call the square root of the product of the prime factors y.

7. Then, gcd(x+y, n) and gcd(x-y, n) are factors of n.

-----------------------------------------------------------------------------

Example:

to factor n=4633:

1. factor base = {2, 3, 5}

2. sqrt(4633) = 68.xxx, so f's "close to" 68 are, say, 38 to 98

3. For f's ((38, 98)^2) - 4633(mod n), the following have 2, 3 or 5
    as prime factors: 59, 67, 68, 69, 85, 96

4. (68 * 69 * 96)^2(mod n) = 2^8 * 3^2 * 5^2 (the exponents are all even).

5. x = sqrt((68 * 69 * 96)^2(mod n)); y = sqrt(2^8 * 3^2 * 5^2)

6. x = (68 * 69 * 96) = 450432; y = ((2^4) * 3 * 5) = 240

7. gcd(450432+240, 4633) = 41; gcd(450432-240, 4633) = 113

8. 4633 = 41 * 113

Relevant Pages

  • Re: implementing the quadratic sieve
    ... rossum wrote: ... >>I am trying to write a toy implementation of the quadratic sieve. ... the factorization having the exponent 0, and, voila, f is smooth. ... Call the square root of the product of the prime factors y. ...
    (comp.programming)
  • Re: uRe: implementing the quadratic sieve
    ... >>I am trying to write a toy implementation of the quadratic sieve. ... > You really don't need f to be close to the square root of n. ... > of the exponents of the primes in the factor base. ... You should be able to figure out q from the factorization ...
    (comp.programming)
  • Re: implementing the quadratic sieve
    ... >are familiar with the quadratic sieve, ... >Quadratic Sieve factoring algorithm: ... Call the square root of the product of the prime factors y. ... The ultimate truth is that there is no Ultimate Truth ...
    (comp.programming)
  • Re: implementing the quadratic sieve
    ... >> I am trying to write a toy implementation of the quadratic sieve. ... >You really don't need f to be close to the square root of n. ... >of the exponents of the primes in the factor base. ... >keep a list of the primes that have odd exponents. ...
    (comp.programming)