fun with msieve

[fivemack]

@fivemack: can you give me good poly for 139606*5^138+1?

Step 1: the number is less than 10^120 (this is an arbitrary bound), so you should use a polynomial of degree 4; if it were >10^200 you'd use degree 6, otherwise degree 5.

Step 2: SNFS at degree D requires you to write some multiple of your number as thing1 * thing2^D + thing3. 138 = 2 mod 4, so you can go up or down. If you go up, you write 25*k = 139606 * 5^140 + 25, if you go down you write k = 3490150 * 5^136 + 1. The numbers are smaller in the first case, so use that one.

Step 3: c4 = 139606, c0 = 25, Y0=5^35, Y1=-1 (because 5^140 = (5^35)^4). The other parameters are as in the .poly file I posted, though obviously you have to fill in the number as n.

[ValerieVonck]

Fivemack,

Following poly file gives me:

n: 400649571144766283782918537635373120355353085250791138983766578873790820125577738508582115173339843751
type: snfs
skew: 1
c4: 139606
c0: 25
Y0: 2910383045673370361328125
Y1: -1

Error: evaluated polynomial value 87253775 is not a multiple of n!

?

[ValerieVonck]

So if I figured this out for 71098*5^176+1,

Degree 4 because length(n) = 128 (>120) but close to 10^120
K=
c4= 71098
c0 = 25 (unknown to me)
Y0= 5^45 ( (5^45)^4 = 180)
Y1= 1

I think I found the error in the previous one Y1 should be 1 instead of -1

Am I making sens?

Thx

[ValerieVonck]

Apperantzly, ggbfs still crashed

[mdettweiler]

This kinda sounds like fun, what do I need to do if I want to take a whack at one of the candidates?

[ValerieVonck]

Originally Posted by CedricVonck

Apperantzly, ggbfs still crashed

Please disregard this post.

I will search further.

[mdettweiler]

I'm going to try taking a whack at 45742*5^143-1. I didn't see a link to download msieve, so I did a Google search for "msieve qs" and one of the first results was a page that had what looked like the correct program on it. I downloaded the Win32 binary application, and ran it with the command line "msieve -m", (after reading the program's syntax help, of course), so that it would ask me to input a number first thing when I started it. The program then asked me for a number, and I punched in 45742*5^143-1, and it promptly gave me a message saying "sieving in progress, press Control-C to pause". So far, everything seems to be working OK; am I dong anything wrong, though, that I haven't noticed?

Oh, and by the way, how long does it take, roughly, to factor one of these candidates? I have a P4 3.2Ghz with hyperthreading.

Edit: Also, if you have to pause in the middle of factoring a number, is it possible to resume where you left off? What command do I enter for that? When I tried stopping and restarting it, it seemed to start from the beginning again.

[jasonp]

Originally Posted by Anonymous

I'm going to try taking a whack at 45742*5^143-1. I didn't see a link to download msieve, so I did a Google search for "msieve qs" and one of the first results was a page that had what looked like the correct program on it. I downloaded the Win32 binary application, and ran it with the command line "msieve -m", (after reading the program's syntax help, of course), so that it would ask me to input a number first thing when I started it. The program then asked me for a number, and I punched in 45742*5^143-1, and it promptly gave me a message saying "sieving in progress, press Control-C to pause". So far, everything seems to be working OK; am I dong anything wrong, though, that I haven't noticed?

Oh, and by the way, how long does it take, roughly, to factor one of these candidates? I have a P4 3.2Ghz with hyperthreading.

Edit: Also, if you have to pause in the middle of factoring a number, is it possible to resume where you left off? What command do I enter for that? When I tried stopping and restarting it, it seemed to start from the beginning again.

You have the correct program, and it's working fine. A 104-digit input will take about 48 hours on your machine, plus or minus a few hours. If you stop and restart in the middle of a job, it will pick up where it left. The factors and intermediate output gets written to msieve.log by default, which you can use for more information.

[mdettweiler]

Originally Posted by jasonp

You have the correct program, and it's working fine. A 104-digit input will take about 48 hours on your machine, plus or minus a few hours. If you stop and restart in the middle of a job, it will pick up where it left. The factors and intermediate output gets written to msieve.log by default, which you can use for more information.

Okay. Oh, and by the way, after an hour of crunching, I noticed this line in my msieve.log file:

Thu Sep 06 02:08:01 2007 c105 factor: 41022844387293300773243672703262299953293914717001974036295563
1626795671706986468052491545677185058593749 (Note: I wrapped this so that it displays better in the forum, the number was actually one big line)

Does this mean that I've found a factor? If so, then I would assume that it proves conclusively that the number is composite; does this mean that I can simply submit that one factor to the sieve submission page, and be done with this number? No use wasting my time factoring the whole thing completely if it's already been proven composite, which is all that matters for this project. Am I correct that this is a factor, and if so, how would I format it for submission in the sieve import page?

[bsquared]

That number is in fact 45742*5^143-1, your input number. Msieve won't find any factors "along the way", but only at the very end. As jasonp indicated, that will take a while. We already know these numbers are composite; the point of this exercise is to find their prime factors, generally a much more complex task.

[fivemack]

Originally Posted by CedricVonck

So if I figured this out for 71098*5^176+1,

Degree 4 because length(n) = 128 (>120) but close to 10^120
K=
c4= 71098
c0 = 25 (unknown to me)
Y0= 5^45 ( (5^45)^4 = 180)
Y1= 1

Ah, no. 176 is already a multiple of 4, so you have N = 71098*(5^44)^4+1.

Which means you should have Y0 = 5^44, c4 = 71098 and c0 = 1.