Re: Factorization status in the 1970's

From: Jean-Luc Cooke (jlcooke_at_engsoc.org)
Date: 07/08/04 

Date: 8 Jul 2004 17:29:27 GMT

In public circles, Pollard was the big name in late 1970s.

1974:
  http://mathworld.wolfram.com/Pollardp-1FactorizationMethod.html

1975:
  http://mathworld.wolfram.com/PollardRhoFactorizationMethod.html

That's a start.

JLC

Francois Grieu <fgrieu@francenet.fr> wrote:
> On a French group, a discussion started on if the progress
> in factorisation since RSA publication in 1977 [1] is to be
> attributed principaly to theoretical progress, or an increase
> in computing power.

> I found a lack of bibliographical data for factoring in the
> 1970's; in particular, no reference on the sate of the art
> circa 1977, preferably with a rough indication of computer
> time spent. Hard data seem to start circa 1982 [2].

> Any pointer ?

> Francois Grieu

> [1] R.L. Rivest, A. Shamir, and L. Adleman: "A Method for
> Obtaining Digital Signatures and Public-Key Cryptosystems"
> Communications of the ACM archive Volume 21,?Issue 2
> (February 1978, first submitted April 4, 1977).
> <http://theory.lcs.mit.edu/~rivest/rsapaper.pdf>

> [2] Davis, J. A., Holdridge, D. B. and Simmons, G. J
> "Status report on factoring (at the Sandia National Labs)"
> Eurocrypt 1984.
> <http://google.com/search?q=Status+report+factoring+Sandia+National+Labs> 

--

Relevant Pages

  • Re: Factorization status in the 1970s
    ... Francois Grieu wrote: ... > On a French group, a discussion started on if the progress ... > attributed principaly to theoretical progress, ... Computing power has increased by only a factor ...
    (sci.crypt)
  • Re: Factorization status in the 1970s
    ... Computing power has increased by only a factor ... Which gives that Moore's law did close to half of the job. ... Obtaining Digital Signatures and Public-Key Cryptosystems" ...
    (sci.crypt)
  • Re: Factorization status in the 1970s
    ... > in computing power. ... > I found a lack of bibliographical data for factoring in the ... Theoretical progress is certainly pretty vast. ... 1st bug in MS win2k source code found after 20 minutes: ...
    (sci.crypt)
  • Re: Factorization status in the 1970s
    ... >> attributed principaly to theoretical progress, ... law as doubling of computing power every 18 month; ... of Moore law, but took only 26, so on a log scale Moore's ... and no useful data to build such reference ...
    (sci.crypt)
  • Re: Factorization status in the 1970s
    ... Francois Grieu wrote: ... computing power actually increased at that rate (for the task of ... Is factoring CPU-bound or memory-bound? ... subsystems increase at different rates. ...
    (sci.crypt)