Python Driver for GGNFS and MSIEVE - Page 54

EdH · 2011-05-21, 00:57

Well, further investigation has turned up something disappointing. My test.log file on the winXP machine is actually 8.3GB!! Rather large to read. I stopped the process on my other machine when its log file got to over 700MB. It looks like this:

Code:

Fri May 20 19:56:45 2011  
Fri May 20 19:56:45 2011  
Fri May 20 19:56:45 2011  Msieve v. 1.49 (SVN 573)
Fri May 20 19:56:45 2011  random seeds: 4e72628f 370912f0
Fri May 20 19:56:45 2011  factoring 8845424710899977815163938063336156710467852144650354456276554838704070938061544223956879363372317220791203448437149670370751897 (127 digits)
Fri May 20 19:56:49 2011  searching for 15-digit factors
Fri May 20 19:56:54 2011  commencing number field sieve (127-digit input)
Fri May 20 19:56:54 2011  R0: -4533315346737024084409672
Fri May 20 19:56:54 2011  R1:  47067074301251
Fri May 20 19:56:54 2011  A0: -161787982576004228012954955972045
Fri May 20 19:56:54 2011  A1:  19917526473116113434318380374
Fri May 20 19:56:54 2011  A2: -10590829318541488172873
Fri May 20 19:56:54 2011  A3: -28808415395441874
Fri May 20 19:56:54 2011  A4: -3009877082
Fri May 20 19:56:54 2011  A5:  4620
Fri May 20 19:56:54 2011  skew 1338733.71, size 3.123e-12, alpha -8.167, combined = 1.125e-10 rroots = 3
Fri May 20 19:56:54 2011  
Fri May 20 19:56:54 2011  commencing relation filtering
Fri May 20 19:56:54 2011  estimated available RAM is 2011.3 MB
Fri May 20 19:56:54 2011  commencing duplicate removal, pass 1
Fri May 20 19:59:51 2011  error -11 reading relation 10203134
Fri May 20 19:59:51 2011  error -11 reading relation 10203135
...
Fri May 20 20:43:50 2011  error -11 reading relation 22571907
Fri May 20 20:43:50 2011  error -11 reading relation 22571908
Fri May 20 20:43:50 2011  found 768502 hash collisions in 10315287 relations

The last line was line number 12256643. At least this explains the "read 10M relations" part. But, now what?

Batalov · 2011-05-21, 01:34

It appears that you have 10315287 valid relations from this project and some 12M other, foreign relations (leftovers from another run? from another polynomial? ...etc). The latter 12M relation caused 12M error lines, but only valid relations were counted by msieve (and the progress 10M-spaced messages are based on their count).

It appears that your polynomial file was replaced (the valid relations are all in the first half of the file, followed by incompatible ones). Check this; and also check that the .fb file (which also has a poly) has the same poly. If it is not so, then you may sieve forever while the filtering will always throw away all new (incompatible) relations. Backup the whole project; trim the bad relations (or 12 million error lines will be printed every time you filter); restore the proper poly and/or .fb file and resume sieving.

NB: the siever only reads the .poly file (and doesn't care about any others), msieve reads .fb file, .ini file (for control and other purposes (and doesn't care about the .poly file); therefore, check the correspondence of these files, -- if they don't match, then your tools are not communicating and wissenschaft ist tot.

EdH · 2011-05-21, 04:15

Thanks! I checked the current .poly against the original and they were different. I transplanted the original for the current, but did not interrupt the script. Maybe it will work its way out with that simple swap. I may not be able to check it until tomorrow night. By then, there should be some progress or setback.

EdH · 2011-05-23, 01:17

OK, no go with any of my repair tests.

I've started a different winXP machine from scratch. It should take about a week to complete. If it still won't solve it, I guess I'll have to throw in the towel for now on these larger composites.

Thanks for all the help.

Hasgar · 2011-06-26, 13:18

hello guys, im a ggnfs noob and factored some small rsa numbers with jeffs guide. my question is: is there a command to test my own polynomials? i know that msieve gives me very good polynomials but i want to make my own tests.

Walter Nissen · 2011-09-03, 16:21

I've run factMsieve.py for 40 hours on a cmd.exe box on XP on a 1-core ,
2-thread Pentium 4 to factor a c114 .
Nice . Really nice .
Now I have some others I'd like to factor .
The least is a c127 .
Can I just follow the instructions in the "Beginners Guide" to factor a c127 ?
Is this something people do routinely ?
Or do I need to do more ?
Should I use NUM_CORES = 1 or NUM_CORES = 2 ?
( If 1 , can I do any useful factoring with the other thread ? )
Will it likely finish within 2 weeks ?
Should I use YAFU instead ?

Anyone who'd like to tell me where I can find answers to these questions among
the thousands of posts here will find me very grateful .

firejuggler · 2011-09-03, 17:29

a c127 is starting to be large for me .
wrell, to get an idea, the number of relation double when you add 6 digits. you are looking at 17 to 20M relation. add that the fact that the relation gathering slow down the higher the composite is and you are looking at 3 to 4 day of constant work on a 2 core. around 100 working hours.

edit found a file for a C121

Code:

Number: test
N = 5858364738523882066246616399915548077164762165145018768500632113602913413636994920984701984069996185148241678223850470857 (121 digits)
Divisors found:
r1=418285902605639683491374164206941880768796851763 (pp48)
r2=14005647099340934492958096845111000136052230794117070163943133764505886739 (pp74)
Version: Msieve v. 1.48
Total time: 27.15 hours.
Factorization parameters were as follows:
n: 5858364738523882066246616399915548077164762165145018768500632113602913413636994920984701984069996185148241678223850470857
Y0: -290002410832638919281206
Y1: 7500653629349
c0: 2518711711578997912832324085
c1: 787076055692069866619886
c2: -47558138715578552841
c3: -42030696799006
c4: 2583983660
c5: 2856
skew: 122189.71 
type: gnfs
Factor base limits: 4400000/4400000
Large primes per side: 3
Large prime bits: 27/27
Sieved algebraic special-q in [0, 0)
Total raw relations: 10547083
Relations: 1329674 relations
Pruned matrix : 756867 x 757092
Polynomial selection time: 5.87 hours.
Total sieving time: 19.35 hours.
Total relation processing time: 0.10 hours.
Matrix solve time: 1.68 hours.
time per square root: 0.16 hours.
Prototype def-par.txt line would be: gnfs,120,5,65,2000,1e-05,0.28,250,20,50000,3600,4400000,4400000,27,27,53,53,2.5,2.5,100000
total time: 27.15 hours.
x86 Family 6 Model 23 Stepping 6, GenuineIntel
Windows-XP-5.1.2600-SP3
processors: 2, speed: 2.83GHz

27 hours total, on a 2 core, meaning 49 hours

And to answer your question, C110-C120 are common, 120-130 are medium, 130-135 take up to a week and above... too hard for me to bother.

wblipp · 2011-09-03, 17:41

Quote:

Originally Posted by Walter Nissen

Now I have some others I'd like to factor .
The least is a c127 .

That's large enough that you want to be sure there isn't an SNFS alternative. If you are not familiar with that, tell us where the numbers come from and somebody here may be able to help.

Walter Nissen · 2011-09-03, 22:43

Thanks for responding.
Let np ( n ) = n^n + (n+1)^(n+1) .
c127 = np ( 79 ) / ( 547 * 1381 * 66269726871718249753 )
There's probably more than you wanted to know about np ( n ) at
the as yet unpublished :
http://upforthecount.com/math/nnp.html
There's a little known about the factors .
p | np ( 2p-2 )
Some larger np have been factored .
np ( 415 ) = 29 * p1089
np ( 802 ) splits into 11 factors including a p2320 .
( n*n + n + 1 ) / 3 | np ( n ) if 4 = n mod 6 ( divides twice ) .
p | np ( n ) for certain n mod (p(p-1)) ; e.g. , also
3 | np ( n ) if 4 = n mod 6 .
All p give rise to such families , e.g. , 5 | np ( n ) if 1 = n mod 20 or
if 8 = n mod 20 , where 20 = 5(5-1) .
If the word "certain" gives rise to an algorithm , then factoring might
be trivial .
I don't know how to map this onto SNFS , but I never discount genius .
The next largest ones I've noticed not yet factored by extensive ECM
are a c145 , a c147 and a c149 , for n = 87 , 83 and 96 .

fivemack · 2011-09-03, 23:15

79^79+80^80 = (79^4) * (79^15)^5 + (80^16)^5

so:

Code:

n: 3545747554330427459757047726394524919008341604708116681613612166055111769302473489038103286321807499348516053117524995279478089
skew: 33
c5: 1
c0: 38950081
Y0: 2814749767106560000000000000000
Y1: -29134419507545592909032289199
lpbr: 25
lpba: 25
mfbr: 54
mfba: 54
alambda: 2.6
rlambda: 2.6
alim: 4000000
rlim: 4000000

sieve with 13e from q=2e6 to q=4e6, it should take about 24 hours.

firejuggler · 2011-09-03, 23:36

Did you run a polyselect or did you calculate the poly by yourself? andd if you did it by yourself, can you explain it?
And Walter, once you get your factorisation (and the work get published), could you update http://factordb.com/
with your newfound factor?

2011-05-21, 01:34	#585
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2⁴·593 Posts	It appears that you have 10315287 valid relations from this project and some 12M other, foreign relations (leftovers from another run? from another polynomial? ...etc). The latter 12M relation caused 12M error lines, but only valid relations were counted by msieve (and the progress 10M-spaced messages are based on their count). It appears that your polynomial file was replaced (the valid relations are all in the first half of the file, followed by incompatible ones). Check this; and also check that the .fb file (which also has a poly) has the same poly. If it is not so, then you may sieve forever while the filtering will always throw away all new (incompatible) relations. Backup the whole project; trim the bad relations (or 12 million error lines will be printed every time you filter); restore the proper poly and/or .fb file and resume sieving. NB: the siever only reads the .poly file (and doesn't care about any others), msieve reads .fb file, .ini file (for control and other purposes (and doesn't care about the .poly file); therefore, check the correspondence of these files, -- if they don't match, then your tools are not communicating and wissenschaft ist tot. Last fiddled with by Batalov on 2011-05-21 at 01:48 Reason: suitable = valid = useful (too many synonyms)

2011-05-21, 04:15	#586
EdH "Ed Hall" Dec 2009 Adirondack Mtns 3,823 Posts	Thanks! I checked the current .poly against the original and they were different. I transplanted the original for the current, but did not interrupt the script. Maybe it will work its way out with that simple swap. I may not be able to check it until tomorrow night. By then, there should be some progress or setback. Last fiddled with by EdH on 2011-05-21 at 04:16 Reason: just 'cause

2011-09-03, 23:36	#594
firejuggler Apr 2010 Over the rainbow 19×137 Posts	Did you run a polyselect or did you calculate the poly by yourself? andd if you did it by yourself, can you explain it? And Walter, once you get your factorisation (and the work get published), could you update http://factordb.com/ with your newfound factor? Last fiddled with by firejuggler on 2011-09-03 at 23:43

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Msieve & ggnfs on MacOS	xilman	Msieve	8	2017-05-20 00:12
Factorizing with MSIEVE, GGNFS & Factmsieve.py	Romuald	Msieve	24	2015-11-09 20:16
Infinite loop for ggnfs or msieve	Greebley	Aliquot Sequences	4	2013-02-06 19:28
Error running GGNFS+msieve+factmsieve.py	D. B. Staple	Factoring	6	2011-06-12 22:23
A new driver? (or type of driver?)	10metreh	Aliquot Sequences	3	2010-02-15 15:57

2011-05-23, 01:17	#587
EdH "Ed Hall" Dec 2009 Adirondack Mtns 3,823 Posts	OK, no go with any of my repair tests. I've started a different winXP machine from scratch. It should take about a week to complete. If it still won't solve it, I guess I'll have to throw in the towel for now on these larger composites. Thanks for all the help.

2011-06-26, 13:18	#588
Hasgar Jun 2011 7 Posts	hello guys, im a ggnfs noob and factored some small rsa numbers with jeffs guide. my question is: is there a command to test my own polynomials? i know that msieve gives me very good polynomials but i want to make my own tests.

2011-09-03, 16:21	#589
Walter Nissen Nov 2006 Terra 78₁₀ Posts	I've run factMsieve.py for 40 hours on a cmd.exe box on XP on a 1-core , 2-thread Pentium 4 to factor a c114 . Nice . Really nice . Now I have some others I'd like to factor . The least is a c127 . Can I just follow the instructions in the "Beginners Guide" to factor a c127 ? Is this something people do routinely ? Or do I need to do more ? Should I use NUM_CORES = 1 or NUM_CORES = 2 ? ( If 1 , can I do any useful factoring with the other thread ? ) Will it likely finish within 2 weeks ? Should I use YAFU instead ? Anyone who'd like to tell me where I can find answers to these questions among the thousands of posts here will find me very grateful .

2011-09-03, 22:43	#592
Walter Nissen Nov 2006 Terra 2·3·13 Posts	Thanks for responding. Let np ( n ) = n^n + (n+1)^(n+1) . c127 = np ( 79 ) / ( 547 * 1381 * 66269726871718249753 ) There's probably more than you wanted to know about np ( n ) at the as yet unpublished : http://upforthecount.com/math/nnp.html There's a little known about the factors . p \| np ( 2p-2 ) Some larger np have been factored . np ( 415 ) = 29 * p1089 np ( 802 ) splits into 11 factors including a p2320 . ( n*n + n + 1 ) / 3 \| np ( n ) if 4 = n mod 6 ( divides twice ) . p \| np ( n ) for certain n mod (p(p-1)) ; e.g. , also 3 \| np ( n ) if 4 = n mod 6 . All p give rise to such families , e.g. , 5 \| np ( n ) if 1 = n mod 20 or if 8 = n mod 20 , where 20 = 5(5-1) . If the word "certain" gives rise to an algorithm , then factoring might be trivial . I don't know how to map this onto SNFS , but I never discount genius . The next largest ones I've noticed not yet factored by extensive ECM are a c145 , a c147 and a c149 , for n = 87 , 83 and 96 .