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

• From: Tom St Denis <tom@xxxxxxx>
• Date: Wed, 24 Mar 2010 05:34:26 -0700 (PDT)

On Mar 24, 7:57 am, adacrypt <austin.oby...@xxxxxxxxxxx> wrote:
On Mar 23, 7:53 pm, Martin Lauridsen <martinlaurid...@xxxxxxxxx>
wrote:

On 23 Mar., 18:27, Pubkeybreaker <pubkeybrea...@xxxxxxx> 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.- Hide quoted text -

- Show quoted text -

Hi Martin,
This is exactly the kind of discussion that I am promoting in my
poster below.  Your discussion prompts me a follows.  I will dive in
quickly with the outline of what might be another very elegant
adaptation of the Vigenere cipher.  This is only a suggestion but it
is worth researching.  I am tempted to keep it to myself but that
would be plagiarism - some thing I despise !

<snip>

I love how despite the fact he has no idea what he's talking about or
what the QS is, he decides to inject himself in the conversation.
Awesome.

Tom
.

• Follow-Ups: