yafu bugs

[jwes]

I downloaded yafu 1.30 and started playing with it and had some problems. I am using Windows 7 professional 64 bit with 4Gb memory. The info from yafu is:

03/28/12 22:40:02 v1.30 @ WIN7, System/Build Info:
Using GMP-ECM 6.3, Powered by GMP 5.0.1
detected Intel(R) Core(TM)2 Duo CPU     E7500  @ 2.93GHz
detected L1 = 32768 bytes, L2 = 3145728 bytes, CL = 64 bytes
measured cpu frequency ~= 2909.877190

===============================================================
======= Welcome to YAFU (Yet Another Factoring Utility) =======
=======             bbuhrow@gmail.com                   =======
=======     Type help at any time, or quit to quit      =======
===============================================================
cached 78498 primes. pmax = 999983

1. If I type yafu "factor(2^3481-1)" at a command prompt, yafu crashes.
Here is the console output:

C:\projects\primes\2npm1>yafu "factor(2^3481-1)"


factoring 768094943911784828733350005255450486035890329238046754610312148020377461818175070860684817318549980398705212392823972941688620626849018287
0080858684634273938283965290831230473428281015361165391710997977723689297059879275164879924696767509172069551521071810619505734977824102967451952022
7824234110799990874398478872097251998619850741350705015014514635013839921270499861443731217405421915598498235862704688233586431535561669685163533009
9725637933236625531945549908440253399369233498924273132799249502013188878182916711100274895543940430217695172661422015012662312574324645441952059909
9936751689237441069865518355017389005512225015124058544203350556785828733977484184256695647631563677891104436800689263451521932981074932863437529175
8609671192841663540505877844262010187446312897821552475934254774944697590836454500913017187872423314134956224515455121468900207913510270380009253710
5041766687594391583830953037052083103691532252397781412741059800520551103663658547552897229716526721900908140757914032980505391254869669853652482761
3824608541628906340351
using pretesting plan: normal
no tune info: using qs/gnfs crossover of 95 digits

div: primes less than 10000
fmt: 1000000 iterations
rho: x^2 + 3, starting 1000 iterations on C1048
rho: x^2 + 2, starting 1000 iterations on C1048
rho: x^2 + 2, starting 1000 iterations on C1043
rho: x^2 + 1, starting 1000 iterations on C1043
pp1: starting B1 = 20K, B2 = gmp-ecm default on C1043
pp1: starting B1 = 20K, B2 = gmp-ecm default on C1043
pp1: starting B1 = 20K, B2 = gmp-ecm default on C1043
pm1: starting B1 = 100K, B2 = gmp-ecm default on C1043
Total factoring time = 9.3205 seconds


***factors found***

P6 = 179951
PRP13 = 3203431780337
PRP1031 = 133243233098286206425895905655339230814837821503707042176728868851627564995597455158205050253666332917826898249705082029329811774808589339
8944316191443786022382948648149820127180616071021241931998164759176647122154977879124908142883823968728235032844711606733373321265364476861448241851
9392989453221962115799024522405104498901459713737808685662443413595655349375239048341550958241450638814760944590236658374229179290977642222726256754
3179850490149256942534759589116259499832489279437323254615840577364392180507537009327735082999407977606521822261289761231049892512560670369903788503
3768615607108249423917666486392293597721002744284183199020388590973842366686307278274822732832868229485451903372732813652178253170030841169780438395
4107548151069972793277926158786752065849297036891260767326465784518800758457811377420171439984071715181951117763117140248357060929148011779659503510
7421423184033544329451581741498912281018605502957101488306481331893368553116822871216805075787185149242291912664471879406452671148265107222936064591
13473

ans = 1

Windbg gives the address as:
00000000`00408bcf e86c450000 call yafu+0xd140 (00000000`0040d140)

and the call stack is:
ntdll!RtlUnhandledExceptionFilter+0x2d2
ntdll!EtwEnumerateProcessRegGuids+0x216
ntdll!RtlQueryProcessLockInformation+0x972
ntdll!RtlLogStackBackTrace+0x444
ntdll!RtlIsDosDeviceName_U+0x7afb
ntdll!RtlAllocateHeap+0xd9d
msvcrt!free+0x1c
yafu+0x8bd4

2. I generate a batch file with the following awk code:
BEGIN {
for (i=1;i<10001;i++)
printf("2^%d-1\n",i)
}

and run it with the command:
yafu "factor(@)" -batchfile 2npm1.txt -pretest -noecm
and it exits after a few hundred numbers. The last few lines of output are:

=== Starting work on batchfile expression ===
factor(2^452-1)
=============================================
factoring 11629419588729710248789180926208072549658261770997088964503843186890228609814366773219056811420217048972200345700258846936553626057834495
using pretesting plan: normal
no tune info: using qs/gnfs crossover of 95 digits

div: primes less than 10000
fmt: 1000000 iterations
could not open factor.log for writing
could not open factor.log for writing
could not open factor.log for writing
03/28/12 22:34:50 v1.30 @ WIN7, final ECM pretested depth: 0.00
03/28/12 22:34:50 v1.30 @ WIN7, c130 cofactor = 1007194009601273323814241024653067790628147304582016486112183731306566324161552868694844114131274939
058447479373383102021075363269
Total factoring time = 0.0040 seconds
Could not open factor.log for appending


***factors found***

P1 = 3
P1 = 5
P3 = 227
P4 = 3391
C130 = 1007194009601273323814241024653067790628147304582016486112183731306566324161552868694844114131274939058447479373383102021075363269

ans = 1007194009601273323814241024653067790628147304582016486112183731306566324161552868694844114131274939058447479373383102021075363269

couldn't open 2npm1.txt for reading

Deleting factor.log does not help. I have plenty of free disk space. Let me know if there is any more information that will help you debug this.

[Dubslow]

In future posts, please use the [/code] tags to paste stuff from the prompt, it makes your post easier to read. (Also while I am generally ignorant in this prog or its math, the first example does not appear to have crashed, the output is generally as I would expect.)

[bsquared]

The crash happens because in several places I haven't checked that the length of a string is sufficient to hold the number being printed to it. For whatever reason, this is non-fatal until at the end of the program when I go to free those strings. Thanks for the bug report.

As for the read/write issues, I have no idea what's going on. It's running on my Win7 system right now with no issues (at about n=1600 or so now). Maybe your system is buffering writes and yafu is trying to open the file before all of the last iteration's output has been flushed. Is this a consistent error? Meaning, does it always happen if you were to rebuild the batchfile and try again? Does it always happen in the same place of the batchfile?

[jwes]

Originally Posted by bsquared

The crash happens because in several places I haven't checked that the length of a string is sufficient to hold the number being printed to it. For whatever reason, this is non-fatal until at the end of the program when I go to free those strings. Thanks for the bug report.

Okay. The problem is that it aborts batch files. My interest is in numbers of the form 2^n-1 which have a large number of small prime factors, so I would like to be able to attempt to factor much larger numbers than most people would.

The problem appears to occur when there are large probable primes or composites in the output. C945 works, but C1028 fails.

Originally Posted by bsquared

As for the read/write issues, I have no idea what's going on. It's running on my Win7 system right now with no issues (at about n=1600 or so now). Maybe your system is buffering writes and yafu is trying to open the file before all of the last iteration's output has been flushed. Is this a consistent error? Meaning, does it always happen if you were to rebuild the batchfile and try again? Does it always happen in the same place of the batchfile?

It always happens on one machine at approximately but not exactly the same place. It does not happen on my laptop running windows 7 home 64 bit. If I have the energy, I'll try compiling yafu and investigating this myself.

[bsquared]

Originally Posted by jwes

Okay. The problem is that it aborts batch files. My interest is in numbers of the form 2^n-1 which have a large number of small prime factors, so I would like to be able to attempt to factor much larger numbers than most people would.

The problem appears to occur when there are large probable primes or composites in the output. C945 works, but C1028 fails.

The magic number in this case is 1024. Any single number with more than that many characters would have this issue. It is now fixed in my development version, so the fix will be available soon via SVN and a bit later when I release 1.31.

Originally Posted by jwes

It always happens on one machine at approximately but not exactly the same place. It does not happen on my laptop running windows 7 home 64 bit. If I have the energy, I'll try compiling yafu and investigating this myself.

If I find the time I'll add strerror(errno) statements after logfile I/O commands to see if any helpful information is produced. That won't be useful to you in the near term, but without a test case that I have access to I don't know how else I can help right now.

If you need help compiling let me know (maybe via PM).

[Dubslow]

http://www.mersenneforum.org/showthread.php?p=294811

From post 6, I took the first number that is prime and attempted to factor N-1.

bill@Gravemind:~∰∂ yafu "factor(8100^1024+203^1024-1)"


factoring 1943834705157593059302663727746432712326695858603836993782308125422445327863025249788937271555460559328238115987209415859509526806740296881992205806055182223874111216518437416856484254737744171230471899255739303903806865079018166244661850180723781565996718779403303280350003573238377928396295245701994112631741128854729834839309849255426056127099710942518731529668300091805245462563884980127596148696598445394397309180201313090202248006400958234487323546567430302332139077980498685773519224640951239685972564333124100456536335644757042111505241146301071089582160999011658100234216229922577186956901752014577264795922358768092327806339642093318294849351131564171857975504443744143517574085984286005360741016501236102093120295664876746306640246787345406722182756296906858620830938721245651579919820766619910027294502420501253637423988547596862088234037514520797404625046204912637656052729044913013144004978890146259930486687320574096501011013913254131434576487618958144073740810641885569723777215039725900120261013064376352263117806238006011859387097159516851525470873343452294437544900476909455372396622738781811295176313279228136817869636169998300609711186929658618461448382071000521222307664964064868045316881705521912140813763906889801330096424187365303119675706725626949498458428861903895249484089058503503779993946720876935625997035091101328905084855224853163777237863097486135149603125249700962656334189592539341789672136139760797516796529626022876525201905369267953011881176629969256383439939725517864180498166239860619871340773666647604132496793419443633900740456933265158464309219998529961048618387256472831138975213954232195048943220146031595819467578351907446286425937341763777370041897571375342275650714939631633976863224377915813658693108508801042023430708046465345216073616289499276569579095294929804904732053184703040351504918867099645362862701479597535990515863115264384946944093394579863105729886348793069078155221160601805953411951025164349715988571971439484344927130959547736681498451372956562501550722338683550607717414673682424684157033382353991558007270307589264967198633518121872151969544958468926718194618212850366666563637210433728726063514910597360291229213052751710884209050333161815913435347778934235233563263544724665289382951561766660199072410481613750410443088952018865656712783438409498252323912414959552414099580781140453161503194451178202039635309658557918329096393168498475336350367603728267343998164315047125116590781393922185111282190150661491425369484319380403830819738394155061076185689772020682088093723319758750388162523212899783751027245139030899244982249553927001194304809224965227079526281048105773450912501192240899551830660376582853737121251239735858528086117990290596653270111866141345735130392912831836212899841854723283083317463997155959632453086631586715218903616593515621460870421539017409377209338600592074952239176816134235170694661979195658078021005374806294207544784532431226470186268672251017007524622545887987783620707258120378113172573808849445743518992266531490442790192038128803123014188821893139083124004272321134858124317310255368879202083329771580239817114856614763811839410135002692290249968395054652017087909828671728224095005974063146577308053716434004024381656759700271291185605938869377959153430126823683949423275575992677337885408999642240679170023817466948017817538570864008248188568374241320587103891123644942300576644098740031762894777288884588745654587260172550315518511068605892679003957333353517244303172826618576992031690645833276894392657401844538359829101209551217385586178655635567822267152037436224702773864002750982873149695734999261012214288173433442956521993697446963906431434530635135929761073907390874279898396235139725385818021299785544373962443831855985688658494830590047214441920281257505809418348690421503281070110948836614152531301441040022244334518120563239022989736574886573612592477468188407216223034202858258700326687484460450718662067083093484213654087639296040337553967175539881950573203969596403272365486080
using pretesting plan: normal
no tune info: using qs/gnfs crossover of 95 digits

div: primes less than 10000
fmt: 1000000 iterations
could not open 7909828671728224095005974063146577308053716434004024381656759700271291185605938869377959153430126823683949423275575992677337885408999642240679170023817466948017817538570864008248188568374241320587103891123644942300576644098740031762894777288884588745654587260172550315518511068605892679003957333353517244303172826618576992031690645833276894392657401844538359829101209551217385586178655635567822267152037436224702773864002750982873149695734999261012214288173433442956521993697446963906431434530635135929761073907390874279898396235139725385818021299785544373962443831855985688658494830590047214441920281257505809418348690421503281070110948836614152531301441040022244334518120563239022989736574886573612592477468188407216223034202858258700326687484460450718662067083093484213654087639296040337553967175539881950573203969596403272365486080 for writing
could not open 7909828671728224095005974063146577308053716434004024381656759700271291185605938869377959153430126823683949423275575992677337885408999642240679170023817466948017817538570864008248188568374241320587103891123644942300576644098740031762894777288884588745654587260172550315518511068605892679003957333353517244303172826618576992031690645833276894392657401844538359829101209551217385586178655635567822267152037436224702773864002750982873149695734999261012214288173433442956521993697446963906431434530635135929761073907390874279898396235139725385818021299785544373962443831855985688658494830590047214441920281257505809418348690421503281070110948836614152531301441040022244334518120563239022989736574886573612592477468188407216223034202858258700326687484460450718662067083093484213654087639296040337553967175539881950573203969596403272365486080 for writing
could not open 7909828671728224095005974063146577308053716434004024381656759700271291185605938869377959153430126823683949423275575992677337885408999642240679170023817466948017817538570864008248188568374241320587103891123644942300576644098740031762894777288884588745654587260172550315518511068605892679003957333353517244303172826618576992031690645833276894392657401844538359829101209551217385586178655635567822267152037436224702773864002750982873149695734999261012214288173433442956521993697446963906431434530635135929761073907390874279898396235139725385818021299785544373962443831855985688658494830590047214441920281257505809418348690421503281070110948836614152531301441040022244334518120563239022989736574886573612592477468188407216223034202858258700326687484460450718662067083093484213654087639296040337553967175539881950573203969596403272365486080 for writing
03/30/12 13:58:56 v1.30 @ Gravemind, current ECM pretesting depth: 0.00
03/30/12 13:58:56 v1.30 @ Gravemind, scheduled 30 curves at B1=2000 toward target pretesting depth of 1229.54
Segmentation fault
bill@Gravemind:~∰∂

Is there some sort of limit on the size of numbers that yafu can handle? Is it something about bash or gnome-terminal, i.e. would a file work better?

[bsquared]

Originally Posted by Dubslow

Is there some sort of limit on the size of numbers that yafu can handle? Is it something about bash or gnome-terminal, i.e. would a file work better?

Yes, this is the same problem as 1.) in the OP. I've fixed it in my development version, but the fix is not otherwise available (yet).

Proof:

###### 272 % yafu "factor(8100^1024+203^1024-1)"
 
factoring 1943834705157593059302663727746432712326695858603836993782308125422445327863025249788937271555460559328238115987209415859509526806740296881992205806055182223874111216518437416856484254737744171230471899255739303903806865079018166244661850180723781565996718779403303280350003573238377928396295245701994112631741128854729834839309849255426056127099710942518731529668300091805245462563884980127596148696598445394397309180201313090202248006400958234487323546567430302332139077980498685773519224640951239685972564333124100456536335644757042111505241146301071089582160999011658100234216229922577186956901752014577264795922358768092327806339642093318294849351131564171857975504443744143517574085984286005360741016501236102093120295664876746306640246787345406722182756296906858620830938721245651579919820766619910027294502420501253637423988547596862088234037514520797404625046204912637656052729044913013144004978890146259930486687320574096501011013913254131434576487618958144073740810641885569723777215039725900120261013064376352263117806238006011859387097159516851525470873343452294437544900476909455372396622738781811295176313279228136817869636169998300609711186929658618461448382071000521222307664964064868045316881705521912140813763906889801330096424187365303119675706725626949498458428861903895249484089058503503779993946720876935625997035091101328905084855224853163777237863097486135149603125249700962656334189592539341789672136139760797516796529626022876525201905369267953011881176629969256383439939725517864180498166239860619871340773666647604132496793419443633900740456933265158464309219998529961048618387256472831138975213954232195048943220146031595819467578351907446286425937341763777370041897571375342275650714939631633976863224377915813658693108508801042023430708046465345216073616289499276569579095294929804904732053184703040351504918867099645362862701479597535990515863115264384946944093394579863105729886348793069078155221160601805953411951025164349715988571971439484344927130959547736681498451372956562501550722338683550607717414673682424684157033382353991558007270307589264967198633518121872151969544958468926718194618212850366666563637210433728726063514910597360291229213052751710884209050333161815913435347778934235233563263544724665289382951561766660199072410481613750410443088952018865656712783438409498252323912414959552414099580781140453161503194451178202039635309658557918329096393168498475336350367603728267343998164315047125116590781393922185111282190150661491425369484319380403830819738394155061076185689772020682088093723319758750388162523212899783751027245139030899244982249553927001194304809224965227079526281048105773450912501192240899551830660376582853737121251239735858528086117990290596653270111866141345735130392912831836212899841854723283083317463997155959632453086631586715218903616593515621460870421539017409377209338600592074952239176816134235170694661979195658078021005374806294207544784532431226470186268672251017007524622545887987783620707258120378113172573808849445743518992266531490442790192038128803123014188821893139083124004272321134858124317310255368879202083329771580239817114856614763811839410135002692290249968395054652017087909828671728224095005974063146577308053716434004024381656759700271291185605938869377959153430126823683949423275575992677337885408999642240679170023817466948017817538570864008248188568374241320587103891123644942300576644098740031762894777288884588745654587260172550315518511068605892679003957333353517244303172826618576992031690645833276894392657401844538359829101209551217385586178655635567822267152037436224702773864002750982873149695734999261012214288173433442956521993697446963906431434530635135929761073907390874279898396235139725385818021299785544373962443831855985688658494830590047214441920281257505809418348690421503281070110948836614152531301441040022244334518120563239022989736574886573612592477468188407216223034202858258700326687484460450718662067083093484213654087639296040337553967175539881950573203969596403272365486080
using pretesting plan: normal
using tune info for qs/gnfs crossover
div: primes less than 10000
fmt: 1000000 iterations
rho: x^2 + 3, starting 1000 iterations on C3996
rho: x^2 + 2, starting 1000 iterations on C3996
rho: x^2 + 2, starting 1000 iterations on C3990
rho: x^2 + 1, starting 1000 iterations on C3990
pm1: starting B1 = 150K, B2 = gmp-ecm default on C3990
ecm: 30/30 curves on C3965 input, at B1 = 2K, B2 = gmp-ecm default
ecm: 1/74 curves on C3965 input, at B1 = 11K, B2 = gmp-ecm default
Aborting...                                                        ecm: 2/74 curves on C3965 input, at B1 = 11K, B2 = gmp-ecm default
***factors found***
P1 = 2
P1 = 2
P1 = 2
P1 = 2
P1 = 2
P1 = 2
P1 = 2
P1 = 2
P1 = 2
P1 = 2
P1 = 2
P1 = 2
P1 = 3
P1 = 5
P1 = 7
P2 = 11
P6 = 657581
C26 = 40937121317417566739710613
***co-factor***
C3965 = <snip>

[Dubslow]

nfs: commencing gnfs on c101: 73106581874831660596680279477902977438719392032450257045813575738299052122934033037321533121218727271

elapsed time of 1152.0187 seconds exceeds 1414 second deadline; poly select done

... last time I checked, 1152 < 1414 . Am I somehow misinterpreting this?

[Dubslow]

I just resumed a SIQS job; at first rels/sec was in the 600K; then it was 100K; then 60K; then 40K, and now it's down under 10K. (100K total rels needed.) I think it estimated rels/sec on total rels found but only divided by time since resume. Not a bug that affects results, but still.

[bsquared]

Originally Posted by Dubslow

nfs: commencing gnfs on c101: 73106581874831660596680279477902977438719392032450257045813575738299052122934033037321533121218727271

elapsed time of 1152.0187 seconds exceeds 1414 second deadline; poly select done

... last time I checked, 1152 < 1414 . Am I somehow misinterpreting this?

Err, no, 1152 is in fact less than 1414. I think I stop if the projected time for the next interval would exceed the deadline.

[Dubslow]

...seg fault, but this time SIQS is causing it.
The first time happened right at the end of sieving, the next two times at the beginning of sieving.

bill@Gravemind:~∰∂ yafu "factor(1524606106882304934687221077096878544309490889973271426793109857591080721691)"


factoring 1524606106882304934687221077096878544309490889973271426793109857591080721691
using pretesting plan: normal
no tune info: using qs/gnfs crossover of 95 digits

div: primes less than 10000
fmt: 1000000 iterations
pp1: starting B1 = 20K, B2 = gmp-ecm default on C76
pp1: starting B1 = 20K, B2 = gmp-ecm default on C76
pp1: starting B1 = 20K, B2 = gmp-ecm default on C76
pm1: starting B1 = 100K, B2 = gmp-ecm default on C76
ecm: 2/30 curves on C76 input, at B1 = 2K, B2 = gmp-ecm default
ecm: 27/27 curves on C61 input, at B1 = 2K, B2 = gmp-ecm default
ecm: 55/55 curves on C61 input, at B1 = 11K, B2 = gmp-ecm default

starting SIQS on c61: 1320987068432694544179216445038930121106664117447303316806953

==== sieving in progress (1 thread):    3888 relations needed ====
====           Press ctrl-c to abort and save state           ====
3765 rels found: 1917 full + 1848 from 17632 partial, (4740.33 rels/sec)

Segmentation fault
bill@Gravemind:~∰∂ yafu "factor(1524606106882304934687221077096878544309490889973271426793109857591080721691)"


factoring 1524606106882304934687221077096878544309490889973271426793109857591080721691
using pretesting plan: normal
no tune info: using qs/gnfs crossover of 95 digits

div: primes less than 10000
fmt: 1000000 iterations
pp1: starting B1 = 20K, B2 = gmp-ecm default on C76
pp1: starting B1 = 20K, B2 = gmp-ecm default on C76
pp1: starting B1 = 20K, B2 = gmp-ecm default on C76
pm1: starting B1 = 100K, B2 = gmp-ecm default on C76
ecm: 30/30 curves on C76 input, at B1 = 2K, B2 = gmp-ecm default
ecm: 3/74 curves on C76 input, at B1 = 11K, B2 = gmp-ecm default
ecm: 55/55 curves on C61 input, at B1 = 11K, B2 = gmp-ecm default

starting SIQS on c61: 1320987068432694544179216445038930121106664117447303316806953

==== sieving in progress (1 thread):    3888 relations needed ====
====           Press ctrl-c to abort and save state           ====


Segmentation fault
bill@Gravemind:~∰∂ yafu "factor(1524606106882304934687221077096878544309490889973271426793109857591080721691)"


factoring 1524606106882304934687221077096878544309490889973271426793109857591080721691
using pretesting plan: normal
no tune info: using qs/gnfs crossover of 95 digits

div: primes less than 10000
fmt: 1000000 iterations
pp1: starting B1 = 20K, B2 = gmp-ecm default on C76
pp1: starting B1 = 20K, B2 = gmp-ecm default on C76
pp1: starting B1 = 20K, B2 = gmp-ecm default on C76
pm1: starting B1 = 100K, B2 = gmp-ecm default on C76
ecm: 30/30 curves on C76 input, at B1 = 2K, B2 = gmp-ecm default
ecm: 5/74 curves on C76 input, at B1 = 11K, B2 = gmp-ecm default
ecm: 55/55 curves on C61 input, at B1 = 11K, B2 = gmp-ecm default

starting SIQS on c61: 1320987068432694544179216445038930121106664117447303316806953

==== sieving in progress (1 thread):    3888 relations needed ====
====           Press ctrl-c to abort and save state           ====


Segmentation fault
bill@Gravemind:~∰∂

I guess the newbies do best at breaking things :P
Edit: Another SIQS job was running at the time, and when it finished sieving, it gave a warning about a bad poly in the save file, and then seg faulted. Is it not possible to run multiple SIQS jobs at once?