RSA-129 contest

Thread View: sci.crypt

2 messages

[T] Back to Threads [V] Tree View [G] Group Articles

2 total messages Started by jbs Thu, 20 Aug 1992 23:35

#915

Author: jbs
Date: Thu, 20 Aug 1992 23:35

23 lines
1557 bytes

          I asked:
:>         How small do the coefficients have to be?  I have been led to
:>believe that the speed of the GNFS overall does not depend much on the
:>efficiency of the search for a good polynomial.  If this is the case it
:>would seem to be unwise to devote a lot of effort to finding a good poly-
:>nomial.  What is the point of this contest?
          Robert D. Silverman replied:
>This is NOT the case. The performance is VERY sensitive to the size
>of the coefficients and it is worthwhile spending a significant amount
>of time trying to find small coefficients.
          and also:
>I estimate that to be competitive with the Quadratic sieve they need
>to find coefficients of 'about' 14 digits.  I am not sure it is
>possible.
          Well, let us estimate how many numbers between 10**128 and
10**129 can be so represented.  m will be about 10**23 (so that c5*
m**5 is 10**129).  There are about 10**23 choices for m, 10**14 for
each of the ci.  This gives 10**23*(10**14)**6 or 10**107 representa-
tions.  Hence the chance that a random number between 10**128 and
10**129 has such a representation is below 10**-20.  It would appear
to me that running ECM would be a better bet than this.
                          James B. Shearer

Re: RSA-129 contest

#939

Author: D. J. Bernstein
Date: Fri, 21 Aug 1992 23:46

29 lines
1700 bytes

In article <9208202353.AA21728@ucbvax.Berkeley.EDU> jbs@WATSON.IBM.COM writes:
  [ Bob Silverman writes: ]
> > I estimate that to be competitive with the Quadratic sieve they need
> > to find coefficients of 'about' 14 digits.  I am not sure it is
> > possible.
> Well, let us estimate how many numbers between 10**128 and
> 10**129 can be so represented.

Keep in mind that---even if Bob's pessimistic estimate of 14 digits is
close to reality, which I very much doubt---f(m) can be any multiple of
n, and two-variable polynomials f(m_1,m_2) also work for GNFS. If we
were to allow 10^5 multiples of n, 10^24 choices of m_1, 10^24 choices
of m_2, and 10^14 choices of each c_i, then there would be roughly 10^9
sufficiently small polynomials for RSA-129. So from a theoretical point
of view there's no problem.

In practice, of course, finding a good polynomial takes a lot of work,
which is why we're running this contest. Obviously it doesn't make sense
to spend more time searching for good polynomials than it would take to
actually run GNFS, but the latter will take months or years on high-end
hardware; we certainly haven't reached the break-even point.

Anyone who missed the original contest announcement two weeks ago can
send mail to factor@src.dec.com with the two lines

  path#yourname@your.host
  rsastatus#

---Dan

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads