mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2020-01-03, 17:36   #12
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

723210 Posts
Default

Quote:
Originally Posted by Till View Post
I guess that you and RDS betted that by now (? see below) a "difficult" 1024 bit number would have been factored. RDS saying no, xilman saying yes.


Those 6 extra month may result from the bet being based in years to come, not an exact date.
I believe that I said "not before 2020". I'm not sure where the '6 months" comes from.

The bet was not just with xilman. Note that it was made over 20 years ago.
R.D. Silverman is offline   Reply With Quote
Old 2020-01-03, 18:16   #13
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

3·139 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
I believe that I said "not before 2020". I'm not sure where the '6 months" comes from.

The bet was not just with xilman. Note that it was made over 20 years ago.
Betting on something twenty years ago that might be on the edge now would be cool shit ;-)

Was it a particular number, e.g. RSA-1024 ?

Last fiddled with by Till on 2020-01-03 at 18:16 Reason: removed withespaces
Till is offline   Reply With Quote
Old 2020-01-13, 04:10   #14
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

1101101000012 Posts
Default

I kind of wish I had been involved in the factoring field back in 2000, looking back it reads like new improvements were arriving rapid-fire. Plus the patent on RSA expired in 2000 and it was set to explode in popularity.
jasonp is offline   Reply With Quote
Old 2020-01-13, 13:06   #15
jyb
 
jyb's Avatar
 
Aug 2005
Seattle, WA

2·5·157 Posts
Default

Quote:
Originally Posted by jasonp View Post
I kind of wish I had been involved in the factoring field back in 2000, looking back it reads like new improvements were arriving rapid-fire. Plus the patent on RSA expired in 2000 and it was set to explode in popularity.
You mean you weren't? From "The Twenty-Fourth Fermat Number Is Composite", Crandall, Meyer, and Papadopoulos:
Quote:
A second run by EWM using a revised version of his code was launched in late February, which caught up with JSP’s test in early summer 1999. Further improvements by JSP to his code meant that, as of late June 1999 the two floating runs were dispatching squarings at roughly the same rate, and in fact they finished within days of each other, on 27 and 31 August 1999, respectively, with exactly matching final residues.
I grant that primality proving and factoring are not the same thing, but the work you were doing was pretty closely related, both in subject and tools/methods, wasn't it?

Last fiddled with by jyb on 2020-01-13 at 13:06
jyb is online now   Reply With Quote
Old 2020-01-17, 19:44   #16
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

3×139 Posts
Default

Quote:
Originally Posted by jasonp View Post
I kind of wish I had been involved in the factoring field back in 2000, looking back it reads like new improvements were arriving rapid-fire.

Well, I could imagine that innovations still occur but they do not get published because of national interests / security concerns ;-)
Till is offline   Reply With Quote
Old 2020-01-17, 21:37   #17
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11100010000002 Posts
Default

Quote:
Originally Posted by jasonp View Post
I kind of wish I had been involved in the factoring field back in 2000, looking back it reads like new improvements were arriving rapid-fire. Plus the patent on RSA expired in 2000 and it was set to explode in popularity.
A brief history:

It has now been nearly 30 years since the computer science community
had a new factoring algorithm. The Number Field Sieve was invented in
1989 by John Pollard. Certainly there have been incremental improvements
in the algorithm, the most important of which was the development of
block methods for doing the linear algebra. Until that development,
linear algebra was done by variations of Gaussian elimination. Because
of the time and space complexity for Gaussian elimination factor base
sizes (and hence size of composites) were sharply limited.

What is strange is that in the period of 1970 through 1989 there were
more than a dozen new techniques that appeared. Prior to 1970 all
factorization methods were purely exponential: either a variant of
Fermat's method or trial division.

Then, starting in 1970 we got the following:

1970 CFRAC (known to Lehmer and Powers much earlier but not practical)
1971 Shanks' Class Group Methods (Not practical at the time)
1974 P-1
1974 Lehman's Algorithm
1975 Pollard Rho
1976 Shanks' SQUFOF and variations (unpublished)
1978 Schroeppel's Linear Sieve (not practical/not implemented/not published)
-- exact date uncertain
1980 QS (Pomerance's improvement to the Linear Sieve)
1982 Williams P+1
1985 MPQS
1985 ECM
1985 Atkins-Schnorr Classgroup
1986 SIQS
1987 FFT extensions to P-1 and ECM
1989 Bach-Shallit extension to P+1 (not practical)
1989 NFS
1990 Lattice version of NFS
1994 Block Wiedemann (exact date uncertain; based on earlier Coppersmith ideas)
1995 Block Lanczos

Note that the last two algorithms are not factoring algorithms per se,
but rather methods for dealing with the Linear Algebra that arises in
factoring algorithms.


WE NEED SOMETHING NEW!!!!!

Shor's algorithm is impossible on classical computers and is not
included here. When 1000+ qubit quantum computers become a reality, Shor's
method will merit inclusion.

Note that most of the innovations came in the 80's.
R.D. Silverman is offline   Reply With Quote
Old 2020-01-17, 21:40   #18
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by Till View Post
Well, I could imagine that innovations still occur but they do not get published because of national interests / security concerns ;-)
And your evidence is?

I've heard this claim made frequently from non-professionals. It is nonsense.
Read e.g. Berstein vs. U.S. State Department.


So called "national security concerns" did not suppress publications.
R.D. Silverman is offline   Reply With Quote
Old 2020-01-17, 21:54   #19
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

3·139 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
And your evidence is?

I've heard this claim made frequently from non-professionals. It is nonsense.
Read e.g. Berstein vs. U.S. State Department.


So called "national security concerns" did not suppress publications.

Note that I wrote "I could imagine" instead of "I believe". As such I do not claim such thing to be true, as such I think that I do not need to provide evidence.


Thanks for the history before. Dana has some slides containing later contributions, if I recall well. The 2005 Kleinjung and Franke paper looks quite good, too.
Till is offline   Reply With Quote
Old 2020-01-17, 22:09   #20
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1C4016 Posts
Default

Quote:
Originally Posted by Till View Post
Note that I wrote "I could imagine" instead of "I believe". As such I do not claim such thing to be true, as such I think that I do not need to provide evidence.
On the contrary. The way you presented it strongly suggests that you believe it.
Otherwise, why say it at all if you don't believe it?

Further, merely suggesting it spreads it as an "urban legend".

Such statements require evidence. Intelligent people do not imagine things without
evidence.

Last fiddled with by R.D. Silverman on 2020-01-17 at 22:13
R.D. Silverman is offline   Reply With Quote
Old 2020-01-17, 23:38   #21
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

131448 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
And your evidence is?

I've heard this claim made frequently from non-professionals. It is nonsense.
Read e.g. Berstein vs. U.S. State Department.


So called "national security concerns" did not suppress publications.
Coincidentally, I had a discussion with a colleague about this this week. She is aware of publications in cryptography and number theory(her former background) being suppressed in the UK.
henryzz is offline   Reply With Quote
Old 2020-01-18, 00:32   #22
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by henryzz View Post
Coincidentally, I had a discussion with a colleague about this this week. She is aware of publications in cryptography and number theory(her former background) being suppressed in the UK.
I suggest that you ask Richard Pinch.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Bad LL-D Success Rate TheMawn Data 14 2014-10-13 20:19
Another success (not)! ATH Data 133 2012-03-09 17:19
Success again?!? ATH Data 80 2011-11-15 11:40
Success?... (M46 related) lycorn News 631 2010-05-26 10:33
Success edorajh Lounge 5 2004-08-15 16:51

All times are UTC. The time now is 22:56.

Tue Oct 27 22:56:52 UTC 2020 up 47 days, 20:07, 2 users, load averages: 2.01, 1.90, 1.83

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.