Re: implementing the quadratic sieve

From: rossum (rossum48_at_coldmail.com)
Date: 11/02/04 

Date: Tue, 02 Nov 2004 22:02:47 +0000

On Mon, 01 Nov 2004 20:44:45 GMT, Marlene Stebbins <marlene@mail.com>
wrote:

>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.
If you want more math background then http://mathworld.wolfram.com/ is
an excellent site. It covers the quadratic sieve at
http://mathworld.wolfram.com/QuadraticSieve.html

>
>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.)
You can save time here by generating the required numbers in order.
By doing this you can just use addition or subtraction in place of
squaring and mod.

Taking 4633 as in your example:

69^2 = 4761 -> 128 mod 4633
70^2 = 4900 -> 267 mod 4633
71^2 = 5041 -> 408 mod 4633
72^2 = 5184 -> 551 mod 4633
73^2 = 5329 -> 696 mod 4633

Given the question "What is the next number in the sequence 128, 267,
408, 551, 696, ..." you should be able to tell by just using addition.

>
>3. If any or all of the primes in the factor base are factors
> of (f^2)-n(mod n), save f.
You might want to look at the concept of "smooth" numbers here
(http://mathworld.wolfram.com/SmoothNumber.html). These are numbers
with no prime factor larger than a given k. Any number with a single
large factor (large defined as greater than k) will not make a square
unless it is multiplied by another number with the same factor.
Unlikely if the factor is large.

>
>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.
Given the number of tries you will potentially have to make before
finding a successful match, you need to think of a way to use the
known factorisations of A and B to generate the factorisation of AB
without having to actually factorise AB.

>
>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.
>

A word of warning. From your post I can tell your age (9th grade),
your probable sex (Marlene) and your e-mail address. You should be
more cautious about the information that you release onto Usenet. At
the very least you are in danger of receiving a lot of spam e-mails
advertising irrelevant (to you) anatomical enlargements.

rossum 

--
The ultimate truth is that there is no Ultimate Truth

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
    ... >> 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)
  • Re: Surrogate factoring, key points
    ... Astute readers should note that it's not the quadratic sieve either, ... where T is the target but there is no vector analysis or anything like ... So it's the no thinking approach to factoring. ... as I have the biggest readership of any poster on these newsgroups. ...
    (sci.math)
  • Prime numbers and the RSA algorithm
    ... depends upon the impracticality of factoring N back into p and q. ... If it is easy to check p for primeness, ... by factorization or by dividing ... it by every number between 2 and the square root of N. ...
    (sci.math)