I programmed the original Pollard Rho in UBASIC and inserted a counter to find how many iterations are needed. The output was 38905704.

[QUOTE=bsquared;167262]Well, [url=http://en.wikipedia.org/wiki/Pollard's_rho_algorithm]Pollard's Rho[/url] algorithm was available at some point in 1975, and with a commodity processor I can factor the C31 in about 20 seconds using Rho with 10e6 iterations on the poly x^2 + 1. Admittedly this is using Brent's faster variation, which wasn't available until 1980. If "infeasible" is defined as 1 week, then this is at least 30 thousand times faster hardware.

With QS it factors in 3 hundredths of a second on the same processor, so algorithms contribute another ~700x speed improvement.[/QUOTE]

It occurs to me that "better algorithms" and "faster hardware" aren't the only two factors. A third perhaps is "availability". Even if the number could have been factored in a week using the hardware and algorithms of the time, it's possible that the researchers did not have a week's worth of processor time to spend on it.

[quote=Mr. P-1;167297]It occurs to me that "better algorithms" and "faster hardware" aren't the only two factors. A third perhaps is "availability". Even if the number could have been factored in a week using the hardware and algorithms of the time, it's possible that the researchers did not have a week's worth of processor time to spend on it.[/quote]

Very true, and certainly availablity of computing power has drastically increased as well since 1975 (another corollary to Moore's law?). I guess my original point is that unless they spent less than ~ 20sec*700 = 4 hrs on it with Rho, the majority of the speedup appears to be hardware, not algorithms, for this size number. Assuming, of course, that the relative speed ratio between my modern day Rho and QS would have been the same in 1975 if QS had existed then.

[QUOTE=Mr. P-1;167249]I understood the point of your post. I took 10metreh's question to mean how long did it take [i]you[/i] to factorize using today's technology. (I assumed that you had, since you posted the factors.)
[/QUOTE]I have to apologize, since when I first read your reply, the forum skipped over 10metreh's message entirely, and I didn't see his question until the second time reading replies, so I thought you were replying to my original message.. (I've seen that before, sometimes reading "new replies" starts at a later reply....the perils of live reading, I guess....)

I guess the real question is, does someone have some old hardware we could run this stuff on? I have a 10+ year old PC, unfortunately, it won't boot no more. :sad: (I keep thinking I should pull the HD and see if there's anything I need on there.)

[quote=schickel;167378]I guess the real question is, does someone have some old hardware we could run this stuff on? I have a 10+ year old PC, unfortunately, it won't boot no more. :sad: (I keep thinking I should pull the HD and see if there's anything I need on there.)[/quote]

I guess someone could write a REALLY SLOW implementation of Pollard's original rho method... :wink:

What a difference another three years make!
Greetings from 21-Dec-2012!

You will be pleased to know that in 2012, all your sequences are belong to us!

[QUOTE=schickel;167378]I guess the real question is, does someone have some old hardware we could run this stuff on? I have a 10+ year old PC, unfortunately, it won't boot no more. :sad: (I keep thinking I should pull the HD and see if there's anything I need on there.)[/QUOTE]Yup.

What do you want? The oldest machine I have powered up at the moment is relatively new but there's a fair chance I could get something running from the 1970s.

You might have to provide software on 8" floppies ...

Paul

According to wikipedia, CFRAC was translated into a computer-friendly algorithm around 1975, so that may have been the most advanced algorithm available. Without a lot of tweaks, even CFRAC would huff and puff trying to factor a C31.

[QUOTE=xilman;167937]Yup.

What do you want? The oldest machine I have powered up at the moment is relatively new but there's a fair chance I could get something running from the 1970s.

You might have to provide software on 8" floppies ...

Paul[/QUOTE]
Sorry, I lost my last 8" floppy after someone ironed it after trying to stuff it in a 3.5" drive....:sad:

is that some sort of april fool's joke? it's hard to believe that actually happened.

[QUOTE=Joshua2;167974]is that some sort of april fool's joke? it's hard to believe that actually happened.[/QUOTE]:innocent: :whistle:

You caught me.....that's an amalgamation of a couple of different tech support urban legends.