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

164448 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

3,319 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

22·5·373 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

3,319 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

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

105816 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

22·5·373 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

 2020-02-26, 00:43 #19 Xyzzy     "Mike" Aug 2002 166258 Posts On our racing bicycle we use an odd and an even pair of gears if possible. This distributes the wear better. Our gearing is 53/44 front and 11-12-13-14-15-16-17-18-19-21 rear. (We don't use the 53 much!) So 11, 13, 17, 19 and 53 are prime. PS - Interesting stuff: https://en.wikipedia.org/wiki/Involute_gear
 2020-02-26, 19:48 #20 xilman Bamboozled!     May 2003 Down not across 10,151 Posts My copy of Sidgewick's Amateur Astronomer's Handbook in La Palma so unavailable for consultation. I know he gave a list of possible gear ratios to change mean solar time to sidereal time for driving an equatorial mount. There are 366.2425 sidereal days per annum but only 365.2425 solar days. IIRC, the best two sets had errors down in the ppm range.
2020-03-08, 20:05   #21
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

10000010110002 Posts

Quote:
 Originally Posted by xilman My copy of Sidgewick's Amateur Astronomer's Handbook in La Palma so unavailable for consultation. I know he gave a list of possible gear ratios to change mean solar time to sidereal time for driving an equatorial mount. There are 366.2425 sidereal days per annum but only 365.2425 solar days. IIRC, the best two sets had errors down in the ppm range.
Somebody should fix the Wikipedia page then; it says 365.2..; for sidereal. https://en.wikipedia.org/wiki/Sidereal_year and indicates a 20 minute difference. Here be headaches; timekeeping for multiple orbiting bodies. https://en.wikipedia.org/wiki/Sidereal_time
The solar day/solar year figure I recall from designing a solar tracking drive in the 1970s was 365.24202.. (probably measurement error bigger back then or remembering wrong). As I recall from a guest speaker in a high school math class, the method of continued fractions is good for arriving at whatever level of approximation you'd like by rational numbers.
The 365.2425 number you gave looks to be the Gregorian calendar approximation.
365 most years
+.25 from years divisible by 4 having a leap day
-.01 from excluding years divisible by 100
+.0025 from years divisible by 400 being leap years.
365.2425 total.

2020-03-08, 20:55   #22
xilman
Bamboozled!

May 2003
Down not across

10,151 Posts

Quote:
 Originally Posted by kriesel Somebody should fix the Wikipedia page then; it says 365.2..; for sidereal. https://en.wikipedia.org/wiki/Sidereal_year and indicates a 20 minute difference. Here be headaches; timekeeping for multiple orbiting bodies. https://en.wikipedia.org/wiki/Sidereal_time The solar day/solar year figure I recall from designing a solar tracking drive in the 1970s was 365.24202.. (probably measurement error bigger back then or remembering wrong). As I recall from a guest speaker in a high school math class, the method of continued fractions is good for arriving at whatever level of approximation you'd like by rational numbers. The 365.2425 number you gave looks to be the Gregorian calendar approximation. 365 most years +.25 from years divisible by 4 having a leap day -.01 from excluding years divisible by 100 +.0025 from years divisible by 400 being leap years. 365.2425 total.
Yup, that is the approximation, which is easily adequate for driving a telescope. If you wish, you could use 366.24202/365.24202

Wikipedia doesn't need fixing. It quotes a sidereal year in units of solar days. A sidereal day is indeed shorter than a solar day by (close to) the ratio I gave.

If it helps, recall that the Earth rotates once with respect to the stars as it goes around the sun in its orbit in addition to the rotations it makes on its axis. That is where the 366/365 approximation comes from.

Last fiddled with by xilman on 2020-03-08 at 21:02

 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 20:50.

Mon Aug 3 20:50:45 UTC 2020 up 17 days, 16:37, 0 users, load averages: 1.46, 1.44, 1.49