# 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**:

**References**:**On selection of polynomials for the Multiple Polynomial Quadratic Sieve***From:*Martin Lauridsen

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

**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***From:*adacrypt

- Prev by Date:
**Re: On selection of polynomials for the Multiple Polynomial Quadratic Sieve** - Next by Date:
**CFP DATA MINING 2010: new date - until 29 March 2010** - Previous by thread:
**Re: 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):