Loading ...
Sorry, an error occurred while loading the content.

QS multipliers

Expand Messages
  • Décio Luiz Gazzoni Filho
    ... Hash: SHA1 Hello, I figured out about multiplying the number n to be factored in QS by a small number m to have mn be a quadratic residues modulo many
    Message 1 of 4 , Feb 3, 2003
    • 0 Attachment
      -----BEGIN PGP SIGNED MESSAGE-----
      Hash: SHA1

      Hello,

      I figured out about multiplying the number n to be factored in QS by a small
      number m to have mn be a quadratic residues modulo many small primes. I was
      trying to code something that would find out this multiplier automatically.
      In order to do that, I test quadratic residuosity of mn (for many small m)
      modulo primes up to a small bound, say 100. I came up with a performance
      metric, which is: set a = 0, and if mn is a quadratic residue modulo p, add
      1/p to a. Then look for the highest value of a in all multipliers tested. The
      reasoning here is that smaller numbers contribute the most. But using that
      metric, here's what I obtained for RSA-129 (for m <= 30):

      No multiplier: 0.9818042063484476677777650724
      21 1.667184064168704928889792990
      6 1.557914324605730750503938962
      24 1.557914324605730750503938962
      26 1.527741592792988751194013061
      5 1.497243896414790462459092847
      20 1.497243896414790462459092847
      11 1.461885705614214965441236758
      30 1.448064969113715442532337720
      17 1.359949142887127222832992922
      14 1.334136356293016452943720741
      15 1.322004009513980879391093155
      9 1.315137539681781001111098405
      29 1.249260427737732707533545974
      19 1.237382132664049180238444489
      8 1.190858309479667878600839507
      18 1.190858309479667878600839507
      2 1.190858309479667878600839507
      3 1.129039847090011466380876713
      27 1.129039847090011466380876713
      12 1.129039847090011466380876713
      23 1.117070111240800324386042955
      10 1.094667880126791794000143738
      7 1.076872592433713518032436873
      28 1.076872592433713518032436873
      13 1.038160363180316013875203894
      4 0.9818042063484476677777650724
      16 0.9818042063484476677777650724
      25 0.9818042063484476677777650724
      22 0.7997440881350904716474085323

      And here are the quadratic residues modulo 21, 6 and 5:

      prime n 21n
      2 1 1
      3 0 1
      5 1 1
      7 0 1
      11 0 1
      13 0 1
      17 1 1
      19 1 0
      23 0 1
      29 1 0
      31 0 1
      37 1 1
      41 1 1
      43 1 1
      47 1 1
      53 0 1
      59 1 1
      61 0 1
      67 0 0
      71 0 1
      73 0 1
      79 1 1
      83 0 0
      89 0 0
      97 1 0
      Quadratic residues: 12 19
      Quadratic non-residues: 13 6


      prime n 6n
      2 1 1
      3 0 1
      5 1 1
      7 0 1
      11 0 1
      13 0 1
      17 1 0
      19 1 1
      23 0 0
      29 1 1
      31 0 1
      37 1 0
      41 1 0
      43 1 1
      47 1 1
      53 0 0
      59 1 0
      61 0 1
      67 0 0
      71 0 0
      73 0 0
      79 1 0
      83 0 1
      89 0 1
      97 1 1
      Quadratic residues: 12 15
      Quadratic non-residues: 13 10

      prime n 5n
      2 1 1
      3 0 1
      5 1 1
      7 0 1
      11 0 0
      13 0 1
      17 1 0
      19 1 1
      23 0 1
      29 1 1
      31 0 0
      37 1 0
      41 1 1
      43 1 0
      47 1 0
      53 0 1
      59 1 1
      61 0 0
      67 0 1
      71 0 0
      73 0 1
      79 1 1
      83 0 1
      89 0 0
      97 1 0
      Quadratic residues: 12 15
      Quadratic non-residues: 13 10

      But actually, the multiplier chosen by the team that factored RSA-129 was 5.
      So I assume my performance metric is wrong. Is there a better way to measure
      the effect of multipliers on QS?

      Also, 21 is clearly better than 5, but 21 adds about 2 bits to the number
      being factored compared to 5. In these cases, how do I measure whether the
      additional 2 bits are worth the increase in quadratic residues?

      Thanks

      Décio
      -----BEGIN PGP SIGNATURE-----
      Version: GnuPG v1.2.1 (GNU/Linux)

      iD8DBQE+PkL7ce3VljctsGsRAnJYAKDFBcKLceO06fNtU8juoxUVwNfulQCfUGUH
      C548EUYbnRWDahIbF0bMItE=
      =W4Ap
      -----END PGP SIGNATURE-----
    • Phil Carmody
      ... Squaresome (i.e. not squarefree) multipliers don t need tobe tried, as a^2.b ... It seems most people use the Knuth multiplier. A quick root around here
      Message 2 of 4 , Feb 3, 2003
      • 0 Attachment
        --- D�cio Luiz Gazzoni Filho <decio@...> wrote:
        > -----BEGIN PGP SIGNED MESSAGE-----
        > Hash: SHA1
        >
        > Hello,
        >
        > I figured out about multiplying the number n to be factored in QS by a small
        > number m to have mn be a quadratic residues modulo many small primes. I was
        > trying to code something that would find out this multiplier automatically.
        > In order to do that, I test quadratic residuosity of mn (for many small m)
        > modulo primes up to a small bound, say 100. I came up with a performance
        > metric, which is: set a = 0, and if mn is a quadratic residue modulo p, add
        > 1/p to a. Then look for the highest value of a in all multipliers tested. The
        > reasoning here is that smaller numbers contribute the most. But using that
        > metric, here's what I obtained for RSA-129 (for m <= 30):

        Squaresome (i.e. not squarefree) multipliers don't need tobe tried, as a^2.b
        will give you the same result as b, as the following show:

        > 6 1.557914324605730750503938962
        > 24 1.557914324605730750503938962

        > 5 1.497243896414790462459092847
        > 20 1.497243896414790462459092847

        > 8 1.190858309479667878600839507
        > 18 1.190858309479667878600839507
        > 2 1.190858309479667878600839507

        > 3 1.129039847090011466380876713
        > 27 1.129039847090011466380876713
        > 12 1.129039847090011466380876713

        > 7 1.076872592433713518032436873
        > 28 1.076872592433713518032436873

        > 4 0.9818042063484476677777650724
        > 16 0.9818042063484476677777650724
        > 25 0.9818042063484476677777650724


        > And here are the quadratic residues modulo 21, 6 and 5:
        >
        > prime n 21n
        > Quadratic residues: 12 19
        > Quadratic non-residues: 13 6
        >
        > prime n 6n
        > Quadratic residues: 12 15
        > Quadratic non-residues: 13 10
        >
        > prime n 5n
        > Quadratic residues: 12 15
        > Quadratic non-residues: 13 10
        >
        > But actually, the multiplier chosen by the team that factored RSA-129 was 5.
        > So I assume my performance metric is wrong. Is there a better way to measure
        > the effect of multipliers on QS?

        It seems most people use the 'Knuth' multiplier.
        A quick root around here indicates that the weight is 2*log(p)/(p-1) or
        log(p)/p probably depending on whether there's one or two roots, not 1/p.
        That's more or less what I'd expect, because larger primes do a proportionally
        (~log) better job of shrinking the cofactor. The (p-1) I can't explain off the
        top of my head though.

        > Also, 21 is clearly better than 5, but 21 adds about 2 bits to the number
        > being factored compared to 5. In these cases, how do I measure whether the
        > additional 2 bits are worth the increase in quadratic residues?

        Numbers that are ~n^(1/2) will have 1 more bit. The largest factor of
        such numbers will have .6 more of a bit. Therefore they will be 52% bigger.
        If you were to extend your factor base then you'd give yourself a much
        larger LA step, so you've got to take the hit primarily in sieving.

        I just did some fag-packetty calculations, and I came to the conclusion that
        the increase in sieving is fractional. I'd like to see someone else come up
        with the same figure though.

        Phil


        =====
        Polish inventions to the world cuisine include the Hamburger, (originally
        named Hzczambrzurszyngerschandwicz), which is in its traditional form a
        meat coupon in between two bread coupons.
        http://softavenue.fi/u/henry.w/poland/ parody of http://jpzr.com/finland/

        __________________________________________________
        Do you Yahoo!?
        Yahoo! Mail Plus - Powerful. Affordable. Sign up now.
        http://mailplus.yahoo.com
      • Paul Leyland
        In the immortal phrase: I think you ll find it in Knuth. In particular, Section 4.5.4 (p 383 in the 2nd edition) and Ex. 28 in that section. The analysis
        Message 3 of 4 , Feb 3, 2003
        • 0 Attachment
          In the immortal phrase: "I think you'll find it in Knuth." In particular, Section 4.5.4 (p 383 in the 2nd edition) and Ex. 28 in that section.

          The analysis there is described in terms of optimizing CFRAC but the problem and its solution are exactly the same for QS and its variants.


          Paul

          > -----Original Message-----
          > From: Phil Carmody [mailto:thefatphil@...]
          > Sent: 03 February 2003 10:59
          > To: primenumbers
          > Subject: Re: [PrimeNumbers] QS multipliers
          >
          >
          > --- Décio Luiz Gazzoni Filho <decio@...> wrote:
          > > -----BEGIN PGP SIGNED MESSAGE-----
          > > Hash: SHA1
          > >
          > > Hello,
          > >
          > > I figured out about multiplying the number n to be factored
          > in QS by a small
          > > number m to have mn be a quadratic residues modulo many
          > small primes. I was
          > > trying to code something that would find out this
          > multiplier automatically.
          > > In order to do that, I test quadratic residuosity of mn
          > (for many small m)
          > > modulo primes up to a small bound, say 100. I came up with
          > a performance
          > > metric, which is: set a = 0, and if mn is a quadratic
          > residue modulo p, add
          > > 1/p to a. Then look for the highest value of a in all
          > multipliers tested. The
          > > reasoning here is that smaller numbers contribute the most.
          > But using that
          > > metric, here's what I obtained for RSA-129 (for m <= 30):
          >
          > Squaresome (i.e. not squarefree) multipliers don't need tobe
          > tried, as a^2.b
          > will give you the same result as b, as the following show:
          >
          > > 6 1.557914324605730750503938962
          > > 24 1.557914324605730750503938962
          >
          > > 5 1.497243896414790462459092847
          > > 20 1.497243896414790462459092847
          >
          > > 8 1.190858309479667878600839507
          > > 18 1.190858309479667878600839507
          > > 2 1.190858309479667878600839507
          >
          > > 3 1.129039847090011466380876713
          > > 27 1.129039847090011466380876713
          > > 12 1.129039847090011466380876713
          >
          > > 7 1.076872592433713518032436873
          > > 28 1.076872592433713518032436873
          >
          > > 4 0.9818042063484476677777650724
          > > 16 0.9818042063484476677777650724
          > > 25 0.9818042063484476677777650724
          >
          >
          > > And here are the quadratic residues modulo 21, 6 and 5:
          > >
          > > prime n 21n
          > > Quadratic residues: 12 19
          > > Quadratic non-residues: 13 6
          > >
          > > prime n 6n
          > > Quadratic residues: 12 15
          > > Quadratic non-residues: 13 10
          > >
          > > prime n 5n
          > > Quadratic residues: 12 15
          > > Quadratic non-residues: 13 10
          > >
          > > But actually, the multiplier chosen by the team that
          > factored RSA-129 was 5.
          > > So I assume my performance metric is wrong. Is there a
          > better way to measure
          > > the effect of multipliers on QS?
          >
          > It seems most people use the 'Knuth' multiplier.
          > A quick root around here indicates that the weight is
          > 2*log(p)/(p-1) or
          > log(p)/p probably depending on whether there's one or two
          > roots, not 1/p.
          > That's more or less what I'd expect, because larger primes do
          > a proportionally
          > (~log) better job of shrinking the cofactor. The (p-1) I
          > can't explain off the
          > top of my head though.
          >
          > > Also, 21 is clearly better than 5, but 21 adds about 2 bits
          > to the number
          > > being factored compared to 5. In these cases, how do I
          > measure whether the
          > > additional 2 bits are worth the increase in quadratic residues?
          >
          > Numbers that are ~n^(1/2) will have 1 more bit. The largest factor of
          > such numbers will have .6 more of a bit. Therefore they will
          > be 52% bigger.
          > If you were to extend your factor base then you'd give yourself a much
          > larger LA step, so you've got to take the hit primarily in sieving.
          >
          > I just did some fag-packetty calculations, and I came to the
          > conclusion that
          > the increase in sieving is fractional. I'd like to see
          > someone else come up
          > with the same figure though.
          >
          > Phil
          >
          >
          > =====
          > Polish inventions to the world cuisine include the Hamburger,
          > (originally
          > named Hzczambrzurszyngerschandwicz), which is in its
          > traditional form a
          > meat coupon in between two bread coupons.
          > http://softavenue.fi/u/henry.w/poland/ parody of
          http://jpzr.com/finland/

          __________________________________________________
          Do you Yahoo!?
          Yahoo! Mail Plus - Powerful. Affordable. Sign up now.
          http://mailplus.yahoo.com

          Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
          The Prime Pages : http://www.primepages.org/



          Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
        • Phil Carmody
          ... Yuppers. I guessed it might be, even though I was aware of the absence of QS. Edition 3 has CFRAC on 397-398, but the explanation of the Schroeppel
          Message 4 of 4 , Feb 3, 2003
          • 0 Attachment
            --- Paul Leyland <pleyland@...> wrote:
            > In the immortal phrase: "I think you'll find it in Knuth." In particular, Section 4.5.4 (p 383
            > in the 2nd edition) and Ex. 28 in that section.
            >
            > The analysis there is described in terms of optimizing CFRAC but the problem and its solution
            > are exactly the same for QS and its variants.

            Yuppers. I guessed it might be, even though I was aware of the absence of QS.

            Edition 3 has CFRAC on 397-398, but the explanation of the Schroeppel
            multiplier on 400. However, the magical function is left as an exercise
            (Exercise 28).

            Fortunately it's both instructive and easy to write a simply GP script that
            will print out counts of divisors for each residue for each small prime.
            I've done this for my Fermat-with-sieves-alike, and it was a _real_
            eye-opener. (I even found a way to visualise themin 2D, and some very
            interesting (but obvious in retrospect) patterns emerged. I don't remember
            the results, but they were trivial to reproduce so I'm not worried about
            that. (And who needs GP - I did those in Perl!). I'd hope that the (p-1)
            in the formula will drop out immediately from actually counting them!

            Phil


            =====
            Shuttle mystery solved - at this speed, you'd disintegrate too!
            http://the-black-hole.org/additions/american_technology.jpg
            (Yes, the same trustworthy news source as american_geography.jpg)

            __________________________________________________
            Do you Yahoo!?
            Yahoo! Mail Plus - Powerful. Affordable. Sign up now.
            http://mailplus.yahoo.com
          Your message has been successfully submitted and would be delivered to recipients shortly.