ubasic script for automated GNFS
 

I have coded an Ubasic script which is doing automated GNFS for numbers >c97. This script is designed to work together with aliquot.ub (see aliquot sequences thread), but it can also be used for factorizations which are not related to aliquot.ub.

Features:

[b]required programs[/b] - make sure to have them in the same directory where you are running ubasic:

- msieve.exe, version 1.39 or higher
- GGNFS

[b]IMPORTANT:[/b] Due to ubasic software limitations, the script can only read filenames in "8+3" format. Therefore you NEED to rename your copy of GGNFS's gnfs-lasieve4I1?e.exe to nfs4I1?e.exe (i.e. nfs4I12e.exe, nfs4I13e.exe, etc.).

[b]IMPORTANT #2[/b]: If you want to use gnfs.ub together with aliquot.ub, you need to add the following line [b]to the aliquot.ub script[/b] (you will find the proper place by looking at the line number):

[code]11375 if N>10^97 then kill "start.txt":print="start.txt":print cutspc(str(N)):run "gnfs.ub" 'run gnfs for numbers > c97[/code]


*** features ***

gnfs.ub is designed to work as an addition to aliquot.ub (and to hand over any found factor to aliquot.ub), but it can also be used to factor any composite which is not necessarily related to aliquot sequences.

There are four ways to use the program - gnfs.ub automatically checks which one you are doing in this order:

1.) (this one requires aliquot.ub which is modified by adding the line 11375 which is mentioned above.): When aliquot.ub gets a composite which needs GNFS (anything bigger than ~c97), then it creates all files which are needed to hand over the data, and then starts gnfs.ub. gnfs.ub will now read the data handed over by aliquot.ub and factors the composite by gnfs (gnfs.ub looks if a file named daten.ubd exists to see if it was started from aliquot.ub). When it is finished, the factors are handed over, and aliquot.ub is started again. (gnfs.ub only starts aliquot.ub when it was started by aliquot.ub itself.)

[b]IMPORTANT[/b]: If you are running aliquot.ub, and you want to factor a composite which is not related to your aliquot sequence, make sure to copy gnfs.ub and all files needed (see above) to a new folder - otherwise it will likely screw up your aliquot sequence run.

2.) Create a file, named "worktodo.txt", which contains the composite you want to factor. If this file exists (and gnfs.ub was not started by aliquot.ub), then gnfs.ub reads the composite from this file. When the factoring is finished, you will find the factors either in the file msieve.log, or in msieve.old. (msieve.log might get deleted after it has been copied to msieve.old.)

3.) When you already have got a polynomial (found by msieve), copy the msieve.fb file, which is containing the polynomial, to the folder where you run ubasic. Don't create a worktodo.txt file in this case (and make sure to delete older worktodo files)! gnfs.log will now perform the factoring using this polynomial. When the factoring is finished, you will find the factors either in the file msieve.log, or in msieve.old. (msieve.log might get deleted after it has been copied to msieve.old.)

4.) When gnfs.ub finds neither of the files mentioned in 1.) to 3.), then it asks to input the composit from an input line. When the factoring is finished, you will find the factors either in the file msieve.log, or in msieve.old. (msieve.log might get deleted after it has been copied to msieve.old.)

Hint: gnfs.ub will NOT factor anything which is smaller than ~2^320 = 2.135987...*10^96 - which appears to be msieve's lower limit for gnfs polynomial search. I used a number of just above this size for testing this script:

2732584592441395021720194901150787772285943502010496085503949065307202194967953137523967798489349

Hint #2: For those who want to have some statistics, gnfs.out prints the composite size, the size of the sieved special Q range and the number of relations found to a file named "stats.txt".

Version 1.01 (bugfix)
 

Version 1.01 is available. It contains a fix for a bug which caused a crash when writing factorization statistics to file.

changelog:

- fixed bug in line 4280 which caused the script to crash with an "illigal parameter" error when printing the statistics of a just finished factorization to stats.txt

another bugfix *grrr*
 

version 1.02 is available (bugfix): I forgot to comment out a line which is just for testing. If you are currently running 1.01, and it crashed with either "break in 4245" or "syntax error in 4245", then do the following:

1.) Look into the "msieve.log" file - your factorization may have already finished and you find the factors there. If gnfs.ub has been started from aliquot.ub, just start aliquot.ub, press strg-c, type "goto 600" and then input the factor(s).

2.) If the factorization has not yet finished (msieve.log saying "filtering wants xxxx more relations"), you can manually finish your factorization using GGNFS: the "last.spq" file holds the value of the last sieved special Q, "poly1.job" contains the polynomial, and "relation.rel" contains your relations.

3.) Make sure to delete or rename the "relation.rel" and "msieve.log" files after you have finished your factorization - or the next factorization could be screwed up. (I just got a msieve.log file holding 450 MB (sic!) of "error -11 when reading relation xy" lines due to forgetting to delete the old relation.rel file.)

lines 4280 and 4245 seemed to be jinxed....
 

Version 1.03

*now* it should work. (I hope.)

thanks for making this
this will be very helpful when my new sequence gets to gnfs stage
now we have got this it might be worth reducing ecm a bit

[QUOTE=henryzz;161432]thanks for making this
this will be very helpful when my new sequence gets to gnfs stage
now we have got this it might be worth reducing ecm a bit[/QUOTE]

When your sequence gets to gnfs stage, save a copy of the files created by aliquot.ub - just in case.

I was able to test the handing over of the factors from gnfs.ub to aliquot.ub only once so far (and with a "cheated" goto statement after I hit and fixed a bug in the sieving stage), so my script might still contain bugs in some routines.

edit: make sure to run version 1.03 - any earlier version will definitely crash due to the bugs described above.

[quote=Andi47;161433]When your sequence gets to gnfs stage, save a copy of the files created by aliquot.ub - just in case.

I was able to test the handing over of the factors from gnfs.ub to aliquot.ub only once so far (and with a "cheated" goto statement after I hit and fixed a bug in the sieving stage), so my script might still contain bugs in some routines.

edit: make sure to run version 1.03 - any earlier version will definitely crash due to the bugs described above.[/quote]

And as it to use. Where to take BASIC???

Version 1.04 (Bugfix & added resume functionality)
 

[b]Version 1.04 is available[/b]

changes:

- uses a larger qintsize for larger factoring jobs
- fixed a bug which can lead to a crash in line 13400 ("illegal parameter in 13400" error). If gnfs.ub crashes this way, you can find the factors in the file "msieve.old". You can resume running aliquot.ub by starting it, pressing Ctrl-C, then type "goto 600" and input the factor(s).
- added Resume functionality: If gnfs.ub gets interrupted, you will find a file named ".last_spq0" in your folder where you are running gnfs.ub. Copy this file to a file named "resume.txt". Make sure that a file named "msieve.fb", holding your polynomial in msieve format, exists. (this should normally be true, hence this file is created during a gnfs.ub run). Then run gnfs.ub. The script will now read the resume.txt file, start msieve to determine how many relations are still needed, and then resume sieving.



[QUOTE=miklin;161436]And as it to use. Where to take BASIC???[/QUOTE]

In the aliquot sequence thread (in [URL="http://www.mersenneforum.org/showpost.php?p=158895&postcount=300"]this posting[/URL]), you will find a link to the "aliquot.ub" script, and the zipped file containing this script, also contains UBASIC.

version 1.05 (Bugfix)
 

So HOW big must a club be to hammer into the script, that F is an integer variable and not some illegal thingy? *grrr*

If gnfs.ub had crashed with "illegal parameter in 13400", you can get the factors from msieve.old and continue running aliquot.ub as described in my previous post. Make sure to delete the relation.rel file, otherwise msieve will get millions of "error -11 when reading relation xy" lines in your next factorization. (the factorization will finish anyway, but with unnecessarily huge msieve.log / msieve.old files.)

[b]Version 1.05[/b]

- added a second fix to prevent "illegal parameter" errors in line 13400 - now it should work, I tested with three c100'ish factorizations. (I copied this routine from aliquot.ub, there it had worked hundreds of time, so why did it error in gnfs.ub versions 1.03 and 1.04?)
- some more informations are printed to screen.

Could you change the "Warning: This factorization WILL take several years!!"? A number greater than 200 digits will take longer than several years!

Version 1.05a
 

[QUOTE=10metreh;162067]Could you change the "Warning: This factorization WILL take several years!!"? A number greater than 200 digits will take longer than several years![/QUOTE]

I think that it won't even start, but I will change the warning to "several decades" in the next version. :wink: (btw: even 100+ years are "several" years. :alien2: )

BTW: As said in the comments to the lines defining the parameters: I think, that the parameters for factorizations up to ~c137 are not too far away from optimum, anything above are wild or even VERY wild guesses. (see also the comment in line 2800. :wink:).

BTW 2: Although the script will probably factor anything up to msieve's upper poly search limit (currently c155?), I would recommend to do some parameter optimizations and a manually attended (multithreaded) run for anything bigger than c130 ... c140.

Edit: Attached version 1.05a which contains the reworded warning.

Version 1.06
 

[b]Version 1.06 is available.[/b]

This version contains a fix for a bug which resulted in wrong Q-range-size values printed to the stats.txt file.

[quote=Andi47;162793][B]Version 1.06 is available.[/B]

This version contains a fix for a bug which resulted in wrong Q-range-size values printed to the stats.txt file.[/quote]

Two severals in the warning.

[QUOTE=10metreh;162813]Two severals in the warning.[/QUOTE]

[b]Version 1.06b[/b]

corrected a writing error (double word) in the screen output which you see when you try to factor anything bigger than c200

it has reached gnfs stage
i am currently sieving
so far it seems to be working fine

[quote=henryzz;163601]it has reached gnfs stage
i am currently sieving
so far it seems to be working fine[/quote]
i keep on forgetting to say that when it came to do the postprocessing it failed with "Division by zero in 5220"
i then realized that there was no large file with all the relations
do you need cat.exe in the directory? it isnt mentioned in the first post of this thread

[QUOTE=henryzz;164148]i keep on forgetting to say that when it came to do the postprocessing it failed with "Division by zero in 5220"
i then realized that there was no large file with all the relations
do you need cat.exe in the directory? it isnt mentioned in the first post of this thread[/QUOTE]

Yes, you need cat.exe in the directory. (can a mod please edit this info into my start posting?)

[quote=Andi47;164167]Yes, you need cat.exe in the directory. (can a mod please edit this info into my start posting?)[/quote]
i added cat.exe and it is no different
looking at the code it seems to be using copy not cat
[code] 3590 f=cutspc(str(q)):print "sieving: i=";i;", q0= ";q;", special Q range size: ";qintsize:print "starting siever":print "input: C";cutspc(str(alen(N)))
3600 if N<10^111 then print "siever: 12e":doscmd "nfs4I12e -a POLY1.JOB -o r0.re1":goto 3650
3610 if N<10^137 then print "siever: 13e":doscmd "nfs4I13e -a POLY1.JOB -o r0.re1":goto 3650
3620 if N<10^160 then print "siever: 14e":print "This factorization will take several weeks or even months!":doscmd "nfs4I14e -a POLY1.JOB -o r0.re1":goto 3650
3630 if N<10^200 then print "siever: 15e":print "Warning: This factorization will take several years!!":doscmd "nfs4I15e -a POLY1.JOB -o r0.re1":goto 3650
3640 print "siever: 16e":print "Warning: This factorization WILL take several decades!!"
3645 doscmd "nfs4I16e.exe -a poly1.job -o r0.rel":goto 3650 'c200 anyone ??!!?? *gg*
3650 if exist("relation.rel") then doscmd "rename relation.rel r1.re1"
3660 doscmd "copy *.re1 relation.rel" 'concatenate relation output files
3670 kill "r0.re1":kill "r1.re1"
[/code]

[QUOTE=henryzz;164201]i added cat.exe and it is no different
looking at the code it seems to be using copy not cat
[code] 3590 f=cutspc(str(q)):print "sieving: i=";i;", q0= ";q;", special Q range size: ";qintsize:print "starting siever":print "input: C";cutspc(str(alen(N)))
3600 if N<10^111 then print "siever: 12e":doscmd "nfs4I12e -a POLY1.JOB -o r0.re1":goto 3650
3610 if N<10^137 then print "siever: 13e":doscmd "nfs4I13e -a POLY1.JOB -o r0.re1":goto 3650
3620 if N<10^160 then print "siever: 14e":print "This factorization will take several weeks or even months!":doscmd "nfs4I14e -a POLY1.JOB -o r0.re1":goto 3650
3630 if N<10^200 then print "siever: 15e":print "Warning: This factorization will take several years!!":doscmd "nfs4I15e -a POLY1.JOB -o r0.re1":goto 3650
3640 print "siever: 16e":print "Warning: This factorization WILL take several decades!!"
3645 doscmd "nfs4I16e.exe -a poly1.job -o r0.rel":goto 3650 'c200 anyone ??!!?? *gg*
3650 if exist("relation.rel") then doscmd "rename relation.rel r1.re1"
3660 doscmd "copy *.re1 relation.rel" 'concatenate relation output files
3670 kill "r0.re1":kill "r1.re1"
[/code][/QUOTE]

Do you have msieve.exe (version 1.39(!)) in the directory?

Do you have renamed gnfs-lasieve4I1?e.exe to nfs4I1?e.exe? - these files have also to be in the directory where you have the gnfs.ub script.

you will also need grep.exe. (sorry, I mismatched cat.exe and grep.exe in my posting above. The file you need is grep.exe.)

I found a bug in resuming: when I resumed the script (with resume.txt present), it ran msieve, waited a bit, ran msieve again with no more relations than last time, and then started sieving not from the special q in resume.txt (1073537), but from that one + 50000 (1123537). It seems as if the script thinks another range of 50000 (1073537-1123537) has been sieved before it runsmsiev the second time.

[QUOTE=10metreh;164231]I found a bug in resuming: when I resumed the script (with resume.txt present), it ran msieve, waited a bit, ran msieve again with no more relations than last time, and then started sieving not from the special q in resume.txt (1073537), but from that one + 50000 (1123537). It seems as if the script thinks another range of 50000 (1073537-1123537) has been sieved before it runsmsiev the second time.[/QUOTE]

This happens when you have got a (small) relations file still sitting in your folder. After running msieve to determine how many relations are still needed, it finds that the output file from the siever already exists, merges it with the large relations file and runs msieve again. (you now should have slightly (!) more relations.)

Workaround: you can either delete the small relations file, or just ignore the bug. It only costs a few minutes while running msieve a second time, and then it will finish the factorization anyway.

[quote=Andi47;164236]This happens when you have got a (small) relations file still sitting in your folder. After running msieve to determine how many relations are still needed, it finds that the output file from the siever already exists, merges it with the large relations file and runs msieve again. (you now should have slightly (!) more relations.)

Workaround: you can either delete the small relations file, or just ignore the bug. It only costs a few minutes while running msieve a second time, and then it will finish the factorization anyway.[/quote]

The odd thing is that it starts from a q that is 50000 (qintsize) larger. Larger q's find relations more slowly (q=1000000 is ~8% slower than q=600000 for this C97). In fact, I was wondering whether you could change the starting q-values to fit in better with def-par.txt.

I won't be back here till late tomorrow, and probably won't get a chance to check till Monday, so there's no rush.

[QUOTE=10metreh;164237]The odd thing is that it starts from a q that is 50000 (qintsize) larger. Larger q's find relations more slowly (q=1000000 is ~8% slower than q=600000 for this C97). In fact, I was wondering whether you could change the starting q-values to fit in better with def-par.txt.

I won't be back here till late tomorrow, and probably won't get a chance to check till Monday, so there's no rush.[/QUOTE]

I have also run into this bug a few times, but currently my free time is very limited (I have got a few talks and business trips in the next weeks), so I don't think that I can fix the bug / tweak the starting q values before ~march 20th. Sorry.

When I'm back on Monday, I might check the script and try to find the bug. Don't be surprised if I post new versions of the script before 20th March.

[QUOTE=10metreh;164241]When I'm back on Monday, I might check the script and try to find the bug. Don't be surprised if I post new versions of the script before 20th March.[/QUOTE]

I think it should suffice to check if the r0.rel file exists, and if yes, merge it into the relation.rel file (by doscmd "copy *.rel relation.rel":kill "r0.rel") before starting msieve. (maybe I have time to do the changes tomorrow before I have to go to the airport.)

[quote=Andi47;164248]I think it should suffice to check if the r0.rel file exists, and if yes, merge it into the relation.rel file (by doscmd "copy *.rel relation.rel":kill "r0.rel") before starting msieve. (maybe I have time to do the changes tomorrow before I have to go to the airport.)[/quote]

Just to clarify, I won't try again until I get another GNFS, because I'm now using factMsieve.pl on the C97. I might try to add SNFS support to the script and include test-sieving for numbers above ~C115 (Andi47, what do you think would be the optimal cutoff here?)

[quote=Andi47;164204]Do you have msieve.exe (version 1.39(!)) in the directory?

Do you have renamed gnfs-lasieve4I1?e.exe to nfs4I1?e.exe? - these files have also to be in the directory where you have the gnfs.ub script.

you will also need grep.exe. (sorry, I mismatched cat.exe and grep.exe in my posting above. The file you need is grep.exe.)[/quote]
here is the output of "dir *.exe"
[code]
24/01/2008 20:29 46,592 cat.exe
27/08/2008 15:46 1,902,514 ecm.exe
14/04/2003 01:00 80,412 grep.exe
22/02/2009 17:16 774,144 msieve.exe
13/05/2006 02:05 225,792 nfs4I12e.exe
13/05/2006 02:05 225,792 nfs4I13e.exe
13/05/2006 02:05 225,792 nfs4I14e.exe
07/10/2000 01:00 126,192 UBIBM32.EXE[/code]
is that all i need or was i trying to be too clever by not including ggnfs poly selection and postprocessing tools?

has anyone had this script working on vista? it would be just like Microsoft to change the functionality of an old command like copy

[quote=henryzz;164252]here is the output of "dir *.exe"
[code]
24/01/2008 20:29 46,592 cat.exe
27/08/2008 15:46 1,902,514 ecm.exe
14/04/2003 01:00 80,412 grep.exe
22/02/2009 17:16 774,144 msieve.exe
13/05/2006 02:05 225,792 nfs4I12e.exe
13/05/2006 02:05 225,792 nfs4I13e.exe
13/05/2006 02:05 225,792 nfs4I14e.exe
07/10/2000 01:00 126,192 UBIBM32.EXE[/code]is that all i need or was i trying to be too clever by not including ggnfs poly selection and postprocessing tools?

has anyone had this script working on vista? it would be just like Microsoft to change the functionality of an old command like copy[/quote]

That looks fine, I can't understand why copy doesn't work. I suggest you (Andi47) change copy to cat if you have time, otherwise I will do it myself on Monday and post the new version.

I don't have access to any Vista machines ATM (although where I currently am I have access to a C2D and have used it to complete the near-repdigit C90), so I can't check. (Vista is so annoying sometimes, isn't it?)

[QUOTE=10metreh;164253]That looks fine, I can't understand why copy doesn't work. I suggest you (Andi47) change copy to cat if you have time, otherwise I will do it myself on Monday and post the new version.[/quote]

Why including something that requires yet another additional program? (not everybody has got cat.exe)

Version 1.07
 

Version 1.07 is available.

- (hopefully) fixed a bug which causes msieve to be started twice and a q range of 50000 to be skipped when a factorization is resumed.

[quote=Andi47;164256]Why including something that requires yet another additional program? (not everybody has got cat.exe)[/quote]
i agree it would be pointless to add cat.exe into the main program currently but i suspect that it might solve my problem so i will impliment it in my version of the script to see if that fixes it
it should be a 5 minute job but dont bother doing it yourself i will do it
edit: did it in about 1 min
now testing

[quote=Andi47;164256]Why including something that requires yet another additional program? (not everybody has got cat.exe)[/quote]

I'm very sorry about the insult(?). :sad:

[QUOTE=10metreh;164260]I'm very sorry about the insult(?). :sad:[/QUOTE]

I don't see it as an insult - I just asked why you want to use cat.exe as it's yet another additional program.

i see in the original script that sometimes the extension is .re1 and othertimes .rel
the difference between 1 and l is not much and it is rather confusing
i think that that difference may have created a bug in the original code
i just dont get how it hasnt affected anyone else
i will fix the bug this caused me to write tomorrow

this reminded me of [URL]http://www.kevinwilliampang.com/post/Top-10-Things-That-Annoy-Programmers.aspx[/URL] although i cant find it on the list now

[QUOTE=henryzz;164264]i see in the original script that sometimes the extension is .re1 and othertimes .rel
the difference between 1 and l is not much and it is rather confusing
i think that that difference may have created a bug in the original code
i just dont get how it hasnt affected anyone else
i will fix the bug this caused me to write tomorrow

this reminded me of [URL]http://www.kevinwilliampang.com/post/Top-10-Things-That-Annoy-Programmers.aspx[/URL] although i cant find it on the list now[/QUOTE]

On which point of the factorization are you now?

When sieving is done, you should have the following files in your directory:

msieve.fb - contains the polynomial in msieve format.
poly1.job - this holds your polynomial
.last_spq0 - contains the highest Q which was sieved.
relation.rel - contains all your relations
msieve.log - msieve's logfile (the last lines either hold the factors or say something like "filtering wants 200000 more relations"). It is possible that this one has already been renamed to msieve.old.
_0.rel - contains the line "N <number to factor>". msieve needs this as first line in msieve.dat
msieve.dat - holds the aforementioned first line and all relations
possibly r0.re1 and r1.re1 - these contains the relations which are not yet merged into relation.rel.

btw: the difference between .re1 and rel is INTENDED (you can rename it to .re2 or something in the code if you want) for NOT accidentally merging ".rel" files when processing "*.re1".

I think your run has failed because grep.exe did not exist and therefore you did not get your "wantrel.txt" and "numofrel.txt" files in lines 5030 and 5080. Without this files, re becomes zero in line 5120, followed by r1=0 in line 5200, thus causing a division by zero in line 5220.

You can try to resume your factorization by renaming .last_spq0 to resume.txt. This forces the program to start msieve.exe again for postprocessing. When msieve.exe is finished, it either knows how many more relations are needed and continues sieving (if grep.exe is started correctly), or gets the factors.
If it crashes again, the first crash (with grep.exe missing) could have screwed up a few things, in this case you might need to restart the factorization from scratch. (in this case, delete (or move to another directory) all *.rel, *.re1 files, as well as msieve.dat, msieve.log and - if you want to do a new poly search - also msieve.fb before starting gnfs.ub.)

[QUOTE=Andi47;164257]Version 1.07 is available.

- (hopefully) fixed a bug which causes msieve to be started twice and a q range of 50000 to be skipped when a factorization is resumed.[/QUOTE]

Hmmmm... something happens so that it now doesn't start postprocessing properly when resuming? You should stick with version 1.06b, I have to look into the bug somewhat closer when I'm back from my business trip.

[quote=10metreh;164253]That looks fine, I can't understand why copy doesn't work.[/quote]

Well, copy is an internal command of the shell, so it probably needs to be run with "cmd /c copy ..."

now that i have sorted out the 1 and l problem it seems to be working properly with my cat.exe version
i dont understand why it is not working with the original version