Running GGNFS

[10metreh]

Originally Posted by wreck

Thanks for your response,I'm using Windows Vista TM Home Basic,
The system is 32 bits.RAM is 2.00 GB,
processor is Intel(R) Core(TM) Duo CPU T6400 @ 2.00GHz 2.00GHz

I've collected about 5.6 million relations and it maybe finished after some hours.

After I factor this number,I'll try to factor another similar numbers using snfs.

After updating my factMsieve.pl file,my problem is a little better now,at least which don't let the example.dat change from 500MB to 1KB.

By the way,I want to ask some other questions.
How biggest number could be factored with my 2GB RAM using gnfs and snfs.
If I can spend one month using the computer which I current use,How big the number will be of using gnfs and snfs.

Thanks again.

I have no idea about the problem. You can probably do up to about 155 digits GNFS with 2GB, not sure about SNFS (difficulty 220?) And I don't have a core2, so I don't know how long it'll take.

[wreck]

Originally Posted by 10metreh

...
You can probably do up to about 155 digits GNFS with 2GB, not sure about SNFS (difficulty 220?) And I don't have a core2, so I don't know how long it'll take.

The number of 133,73- C117 has been split into p50*p68.

Mon Jun 29 02:36:36 2009  Msieve v. 1.41
Mon Jun 29 02:36:36 2009  random seeds: 7adbfe80 90c7d790
Mon Jun 29 02:36:36 2009  factoring 649017259752958866605145764425757672283171950861900323760825207701118761377483133801690875448183846729244199808206733 (117 digits)
Mon Jun 29 02:36:38 2009  searching for 15-digit factors
Mon Jun 29 02:36:40 2009  commencing number field sieve (117-digit input)
Mon Jun 29 02:36:40 2009  R0: -25811520411263150444868
Mon Jun 29 02:36:40 2009  R1:  10067298142853
Mon Jun 29 02:36:40 2009  A0: -223178434415630870667249463
Mon Jun 29 02:36:40 2009  A1: -100327593777682496655832
Mon Jun 29 02:36:40 2009  A2: -13122513616291617555
Mon Jun 29 02:36:40 2009  A3: -639755741801855
Mon Jun 29 02:36:40 2009  A4:  21758634661
Mon Jun 29 02:36:40 2009  A5:  56640
Mon Jun 29 02:36:40 2009  skew 1.00, size 3.212520e-011, alpha -6.108421, combined = 2.211979e-011
Mon Jun 29 02:36:40 2009  
Mon Jun 29 02:36:40 2009  commencing square root phase
Mon Jun 29 02:36:40 2009  reading relations for dependency 1
Mon Jun 29 02:36:42 2009  read 282646 cycles
Mon Jun 29 02:36:43 2009  cycles contain 1176125 unique relations
Mon Jun 29 02:37:16 2009  read 1176125 relations
Mon Jun 29 02:37:25 2009  multiplying 962018 relations
Mon Jun 29 02:41:29 2009  multiply complete, coefficients have about 45.62 million bits
Mon Jun 29 02:41:31 2009  initial square root is modulo 3550109
Mon Jun 29 02:46:49 2009  sqrtTime: 609
Mon Jun 29 02:46:49 2009  prp50 factor: 32697105469213359815376643847840081701681786695509
Mon Jun 29 02:46:49 2009  prp68 factor: 19849379645059241577991406645142244036518705772264107201949154658137
Mon Jun 29 02:46:49 2009  elapsed time 00:10:13

It only take me about 21 hours totally.
poly sieving took 2 hours,relations sieving took 18 hours,and the last part took 1 hour.

[wreck]

It seems like that I get some difficulties when using snfs.

I'm preparing to factoring 136^73-1 using snfs by msieve.
the worktodo.ini is

n:4731588299358581392206972814837279876590647809661957400062456689033346472753376261112083650744829144188189893004499029020127140225271052682382194515789
# 136^73-1, difficulty: 158.21, skewness: 1.78, alpha: 0.00
# Cost: 2.84349e+015, est. time: 1.35 GHz days (not accurate yet!)
X5 16
X4 0
X3 0
X2 0
X1 0
X0 -289
Y1 -1
Y0 25178139429992821256026738130944
M 25178139429992821256026738130944

but I got the following error:

F:\chenbo\math\msieve>msieve -ns
error generating or reading NFS polynomials
error -4 converting '136^73-1, difficulty: 158.21, skewness: 1.78, alpha: 0.00'
error -4 converting '2.84349e+015, est. time: 1.35 GHz days (not accurate yet!)'

error -8 converting '5 16'
error -8 converting '4 0'
error -8 converting '3 0'
error -8 converting '2 0'
error -8 converting '1 0'
error -11 converting '0 -289'
error 0 converting '1 -1'
error -8 converting '0 25178139429992821256026738130944'

F:\chenbo\math\msieve>

any ideas?

[10metreh]

Originally Posted by wreck

It seems like that I get some difficulties when using snfs.

I'm preparing to factoring 136^73-1 using snfs by msieve.
the worktodo.ini is

n:4731588299358581392206972814837279876590647809661957400062456689033346472753376261112083650744829144188189893004499029020127140225271052682382194515789
# 136^73-1, difficulty: 158.21, skewness: 1.78, alpha: 0.00
# Cost: 2.84349e+015, est. time: 1.35 GHz days (not accurate yet!)
X5 16
X4 0
X3 0
X2 0
X1 0
X0 -289
Y1 -1
Y0 25178139429992821256026738130944
M 25178139429992821256026738130944

but I got the following error:

F:\chenbo\math\msieve>msieve -ns
error generating or reading NFS polynomials
error -4 converting '136^73-1, difficulty: 158.21, skewness: 1.78, alpha: 0.00'
error -4 converting '2.84349e+015, est. time: 1.35 GHz days (not accurate yet!)'
 
error -8 converting '5 16'
error -8 converting '4 0'
error -8 converting '3 0'
error -8 converting '2 0'
error -8 converting '1 0'
error -11 converting '0 -289'
error 0 converting '1 -1'
error -8 converting '0 25178139429992821256026738130944'
 
F:\chenbo\math\msieve>

any ideas?

You have to convert the polynomial to GGNFS format. Create this file:

n: 4731588299358581392206972814837279876590647809661957400062456689033346472753376261112083650744829144188189893004499029020127140225271052682382194515789
c5: 16
c0: -289
Y1: -1
Y0: 25178139429992821256026738130944
skew: 1.78
type: snfs

and call it snfs.poly. Then run "factMsieve.pl snfs".

[unconnected]

I've a problem factoring 102 digit number with GGNFS.

Mon Jul 20 21:57:44 2009  Msieve v. 1.42
Mon Jul 20 21:57:44 2009  random seeds: de43dd40 2bc97a68
Mon Jul 20 21:57:44 2009  factoring 333024951806774278910957960188334627970628392327150533487887555153082737438366043160130114305192152269 (102 digits)
Mon Jul 20 21:57:45 2009  searching for 15-digit factors
Mon Jul 20 21:57:46 2009  commencing number field sieve (102-digit input)
Mon Jul 20 21:57:46 2009  R0: -15203982399225076243
Mon Jul 20 21:57:46 2009  R1:  75997127183
Mon Jul 20 21:57:46 2009  A0: -27135635269355479728180
Mon Jul 20 21:57:46 2009  A1:  30878653909272479847
Mon Jul 20 21:57:46 2009  A2:  27412399957360902
Mon Jul 20 21:57:46 2009  A3:  4724996935282
Mon Jul 20 21:57:46 2009  A4: -1723058788
Mon Jul 20 21:57:46 2009  A5:  409920
Mon Jul 20 21:57:46 2009  skew 2896.18, size 1.055899e-009, alpha -6.085626, combined = 2.680744e-009
Mon Jul 20 21:57:46 2009  
Mon Jul 20 21:57:46 2009  commencing relation filtering
Mon Jul 20 21:57:46 2009  estimated available RAM is 1902.7 MB
Mon Jul 20 21:57:46 2009  commencing duplicate removal, pass 1
Mon Jul 20 21:58:38 2009  found 2157707 hash collisions in 6318800 relations
Mon Jul 20 21:58:47 2009  commencing duplicate removal, pass 2
Mon Jul 20 21:59:00 2009  found 2295865 duplicates and 4022935 unique relations
Mon Jul 20 21:59:00 2009  memory use: 45.3 MB
Mon Jul 20 21:59:00 2009  reading ideals above 100000
Mon Jul 20 21:59:00 2009  commencing singleton removal, initial pass
Mon Jul 20 21:59:49 2009  memory use: 74.6 MB
Mon Jul 20 21:59:49 2009  reading all ideals from disk
Mon Jul 20 21:59:50 2009  memory use: 126.9 MB
Mon Jul 20 21:59:50 2009  commencing in-memory singleton removal
Mon Jul 20 21:59:50 2009  begin with 4022935 relations and 4542999 unique ideals
Mon Jul 20 21:59:55 2009  reduce to 1214193 relations and 1191329 ideals in 17 passes
Mon Jul 20 21:59:55 2009  max relations containing the same ideal: 113
Mon Jul 20 21:59:56 2009  relations with 0 large ideals: 73
Mon Jul 20 21:59:56 2009  relations with 1 large ideals: 107
Mon Jul 20 21:59:56 2009  relations with 2 large ideals: 2287
Mon Jul 20 21:59:56 2009  relations with 3 large ideals: 20164
Mon Jul 20 21:59:56 2009  relations with 4 large ideals: 95359
Mon Jul 20 21:59:56 2009  relations with 5 large ideals: 247673
Mon Jul 20 21:59:56 2009  relations with 6 large ideals: 370591
Mon Jul 20 21:59:56 2009  relations with 7+ large ideals: 477939
Mon Jul 20 21:59:56 2009  commencing 2-way merge
Mon Jul 20 21:59:57 2009  reduce to 654037 relation sets and 631370 unique ideals
Mon Jul 20 21:59:57 2009  ignored 197 oversize relation sets
Mon Jul 20 21:59:57 2009  commencing full merge
Mon Jul 20 22:00:29 2009  memory use: 20.6 MB
Mon Jul 20 22:00:29 2009  found 21759 cycles, need 141913
Mon Jul 20 22:00:29 2009  weight of 21759 cycles is about 3663610 (168.37/cycle)
Mon Jul 20 22:00:29 2009  distribution of cycle lengths:
Mon Jul 20 22:00:29 2009  1 relations: 1544
Mon Jul 20 22:00:29 2009  2 relations: 771
Mon Jul 20 22:00:29 2009  3 relations: 844
Mon Jul 20 22:00:29 2009  4 relations: 880
Mon Jul 20 22:00:29 2009  5 relations: 912
Mon Jul 20 22:00:29 2009  6 relations: 928
Mon Jul 20 22:00:29 2009  7 relations: 894
Mon Jul 20 22:00:29 2009  8 relations: 895
Mon Jul 20 22:00:29 2009  9 relations: 802
Mon Jul 20 22:00:29 2009  10+ relations: 13289
Mon Jul 20 22:00:29 2009  heaviest cycle: 28 relations
Mon Jul 20 22:00:29 2009  commencing cycle optimization
Mon Jul 20 22:00:29 2009  start with 282947 relations
Mon Jul 20 22:00:30 2009  pruned 10464 relations
Mon Jul 20 22:00:30 2009  memory use: 7.0 MB
Mon Jul 20 22:00:30 2009  distribution of cycle lengths:
Mon Jul 20 22:00:30 2009  1 relations: 1544
Mon Jul 20 22:00:30 2009  2 relations: 793
Mon Jul 20 22:00:30 2009  3 relations: 862
Mon Jul 20 22:00:30 2009  4 relations: 904
Mon Jul 20 22:00:30 2009  5 relations: 957
Mon Jul 20 22:00:30 2009  6 relations: 954
Mon Jul 20 22:00:30 2009  7 relations: 929
Mon Jul 20 22:00:30 2009  8 relations: 939
Mon Jul 20 22:00:30 2009  9 relations: 861
Mon Jul 20 22:00:30 2009  10+ relations: 13016
Mon Jul 20 22:00:30 2009  heaviest cycle: 28 relations
Mon Jul 20 22:00:30 2009  RelProcTime: 164
Mon Jul 20 22:00:30 2009  
Mon Jul 20 22:00:30 2009  commencing linear algebra
Mon Jul 20 22:00:30 2009  read 21759 cycles
Mon Jul 20 22:00:30 2009  cycles contain 146535 unique relations
Mon Jul 20 22:00:36 2009  read 146535 relations
Mon Jul 20 22:00:36 2009  using 20 quadratic characters above 67066200
Mon Jul 20 22:00:37 2009  building initial matrix
Mon Jul 20 22:00:38 2009  memory use: 17.4 MB
Mon Jul 20 22:00:38 2009  read 21759 cycles
Mon Jul 20 22:00:38 2009  matrix is 133783 x 21759 (11.5 MB) with weight 3605834 (165.72/col)
Mon Jul 20 22:00:38 2009  sparse part has weight 2868878 (131.85/col)
Mon Jul 20 22:00:39 2009  matrix is corrupt; skipping linear algebra
Mon Jul 20 22:00:39 2009  
Mon Jul 20 22:00:39 2009  commencing square root phase
Mon Jul 20 22:00:39 2009  reading relations for dependency 1
Mon Jul 20 22:00:39 2009  error: read_cycles can't open dependency file

Number of cycles (21759) does not depend on number of relations (trying 3.5M-6.3M). I switched to msieve 1.41 and got another set of problems. Starting with 4M relations - filtering wants 209304 more relations, with 4.2M - filtering wants 77616 more relations, with 4.3M another error - "matrix must have more columns than rows". The same error with 4.4M and 4.5M relations, but from 4.6M up to 6.3M error changed - "too many merge attempts". Here is run with 4.6M relations in attachment.
Then I deleted all related files and begin again from scratch - no result. What's wrong?

[axn]

you have humongous amount of duplicates. Not helpful, I know -- just an observation.

Please post the sieving parameters, sieve range, and yield.

[jasonp]

The behavior with v1.41 is sort of expected; you start off with too few relations for the singleton removal to complete, then the singleton removal completes but you have slightly too few relations so the matrix gets destroyed when the linear algebra starts. What's strange is that apparently you go from that straight to having far too many excess relations.

My guess is that because you have so many duplicates, the dataset is always in a position where it is just short of having enough relations to create a dense enough matrix. That would also explain why the merge phase doesn't find enough cycles; it starts off having enough, but pruning a few columns creates more singletons that need to get deleted, which causes a chain reaction that destroys the matrix.

Not sure what to do about that; use a siever with a larger area to find more unique relations?

[henryzz]

how did you get that amount of duplicates did you use 10e or 11e or something?

[10metreh]

Originally Posted by unconnected

[code]Mon Jul 20 21:59:56 2009 commencing 2-way merge
Mon Jul 20 21:59:57 2009 reduce to 654037 relation sets and 631370 unique ideals
Mon Jul 20 21:59:57 2009 ignored 197 oversize relation sets

Could this have anything to do with it?

Edit: this should be moved to the 1.42 thread.

[jasonp]

Oversize relation sets are another sign that you have just enough relations to build a matrix. Otherwise you would have some extras, and the clique removal would prune the oversize sets before the merge phase had to do it.

[10metreh]

I notice it is p51*p52 in the database. Unconnected, was that you or someone else?