Prev: Updating the Historic OTP.
Next: CFP DATA MINING 2010: new date - until 29 March 2010
From: Martin Lauridsen on 23 Mar 2010 09:32
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!

Might anyone help me clarify this?

Thanks!
From: Pubkeybreaker on 23 Mar 2010 13:27
On Mar 23, 9:32 am, Martin Lauridsen <martinlaurid...(a)gmail.com>
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.


From: Globemaker on 23 Mar 2010 13:31
There are books on amazon.com that explain the quadratic field sieve
QFS. If no specialists on sci.crypt will direct you to the condensed
story, you may need to do as I did, and buy several expensive books on
the math of factoring composite numbers. Reading the books on this
subject is very difficult for a non-mathematician. The computer
program to implement the QFS would be a great accomplishment for you,
or for anyone.
From: Pubkeybreaker on 23 Mar 2010 15:22
On Mar 23, 1:31 pm, Globemaker <alanfolms...(a)cabanova.com> wrote:
> There are books on amazon.com that explain the quadratic field sieve
> QFS.

There is no such thing as QFS. We have the Number Field Sieve (NFS)
which can be set up to use a qudratic FIELD, but it has little
relation
to the Quadratic Sieve.


> If no specialists on sci.crypt will direct you to the condensed
> story,

Huh? I already answered the original question! What am I? Chopped
liver?
RTFLMAO.
From: Martin Lauridsen on 23 Mar 2010 15:53
On 23 Mar., 18:27, Pubkeybreaker <pubkeybrea...(a)aol.com> wrote:
> 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.

Hi Pubkeybreaker.

I see that any square must be 0 or 1 (mod 4), since we have four
cases:

a = 0 (mod 4) => a^2 = 0 (mod 4)
a = 1 (mod 4) => a^2 = 1 (mod 4)
a = 2 (mod 4) => a^2 = 4 = 1 (mod 4)
a = 3 (mod 4) => a^2 = 9 = 1 (mod 4)

Yes, I understand that we must find some polynomial, lets call it
Q(x), which generates squares (mod N).
I have already implemented this, for the single polynomial case. Here
I use Q(x) = (x + m)^2 - N, where m = floor(sqrt(N)).

We want Q(x) to produce a lot of values, that are smooth with regard
to the factor base, for a somewhat small interval [-M, M].
I am in doubt how to choose the coeffecients A, B and C in Q(x) = Ax^2
+ Bx + C, to obtain this.
 |  Next  |  Last
Pages: 1 2 3 4 5
Prev: Updating the Historic OTP.
Next: CFP DATA MINING 2010: new date - until 29 March 2010