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

11245RE: [PrimeNumbers] QS multipliers

Expand Messages
  • Paul Leyland
    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/
    • Show all 4 messages in this topic