Time it takes to select polynomials for 154 digits

[xilman]

Originally Posted by John5788

I lowered e to 2.00e-12 and the first polynomial was found pretty early:

-> =====================================================
-> Best score so far: 0.000000e+00 (goodScore=2.000000e-12)
-> =====================================================

-> Searching leading coefficients from 341001 to 342000.
=>  "../bin/pol51m0b" -b testFactor/testFactor.polsel.-gentoo1.16383 -v -v -p 7 -n 4.86E+023 -a 341 -A 342 > testFactor/testFactor.polsel.-gentoo1.16383.log
=>  "../bin/pol51opt" -b testFactor/testFactor.polsel.-gentoo1.16383 -v -v -n 6.13E+021 -N 1.48E+019 -e 2.00E-012 > testFactor/testFactor.polsel.-gentoo1.16383.log
M: 6345804928334754720431658612586053227344434344621313816572578856699293063157369614971879920373432240149347818163172848912889130278051942057123943802252773
Murphy_E: 2.24e-12
Y0: -474476921671002389987129456480
Y1: 264677853183412867
alpha: -6.96
c0: 45436887182203702187613529219004158389
c1: 9618343556994505527608625494947
c2: -121412576663303375538788791
c3: -23859647401868808903
c4: 46472546111430
c5: 342000
norm: 1.23e+22
skewness: 1811932.11
-> =====================================================
-> Best score so far: 2.240000e-12 (goodScore=2.000000e-12)
-> =====================================================

-> Searching leading coefficients from 342001 to 343000.
=>  "../bin/pol51m0b" -b testFactor/testFactor.polsel.-gentoo1.16383 -v -v -p 7 -n 4.86E+023 -a 342 -A 343 > testFactor/testFactor.polsel.-gentoo1.16383.log
=>  "../bin/pol51opt" -b testFactor/testFactor.polsel.-gentoo1.16383 -v -v -n 6.13E+021 -N 1.48E+019 -e 2.00E-012 > testFactor/testFactor.polsel.-gentoo1.16383.log

As a matter of interest, what is the integer you are trying to factor? Not the numerical value, which you've already posted, but why is that particular integer of sufficient interest that you're prepared to spend a great deal of time and effort to factor it?

Paul

[jasonp]

Originally Posted by xilman

As a matter of interest, what is the integer you are trying to factor? Not the numerical value, which you've already posted, but why is that particular integer of sufficient interest that you're prepared to spend a great deal of time and effort to factor it?

Now that the available tools are powerful enough for a single user to factorize a (small and unsafe) RSA key, I assume that any 154-155 digit GNFS job is either

- a school project
- the copy protection from old software
- a crackme (a toy version of the previous)
- a public key from the 90s

[xilman]

Originally Posted by jasonp

Now that the available tools are powerful enough for a single user to factorize a (small and unsafe) RSA key, I assume that any 154-155 digit GNFS job is either

- a school project
- the copy protection from old software
- a crackme (a toy version of the previous)
- a public key from the 90s

Sure, but it would still be nice to know what it is.

Paul

[Batalov]

Originally Posted by John5788

well I haven't been to that exact site to try factoring numbers, but I have tried a few sample RSA100 numbers which took less than a day to complete

Some time ago I linear-fit the log transformed times I had on a 2.6GHz Opteron on a hundred various SNFS's (not imaginary, real runs, from a 100 to 218), and it was a classic L(1/3) fit. D-oh! No surprise here. Every 30 orders of maginitude for SNFS (21-22 orders for GNFS) - expect 10 times more work.
What matters is the coefficient.
For that Opteron the line went through these values:
SNFS-120 1hour
SNFS-150 10hrs
SNFS-180 100hrs
SNFS-210 1000hrs
SNFS-225 3200hrs

GNFS-94 3hrs
GNFS-105 10hrs
SNFS-127 100hrs
SNFS-149 1000hrs
SNFS-160 3200hrs

Something like that.

So if for RSA100 you needed less than a day, for RSA154 you will need less than ~300 days (~10^(54/22) harder). Of which (see above) use about ~15 days for poly selection (5%). Don't take these numbers as a promise; your mileage may vary. In the higher range you have to work hard for that log-log linearity.

Just my 2 roubles,

--Serge

[miklin]

These keys can be made Msieve for 10 - 15 days easily.

[John5788]

alright after running factMsieve.pl for 48 hours, the polynomial selected had a score of 2.71e-12, which seems to be pretty decent.

now it seems to be searching for relations, needs at least 2868670, and I've found 525900 relations. I've enabled the 4 threads in factMsieve.pl, hopefully it will make things quicker.

for those wondering what I am up to, this is kind of a school related number I am trying to factor. It's just that my lab partner decided to make a 512bit RSA modulus and wanted me to try factoring it, seeing if it was actually possible for us to do something pretty significant like this. at the same time, I gave him a 512bit number and we'll see the results in the end.

[R.D. Silverman]

Originally Posted by John5788

It's just that my lab partner decided to make a 512bit RSA modulus and wanted me to try factoring it, seeing if it was actually possible for us to do something pretty significant like this. at the same time, I gave him a 512bit number and we'll see the results in the end.

The effort required to factor an RSA-512 bit modulus is well known.

Please explain why you believe that what you are doing is

"something pretty significant ".

You are simply using code written by someone else to do something
that we already know how to do. This is not a "leading edge"
computation.

[S485122]

Originally Posted by R.D. Silverman

The effort required to factor an RSA-512 bit modulus is well known. Please explain why you believe that what you are doing is "something pretty significant ".
You are simply using code written by someone else to do something that we already know how to do. This is not a "leading edge" computation.

Some people are climbing montains that have been climbed before, using materials, routes and techniques found and produced by others. They are not champions, they are not the best, some others find it dangerous, costly and futile.... They will not be the first to do it, but they still want to do it.

I, for instance, derive my mathematical pleasures from so much less worthy things (it is amazing how much you loose over the years when you have a mechanical job...)

This particular pursuit may not be interesting for a top mathemacian, but it is worthwile for lesser beings, let them shovel up dust in peace while you contemplate the high spheres ;-)

Jacob

[R.D. Silverman]

Originally Posted by S485122

Some people are climbing montains that have been climbed before, using materials, routes and techniques found and produced by others. They are not champions, they are not the best, some others find it dangerous, costly and futile.... They will not be the first to do it, but they still want to do it.

I, for instance, derive my mathematical pleasures from so much less worthy things (it is amazing how much you loose over the years when you have a mechanical job...)

This particular pursuit may not be interesting for a top mathemacian, but it is worthwile for lesser beings, let them shovel up dust in peace while you contemplate the high spheres ;-)

Jacob

Go for it. I was only questioning the "highly significant" hype.

And I don't understand what people get from blindly running someone
else's code unless it is a game or tool of some kind that one uses to accomplish something. However, this is *my* failing.

And I am definitely *not* a 'top' mathematician.

[xilman]

Originally Posted by R.D. Silverman

And I don't understand what people get from blindly running someone else's code unless it is a game or tool of some kind that one uses to accomplish something.

Now there's a thought! I'd never really considered factoring and the like as having (some of) the qualities of a game. Now that you've drawn my attention to it I can see some similarities.

Thanks for the enlightenment.


Paul

[sean]

Originally Posted by xilman

Now there's a thought! I'd never really considered factoring and the like as having (some of) the qualities of a game. Now that you've drawn my attention to it I can see some similarities.

Thanks for the enlightenment.


Paul

Factoring is certainly more fun and more rewarding than solitaire :-)