What a difference 30 years makes!

[schickel]

Here's an interesting quote from "What Drives An Aliquot Sequence?", from Mathematics of Computation, 1975. This is regarding the 276 sequence, and the state-of-the-art knowledge back then:

Lehmer has computed a further 200 terms which show an erratic upward tendency. The extent of our present knowledge is

107100047962427456048833497403019424 = 276:433 =

where c is a 31-digit composite with no small factors.

Kinda unbelievable when you think about it....

BTW, the c31 factors as 1171449981591251 * 4785657413964331.

[10metreh]

Originally Posted by schickel

BTW, the c311 factors as 1171449981591251 * 4785657413964331.

When was it a C311? (I wonder whether we'll be onto C311s in 30 years' time...)

BTW, how long did it take to factor the C31, and what method was used?

{Heh, no "beat you to the edit" this time!}

[Mr. P-1]

I don't know what method schickle used, but it took me less than a tenth of a second, not counting the time it took to type in the command:

echo 107100047962427456048833497403019424 | ecm -t 200 -c 10 7000
GMP-ECM 6.2 [powered by GMP 4.2.2] [ECM]
Input number is 107100047962427456048833497403019424 (36 digits)
********** Factor found trial div: 2
Found proven prime factor of  1 digits: 2^5
********** Factor found trial div: 3
Found proven prime factor of  1 digits: 3
********** Factor found trial div: 199
Found proven prime factor of  3 digits: 199
Using B1=7000, B2=754806, polynomial x^1, sigma=4282110816
Step 1 took 44ms
Step 2 took 40ms
********** Factor found in step 2: 1171449981591251
Found probable prime factor of 16 digits: 1171449981591251
Probable prime cofactor 4785657413964331 has 16 digits

real    0m0.098s
user    0m0.096s
sys     0m0.004s

[10metreh]

Originally Posted by Mr. P-1

I don't know what method schickle used, but it took me less than a tenth of a second, not counting the time it took to type in the command:

echo 107100047962427456048833497403019424 | ecm -t 200 -c 10 7000
GMP-ECM 6.2 [powered by GMP 4.2.2] [ECM]
Input number is 107100047962427456048833497403019424 (36 digits)
********** Factor found trial div: 2
Found proven prime factor of  1 digits: 2^5
********** Factor found trial div: 3
Found proven prime factor of  1 digits: 3
********** Factor found trial div: 199
Found proven prime factor of  3 digits: 199
Using B1=7000, B2=754806, polynomial x^1, sigma=4282110816
Step 1 took 44ms
Step 2 took 40ms
********** Factor found in step 2: 1171449981591251
Found probable prime factor of 16 digits: 1171449981591251
Probable prime cofactor 4785657413964331 has 16 digits
 
real    0m0.098s
user    0m0.096s
sys     0m0.004s

I mean, what method was originally used?

[schickel]

Originally Posted by Mr. P-1

I don't know what method schickle used, but it took me less than a tenth of a second, not counting the time it took to type in the command:

Read a little closer.....that was quoted from an article from 1975.

I was comparing "state of the art" then and now......

[schickel]

Originally Posted by 10metreh

I mean, what method was originally used?

I don't know. It was factored some time after the original 1975 article.....I guess someone could contact Lehmer and see if he remembers factoring it way back then.

[10metreh]

Originally Posted by schickel

I don't know. It was factored some time after the original 1975 article.....I guess someone could contact Lehmer and see if he remembers factoring it way back then.

I thought he had died back in '91 or some time around then.

[schickel]

Originally Posted by 10metreh

I thought he had died back in '91 or some time around then.

OK, we could call Jennifer Love Hewitt, then.....

[Mr. P-1]

Originally Posted by schickel

Read a little closer.....that was quoted from an article from 1975.

I was comparing "state of the art" then and now......

I understood the point of your post. I took 10metreh's question to mean how long did it take you to factorize using today's technology. (I assumed that you had, since you posted the factors.)

The point being that what was infeasible in 1975 took less than a tenth of a second in 2009 on a commodity processor which was nowhere near the fastest available even when I bought it three years ago.

I wonder how much of the advance in 30 years has been due to faster hardware, and how much due to better algorithms.

[axn]

Originally Posted by Mr. P-1

I wonder how much of the advance in 30 years has been due to faster hardware, and how much due to better algorithms.

I doubt whether faster hardware could've contributed to more than a factor of 1e6 in performance gain in 30 years.

So, my vote is for the bulk of the improvement due to faster algos.

[bsquared]

Originally Posted by Mr. P-1

I understood the point of your post. I took 10metreh's question to mean how long did it take you to factorize using today's technology. (I assumed that you had, since you posted the factors.)

The point being that what was infeasible in 1975 took less than a tenth of a second in 2009 on a commodity processor which was nowhere near the fastest available even when I bought it three years ago.

I wonder how much of the advance in 30 years has been due to faster hardware, and how much due to better algorithms.

Well, Pollard's Rho 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.