fun with msieve

[ValerieVonck]

139606*5^138+1 completed & submitted

[fivemack]

Originally Posted by CedricVonck

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!

I've just copy-and-pasted that file and it works with the version of ggnfs I have installed. The message you get is consistent with having put "Y0: 5^35" somewhere in the file, rather than expanding the number; make sure there are no other lines in the file than those.

[mdettweiler]

Originally Posted by 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.

Ah, I see. So I guess I'll have to continue all the way, then.

However, if I'm going to be crunching something that might take upwards of 48 hours on my CPU, that means that I'm going to need to be able to stop and resume the client easily, since my computer's not on 24/7. When I had last shut down my computer, I closed out msieve by pressing Control-C, and then letting it gracefully shut down; however, now when I try to run msieve, it just tells me "could not open file worktodo.ini". I don't have a worktodo.ini file; instead, I just originally ran it with the -m option so that I would be able to punch in the number directly to the program. While running, it had created a "msieve.dat" file. Now, however, when I try to just run "msieve" (I'm afraid that if I use -m and punch the number in again, then it will start all over again), it gives me the worktodo.ini error. What command do I need to launch it with in order to have it resume where it left off?

[ValerieVonck]

Originally Posted by fivemack

I've just copy-and-pasted that file and it works with the version of ggnfs I have installed. The message you get is consistent with having put "Y0: 5^35" somewhere in the file, rather than expanding the number; make sure there are no other lines in the file than those.

Dear,

Following poly gives

Error: poly coefficients have a common factor 0. Please divide it out

with following poly

n: 74229775530521455488007758492787522898438620227229981378006965553757821319102732125294955012329012333793798461556434631347656251
type: snfs
skew: 1
c4= 71098
c0 = 1
Y0= 5^44
Y1= 1

Let me say that is a nice, constructive , topic!
I appreciate that people are helping me understanding SNFS from scratch!
Respect!

[jasonp]

Originally Posted by Anonymous

When I had last shut down my computer, I closed out msieve by pressing Control-C, and then letting it gracefully shut down; however, now when I try to run msieve, it just tells me "could not open file worktodo.ini". I don't have a worktodo.ini file; instead, I just originally ran it with the -m option so that I would be able to punch in the number directly to the program. While running, it had created a "msieve.dat" file. Now, however, when I try to just run "msieve" (I'm afraid that if I use -m and punch the number in again, then it will start all over again), it gives me the worktodo.ini error. What command do I need to launch it with in order to have it resume where it left off?

As long as the number is the same as last time, restarts will automatically pick up where you left off. If you want to guarantee not losing work, copy msieve.dat to another name. When the restart happens, if the number of relations displayed involves big numbers, then you restarted fine.

You can restart with -m, or just paste the number to factor into a file named 'worktodo.ini' and run msieve without arguments.

To prevent confusion in the future, the next release will not print out any factors if none were found.

[bsquared]

Originally Posted by Anonymous

however, now when I try to run msieve, it just tells me "could not open file worktodo.ini". I don't have a worktodo.ini file; instead, I just originally ran it with the -m option so that I would be able to punch in the number directly to the program. While running, it had created a "msieve.dat" file. Now, however, when I try to just run "msieve" (I'm afraid that if I use -m and punch the number in again, then it will start all over again), it gives me the worktodo.ini error. What command do I need to launch it with in order to have it resume where it left off?

Jasonp (who wrote msieve) could tell you without hesitation, but I believe that one of the first things msieve does is compare the input number (any method of input) with the header in msieve.dat. If the numbers are the same, it will continue from where it left off. So you should be ok in using the -m option again. However, you should back up msieve.dat first before trying this, as I may be wrong. Disk space is cheap. If for some reason your msieve.dat file gets hosed (file size resets to 0), then you can restore and try something else.

If you are taking an interest in factoring 105 digit numbers, you also owe it to yourself to read up on and try to use ggnfs. Numbers this size can be factored in a few hours or less using it. Search this forum and google with ggnfs to get started.

[edit] The first part is now redundant, but I'll go ahead a reemphasize part 2: ggnfs (using SNFS). msieve is the fastest QS implementation I am aware of, but it simply can't keep up to the NFS for numbers this large.

- ben.

[mdettweiler]

Originally Posted by jasonp

As long as the number is the same as last time, restarts will automatically pick up where you left off. If you want to guarantee not losing work, copy msieve.dat to another name. When the restart happens, if the number of relations displayed involves big numbers, then you restarted fine.

You can restart with -m, or just paste the number to factor into a file named 'worktodo.ini' and run msieve without arguments.

To prevent confusion in the future, the next release will not print out any factors if none were found.

Thanks for the tips--I already had a text file sitting in the same folder (called work.txt) that contained just the number, so that I wouldn't have to go digging in this forum thread every time I needed to re-enter is, and I simply renamed that to worktodo.ini. It seems to be working fine; I've made a backup copy of msieve.dat too.

Originally Posted by bsquared

Jasonp (who wrote msieve) could tell you without hesitation, but I believe that one of the first things msieve does is compare the input number (any method of input) with the header in msieve.dat. If the numbers are the same, it will continue from where it left off. So you should be ok in using the -m option again. However, you should back up msieve.dat first before trying this, as I may be wrong. Disk space is cheap. If for some reason your msieve.dat file gets hosed (file size resets to 0), then you can restore and try something else.

If you are taking an interest in factoring 105 digit numbers, you also owe it to yourself to read up on and try to use ggnfs. Numbers this size can be factored in a few hours or less using it. Search this forum and google with ggnfs to get started.

[edit] The first part is now redundant, but I'll go ahead a reemphasize part 2: ggnfs (using SNFS). msieve is the fastest QS implementation I am aware of, but it simply can't keep up to the NFS for numbers this large.

- ben.

Okay. I'm not exactly interested in doing tons of this, just this one factor to try it out, and possibly a couple more later. I would generally rather have my CPU time put to use doing primality testing or sieving, considering that having the factored numbers isn't exactly useful to the project (as far as I know) as long as they already know the number is composite. So, considering how complex this whole ggnfs thing looks, I think I'll stick with msieve unless I somehow change direction towards doing tons of this factoring.

You know, I'm thinking that it might be kind of cool to use for this project numbers that haven't been proven prime or composite yet--since most of them are composite anyway. Then, this subproject could actually be somewhat useful to the project, rather than just being a fun little way to use up your CPU time. Then, when the factors are submitted to the factor submission page, instead of just being noted as being a factor for a number and nothing more, they'll actually help to knock down candidates.

[fivemack]

Originally Posted by CedricVonck

Dear,

Following poly gives

Error: poly coefficients have a common factor 0. Please divide it out

with following poly

n: 74229775530521455488007758492787522898438620227229981378006965553757821319102732125294955012329012333793798461556434631347656251
type: snfs
skew: 1
c4= 71098
c0 = 1
Y0= 5^44
Y1= 1

You haven't quite understood the syntax of the file; my notes are written in general maths notation, but the ggnfs input file requires the parameters to be given as

c4: 71098

with the parameter name (the c has to be lower-case, the Y has to be upper-case), a colon, a space, and the parameter value. And you have to write the numbers explicitly, so

Y0: 5684341886080801486968994140625

because

Y0: 5^44

will be parsed as setting Y0=5.

You should also put Y1 as -1 (because the value at which the polynomial is evaluated is the root of Y0+Y1*x=0, ie if you want the value to be Y then you should have Y0=Y and Y1=-1 to get the equation Y-x=0); but it doesn't matter here because the polynomial has coefficients only at even powers, and (-t)^4 = t^4.

[masser]

Originally Posted by Anonymous

You know, I'm thinking that it might be kind of cool to use for this project numbers that haven't been proven prime or composite yet--since most of them are composite anyway. Then, this subproject could actually be somewhat useful to the project, rather than just being a fun little way to use up your CPU time. Then, when the factors are submitted to the factor submission page, instead of just being noted as being a factor for a number and nothing more, they'll actually help to knock down candidates.

The numbers that have not been proven prime or composite have the from k*5^n+/-1 where n > 170000. These numbers have more than 100,000 digits, so using integer factorization programs like msieve/snfs/gnfs will not work and even if they did work in that range, they would be ridiculously inefficient.

Currently we can do primality tests that tell us whether a candidate is prime or composite. Right now, sieving (finding just one factor of a candidate) is more efficient than performing primality tests. We use srsieve to do the sieving for this project: see http://www.mersenneforum.org/showthread.php?t=6084. Eventually, perhaps when testing reaches n = 700,000, P-1 factoring will also become useful to the Base 5 Riesel Sierpinski project.

[mdettweiler]

Originally Posted by masser

The numbers that have not been proven prime or composite have the from k*5^n+/-1 where n > 170000. These numbers have more than 100,000 digits, so using integer factorization programs like msieve/snfs/gnfs will not work and even if they did work in that range, they would be completely inefficient.

Currently we can do primality tests that tell us whether a candidate is prime or composite. Right now, sieving (finding just one factor of a candidate) is more efficient than performing primality tests. We use srsieve to do the sieving for this project: see http://www.mersenneforum.org/showthread.php?t=6084. Eventually, perhaps when testing reaches n = 700,000, P-1 factoring will also become useful to the Base 5 Riesel Sierpinski project.

Okay, I see now. Actually, speaking of the sieving here, I had checked that out and am planning to probably do some in the near future. I'm already familiar with sr2sieve from the Riesel Sieve project, and I've heard that sr5sieve is simply sr2sieve with a couple extremely minor code tweaks, so it shouldn't be too hard.

As for this factoring, if that's the case, with the factoring not being useful for any purpose other than just for the fun of finding the prime factors of a number, I probably won't do any more factoring after this one number. I'll just go along and finish this one because after having put 10 hours of CPU time into it, it would be a big waste of CPU power not to. I started with the assumption that these factors were actually helping to knock down candidates by proving that they're composite. Oh well.

[masser]

36412*5^142+1 = 242493545107546848231264593265788131 * p69 = p36*p69