Re: On selection of polynomials for the Multiple Polynomial Quadratic Sieve
- From: Pubkeybreaker <pubkeybreaker@xxxxxxx>
- Date: Tue, 23 Mar 2010 10:27:15 -0700 (PDT)
On Mar 23, 9:32 am, Martin Lauridsen <martinlaurid...@xxxxxxxxx>
wrote:
Hello group,
For my bachelors thesis, I am to implement a parallel quadratic
sieve. I want to do this, using several polynomials, as it is my
understanding, that I can gain a theoretical maximum speedup of the
data collection phase.
I am reading an article by Robert Silverman, which describes how to
choose the coeffecients for the polynomials
Q(x) = Ax^2 + Bx + C
I am a computer science student, and sometimes the math can be tricky
for me.
The first step, he says is, that for Q(x) to generate quadratic
residues, it must hold that B^2 - 4AC = N, and that this is congruent
to either 0 or 1 (mod 4). I do not see why this holds!.
.......
What is "this"? Are you asking why B^2- 4AC is 0 or 1 mod 4?
Or are you asking why it must equal k*N (not just N) for some
selected multiplier k?
If the former, observe that all squares are either 0 or 1 mod 4 [do
you see why?]
and that 4AC is 0 mod 4.
We are trying to find polynomials f(x) such that g^2(x) = f(x) = a
mod N
and also that p divides f(x), f(x+p), f(x+2p) .... for certain
primes p (primes in the factor base)
Now solve f(x) = 0 mod p using the quadratic formula mod p and use
the fact that p is
a quad. residue of kN. If the discriminant is not a square mod N,
then the polynomial will not
generate squares mod N.
.
- Follow-Ups:
- Re: On selection of polynomials for the Multiple Polynomial Quadratic Sieve
- From: Martin Lauridsen
- Re: On selection of polynomials for the Multiple Polynomial Quadratic Sieve
- References:
- On selection of polynomials for the Multiple Polynomial Quadratic Sieve
- From: Martin Lauridsen
- On selection of polynomials for the Multiple Polynomial Quadratic Sieve
- Prev by Date: Re: Updating the Historic OTP.
- Next by Date: Re: On selection of polynomials for the Multiple Polynomial Quadratic Sieve
- Previous by thread: On selection of polynomials for the Multiple Polynomial Quadratic Sieve
- Next by thread: Re: On selection of polynomials for the Multiple Polynomial Quadratic Sieve
- Index(es):
Relevant Pages
|
