Prev: Updating the Historic OTP.
Next: CFP DATA MINING 2010: new date - until 29 March 2010
From: adacrypt on 24 Mar 2010 13:32
On Mar 23, 1:32 pm, 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!
>
> Might anyone help me clarify this?
>
> Thanks!

The expression (B^2 - 4AC) is the discriminant of the general
quadratic Ax^2 + Bx + C.

In order for the quadratic to have real roots (i.e. not cmplex roots)
that expression must be >= 0

In order for it to have any residue in modular arithmetic it must be
integer values all round - no float values of A, B, or C.

The modulus N has N congruence classes i.e. when N = 4 there are four
classes which have periodicity of 4 between elements.

Call the a^2 the LHS - you can see (in the distance that this divides
by four and leaves a residue of 0 when a round multiple of 4 and 1
otherwise.

This is admittedly incomplete as a proof but it is a start.

This is coming out of my memory pack from way back - I sugggest not
researching this at too high a level - I suspect it is just elementary
number theory but i can't recommend any book - regards - it didnt
occur to me that this info might be useful as a starting point earlier
- adacrypt
From: adacrypt on 24 Mar 2010 15:30
On Mar 23, 1:32 pm, 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!
>
> Might anyone help me clarify this?
>
> Thanks!

Mod 4 means there are 4 congruence classes that have periodicity of 4
i.e. the space between the residues that form the class is 4 in ech of
the four cases.

Take the general case is that a = n

Then the next a = n +1

The difference between the two consecutive a's is (n+1)^2 - n^2 =
(n^2 +2n +1) - n^2 = 2n+1

2n +1 (Mod 4) = n + 1 ( as the corresponding class residue)

(n+1 is congruent with n) (Mod 4) true for all n positive integers

The first instance is a = 0 i.e. n = 0 and n (mod 4) = 0 ,

the rest of the sequnce n(Mod 4) = 1

QED ?

Try this - regards - adacrypt
From: Martin Lauridsen on 25 Mar 2010 04:37
On 24 Mar., 01:42, Scott Contini <the_great_cont...(a)yahoo.com> wrote:
> I also learned it from Bob's paper, but if you want a second
> explanation, see:
>  http://www.crypto-world.com/documents/contini_siqs.pdf
> It's summarised compactly in Figure 2.2, and the logic behind it
> is explained in section 2 pages 6 - 9.
>
> Scott

Hi Scott.

Yes, I have found Silvermans paper to be very nice. The one you link
to (I assume you wrote it), is also very nice in the way, that it
seems to spell out things more, which is quite nice for a non-
mathematician as I.
Thank you very much for this, I will continue reading it today.
From: Pubkeybreaker on 25 Mar 2010 06:51
On Mar 25, 4:37 am, Martin Lauridsen <martinlaurid...(a)gmail.com>
wrote:
> On 24 Mar., 01:42, Scott Contini <the_great_cont...(a)yahoo.com> wrote:
>
> > I also learned it from Bob's paper, but if you want a second
> > explanation, see:
> >  http://www.crypto-world.com/documents/contini_siqs.pdf
> > It's summarised compactly in Figure 2.2, and the logic behind it
> > is explained in section 2 pages 6 - 9.
>
> > Scott
>
> Hi Scott.
>
> Yes, I have found Silvermans paper to be very nice.

Why, thank you!
From: adacrypt on 25 Mar 2010 11:33
On Mar 24, 12:34 pm, Tom St Denis <t...(a)iahu.ca> wrote:
> On Mar 24, 7:57 am, adacrypt <austin.oby...(a)hotmail.com> wrote:
>
>
>
>
>
> > On Mar 23, 7:53 pm, Martin Lauridsen <martinlaurid...(a)gmail.com>
> > wrote:
>
> > > 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.- 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- Hide quoted text -
>
> - Show quoted text -

Ok - I got it wrong - I was out of my depth and indeed barking up the
wrong tree without realising it - apologies to all concerned.

This of course means as applied to cryptography.

I believe I have proved the theorem in passing although nobody wants
to know that in the face of the bigger issue of factorizing giant
numbers.

I honestly suspect that will not come in time to be of any great value
in cryptography but there I go again jumoing the gun.

Regards - Austin O' Byrne
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5
Prev: Updating the Historic OTP.
Next: CFP DATA MINING 2010: new date - until 29 March 2010