Re: implementing the quadratic sieve

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

Date: Wed, 03 Nov 2004 00:53:54 GMT

rossum wrote:
> 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

An excellent site for those with a lot of math under their belt.
I usually have a hard time getting past the jargon and notation and am
always looking for plain English explanations and practical examples.
>
>
>>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.

Would it be 843 (696+147), by any chance? Did you start with 69 because
69 == ceil(sqrt(4633))?
>
>
>>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.

I read that "B smooth" numbers have all their prime factors in
the factor base. So I'm thinking that if only 2 of the numbers
in the factor base are factors of f, then the rest can be included in
the factorization having the exponent 0, and, voila, f is smooth.
E.g. 108 = 2^2 * 3^3 * 5^0 = 4 * 27 * 1 Or is that cheating?

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.

What are A & B equivalent to in my notation?
>
>
>>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.

I learned my lesson about Usenet a long time ago. The email address
is fake. If you can find me from the information I have provided, I
will be happy to consider your offer. Anyway, I have a list of dirty
words in my email filters that would make George Carlin look like
Mother Theresa. I appreciate your concern though.

Marlene

PS- actually, I wouldn't mind some private correspondence with someone
with some knowledge of this subject. At this point it's more about
math than programming and maybe OT for this group.
>
>
> rossum
>
>
> --
>
> The ultimate truth is that there is no Ultimate Truth

Relevant Pages

  • 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)
  • uRe: implementing the quadratic sieve
    ... > I am trying to write a toy implementation of the quadratic sieve. ... requirement is really only required for optimizing the algorithm. ... 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)
  • Re: BigInteger enhancing
    ... If you are after factorization with quadratic sieve, ... The custom code was about twice faster, ...
    (comp.lang.java.programmer)