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
.
 FollowUps:
 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
 On selection of polynomials for the Multiple Polynomial Quadratic Sieve
 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):
Relevant Pages
