Re: On selection of polynomials for the Multiple Polynomial Quadratic Sieve



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.


.



Relevant Pages

  • Re: square root of trigometric polynomial?
    ... On the otherhand take any trig polynomial square it, ... finitely many trigonometric polynomials. ... function of t is not the square of a rational function of t ...
    (sci.math)
  • Re: More about --- Formulae for Latin squares of size 2^n
    ... Galois Field to the prime base q; for mod 2 polynomials, ... "To get primitives of non-Mersenne prime degree n, ... > standard 4x4 square. ... > permutation is orthogonal to is also orthogonal to 23 others. ...
    (sci.crypt)
  • Re: square root of trigometric polynomial?
    ... any such polynomial is identically the square of another. ... Consider the class T of trigonometric polynomials for which ... required only to be nonzero rationals, but for simplicity, ...
    (sci.math)
  • Re: Factoring problem solution
    ... NFS works this way: you have two polynomials, ... Now pick the prime factorization of both Fand Gand reduce the ... exponents in these factorizations modulo 2. ... square (this is not strictly true, but using a trick due to Adleman this ...
    (sci.math)
  • Re: Factoring problem solution
    ... NFS works this way: you have two polynomials, ... Now pick the prime factorization of both Fand Gand reduce the ... exponents in these factorizations modulo 2. ... square (this is not strictly true, but using a trick due to Adleman this ...
    (sci.crypt)