mersenneforum.org Factoring Large Numbers (RSA) - Quirky Idea
 Register FAQ Search Today's Posts Mark Forums Read

2020-02-13, 13:02   #12
R.D. Silverman

Nov 2003

37·197 Posts

Quote:
 Originally Posted by LaurV Don't need to mention it. The general problem with the newcomers here (and few of the "old salts" too, even some with math background) is that they do not grasp the magnitude of the numbers we are working with. From time to time we got people trying to teach us new factoring methods, and exemplifying such methods on 3 or 5 digits numbers (we have few of such people who are residents here on the forum, already). Factoring is an easy task. Is the magnitude of the numbers that makes it hard. One hundred digits (which we can factor very easy, in hours or minutes, depending on the hardware), is about the number of atoms in a billion trillions universes... If you indeed discover a method which will be one thousand times faster than the current methods, the effect will just be that people will factor numbers with 50 more digits or so, than we are able to do today. You would need to do much better than that.
D. Lehmer once said that factoring would always be a hard problem because any new
method is very quickly pushed to its limits.

2020-02-13, 16:55   #13
Dr Sardonicus

Feb 2017
Nowhere

2×19×73 Posts

Quote:
 Originally Posted by R.D. Silverman D. Lehmer once said that factoring would always be a hard problem because any new method is very quickly pushed to its limits.
Recreations in the Theory of Numbers has a chapter ("Resolution") on factoring, which features the factoring machine that the Lehmers (father and son) devised.

If you want to see currently state-of-the-art methods being pushed to their limits, you could do worse than some of the threads of the Mersenne Forum.

2020-02-13, 17:45   #14
R.D. Silverman

Nov 2003

37×197 Posts

Quote:
 Originally Posted by Dr Sardonicus Recreations in the Theory of Numbers has a chapter ("Resolution") on factoring, which features the factoring machine that the Lehmers (father and son) devised. If you want to see currently state-of-the-art methods being pushed to their limits, you could do worse than some of the threads of the Mersenne Forum.
Machine? Or did you mean machines? Which one did you have in mind?
They built a number of them. A paper-tape sieve, the photo electric gear sieve,
DLS-127, DLS-157, etc.

Back in the 80's when the computer museum was still in Boston I got to play
with their photoelectric sieve. It was not on display (of course!). It was held
in storage because the public would never be interested in such a thing (can you hear
the sarcasm?). It lacked a drive belt, light source, and photo receptor, but I provided
a common auto fan belt that fit, a gas laser and a photo multiplier and got it to work.
[I had a letter from Dick Lehmer to the museum staff asking the staff to let me try].

I was actually amazed that the drive motor still functioned.

The device had a bunch of gears, each with a prime number of teeth. Each gear also
had a circular ring of small holes, corresponding to the teeth. You programmed
the thing by plugging the holes with toothpicks! When it was turned on it would
spin all the gears until one set of holes lined up. The lineup was detected
by a flash of light that poked through the holes. A counter on the top revealed the
number of revolutions. It was clunky and slow relative to even a Sun-2, but it worked!

I had fun trying to explain the thing to the staff. They were clueless as to what the
machine was or even after I explained it.

The sad thing is that the device was on display at least back in 1984 when the
museum was still at DEC in Marlborough. I know, because I was working there at the time.
[an extraordinary coincidence, which is how I knew about the status of the machine].

2020-02-13, 19:45   #15
Dr Sardonicus

Feb 2017
Nowhere

Quote:
 Originally Posted by R.D. Silverman Machine? Or did you mean machines? Which one did you have in mind? They built a number of them. A paper-tape sieve, the photo electric gear sieve, DLS-127, DLS-157, etc.
The photo electric gear sieve.

There's a photograph of it in the book to which I provided a link. If you go there, a text search for "gears" will get you to the right place pretty quickly.

2020-02-18, 20:29   #16
jwaltos

Apr 2012

1010011012 Posts

Quote:
 Originally Posted by Dr Sardonicus
Beiler's book (and Dorrie's) are two of my favourites. Nice to see Beiler's book quoted.

Last fiddled with by jwaltos on 2020-02-18 at 20:42

 Similar Threads Thread Thread Starter Forum Replies Last Post MarcinLesniak Miscellaneous Math 16 2019-03-26 23:30 ThiloHarich Factoring 15 2017-03-06 11:23 Merfighters Miscellaneous Math 2 2010-10-29 16:51 Mini-Geek Programming 10 2008-07-31 17:04 Bundu Software 5 2004-08-26 01:56

All times are UTC. The time now is 21:53.

Wed Feb 19 21:53:25 UTC 2020 up 19 days, 16:25, 1 user, load averages: 2.75, 2.39, 2.43