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

7,309 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,791 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

7,309 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

53478 Posts

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

3×113 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

2020-02-25, 18:01   #17
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

2·1,607 Posts

Quote:
 Originally Posted by R.D. Silverman 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 know it's a long time ago, but I wondered how high a prime number of gear teeth it had. "There are thus 30 driven gears corresponding to the 30 odd primes from 3 to 127." (page 239 of the earlier mentioned book.) Nowadays one could just CAD model and 3d print such a thing, but in the old days pre-CNC-machining, getting a gear with a particular prime number of teeth could be no small feat, involving finding a gear hobber, a good indexing head, and an even better machinist. https://en.wikipedia.org/wiki/Indexing_head
Thinking back to my engineering career, I recalled prime tooth count being unusual. Although it is sometimes put to good use. https://engineering.stackexchange.co...rs-in-practice
Going through an old Stock Drive Products/Sterling Instrument catalog, I found the following prime tooth counts available, in at least one pitch and pressure angle: 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 59, 71, 109, 127. That's in about 200 pages of catalog.

Last fiddled with by kriesel on 2020-02-25 at 18:36

2020-02-25, 18:14   #18
R.D. Silverman

Nov 2003

11100100011012 Posts

Quote:
 Originally Posted by kriesel I know it's a long time ago, but I wonder how high a prime number of gear teeth it had.
primes up to 37.

BTW. The computer museum moved to California. I do not know what became of the machine.

Last fiddled with by R.D. Silverman on 2020-02-25 at 18:15

 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 19:34.

Tue Feb 25 19:34:47 UTC 2020 up 25 days, 14:06, 2 users, load averages: 2.45, 2.66, 2.73

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.