The factorization of primorials +/- 1

[Joppe_Bos]

Today GNFS finished the c147 from:
P84# + 1 = 433# + 1 into:
p58 = 2103157367614134948281973504071365425569967537340462000043
p89 = 73439599379616488094871810663689279459773266178128387816795413342444947778160098979112621
Some information:
Sieving took almost 3 weeks and run on 2 to 8 processors. I used ggnfs for the lattice sieving (Franke and Kleinjung's implementation) and msieve for line sieving (A = (8 * 10^8) and B < 5000) to get a lot of "cheap" relations. Post processing was done with msieve which produced the following: "matrix is 3976158 x 3976406 with weight 287865421 (avg 72.39/col)". Lanczos took 3,5 days running on 2 processors and found 41 dependencies. The factors were found on the first dependency in 1.5 hours.

I will continue to do some ECM work on the first composites in the tables.

[jasonp]

Originally Posted by Joppe_Bos

Today GNFS finished the c147 from:
P84# + 1 = 433# + 1 into:
p58 = 2103157367614134948281973504071365425569967537340462000043
p89 = 73439599379616488094871810663689279459773266178128387816795413342444947778160098979112621

Well done. Could you post or email me the logfile?

[Joppe_Bos]

Of course here it is.

Mon Oct 29 14:57:52 2007  Msieve v. 1.28
Mon Oct 29 14:57:52 2007  random seeds: e6a088a6 46b5193e
Mon Oct 29 14:57:52 2007  factoring 154455034509870871138247068868721721591054129536601105421027368296319778967533725346346141804408048197628722872409650911503036410072002427003842703 (147 digits)
Mon Oct 29 14:57:53 2007  commencing number field sieve (146-digit input)
Mon Oct 29 14:57:53 2007  R0: -9080532434842022494687534131
Mon Oct 29 14:57:53 2007  R1:  89513276937744847
Mon Oct 29 14:57:53 2007  A0:  3014695916777782838897463814923520
Mon Oct 29 14:57:53 2007  A1:  24509378571775409994732992672
Mon Oct 29 14:57:53 2007  A2: -37127804081311724930876
Mon Oct 29 14:57:53 2007  A3: -1355754107840870302
Mon Oct 29 14:57:53 2007  A4: -85121038429
Mon Oct 29 14:57:53 2007  A5:  2501760
Mon Oct 29 14:57:53 2007  size score = 4.593362e-15, Murphy alpha = -5.590193, combined = 2.960697e-14
Mon Oct 29 14:59:00 2007  restarting with 30158094 relations
Mon Oct 29 14:59:00 2007  
Mon Oct 29 14:59:00 2007  commencing relation filtering
Mon Oct 29 14:59:00 2007  commencing duplicate removal, pass 1
Mon Oct 29 15:03:32 2007  error -3 reading relation 30132773
Mon Oct 29 15:03:33 2007  found 2567929 hash collisions in 30158093 relations
Mon Oct 29 15:03:33 2007  commencing duplicate removal, pass 2
Mon Oct 29 15:05:14 2007  found 1044002 duplicates and 29114091 unique relations
Mon Oct 29 15:05:14 2007  memory use: 94.6 MB
Mon Oct 29 15:05:27 2007  ignoring smallest 1399557 rational and 1399983 algebraic ideals
Mon Oct 29 15:05:27 2007  filtering rational ideals above 22174884
Mon Oct 29 15:05:27 2007  filtering algebraic ideals above 22174884
Mon Oct 29 15:05:27 2007  need 4759218 more relations than ideals
Mon Oct 29 15:05:27 2007  commencing singleton removal, pass 1
Mon Oct 29 15:10:15 2007  relations with 0 large ideals: 55470
Mon Oct 29 15:10:15 2007  relations with 1 large ideals: 988967
Mon Oct 29 15:10:15 2007  relations with 2 large ideals: 5358003
Mon Oct 29 15:10:15 2007  relations with 3 large ideals: 10571880
Mon Oct 29 15:10:15 2007  relations with 4 large ideals: 8128284
Mon Oct 29 15:10:15 2007  relations with 5 large ideals: 3182933
Mon Oct 29 15:10:15 2007  relations with 6 large ideals: 726086
Mon Oct 29 15:10:15 2007  relations with 7+ large ideals: 102468
Mon Oct 29 15:10:15 2007  29114091 relations and about 25855503 large ideals
Mon Oct 29 15:10:15 2007  commencing singleton removal, pass 2
Mon Oct 29 15:15:00 2007  found 12141501 singletons
Mon Oct 29 15:15:00 2007  current dataset: 16972590 relations and about 12057839 large ideals
Mon Oct 29 15:15:00 2007  commencing singleton removal, pass 3
Mon Oct 29 15:18:05 2007  found 1585920 singletons
Mon Oct 29 15:18:05 2007  current dataset: 15386670 relations and about 10424702 large ideals
Mon Oct 29 15:18:05 2007  commencing singleton removal, pass 4
Mon Oct 29 15:20:58 2007  found 238887 singletons
Mon Oct 29 15:20:58 2007  current dataset: 15147783 relations and about 10184466 large ideals
Mon Oct 29 15:20:58 2007  commencing singleton removal, final pass
Mon Oct 29 15:24:08 2007  memory use: 545.0 MB
Mon Oct 29 15:24:08 2007  commencing in-memory singleton removal
Mon Oct 29 15:24:10 2007  begin with 15147783 relations and 12155945 unique ideals
Mon Oct 29 15:24:28 2007  reduce to 11844213 relations and 8715774 ideals in 11 passes
Mon Oct 29 15:24:28 2007  max relations containing the same ideal: 33
Mon Oct 29 15:24:30 2007  dataset has 11.7% excess relations
Mon Oct 29 15:24:41 2007  ignoring smallest 1268076 rational and 1268500 algebraic ideals
Mon Oct 29 15:24:41 2007  filtering rational ideals above 19957395
Mon Oct 29 15:24:41 2007  filtering algebraic ideals above 19957395
Mon Oct 29 15:24:41 2007  need 3023503 more relations than ideals
Mon Oct 29 15:24:41 2007  commencing singleton removal, final pass
Mon Oct 29 15:27:47 2007  memory use: 666.1 MB
Mon Oct 29 15:27:47 2007  commencing in-memory singleton removal
Mon Oct 29 15:27:50 2007  begin with 15147783 relations and 12418568 unique ideals
Mon Oct 29 15:28:08 2007  reduce to 11833218 relations and 8966630 ideals in 11 passes
Mon Oct 29 15:28:08 2007  max relations containing the same ideal: 33
Mon Oct 29 15:28:10 2007  dataset has 2.4% excess relations
Mon Oct 29 15:28:12 2007  relations with 0 large ideals: 47059
Mon Oct 29 15:28:12 2007  relations with 1 large ideals: 732276
Mon Oct 29 15:28:12 2007  relations with 2 large ideals: 2724357
Mon Oct 29 15:28:12 2007  relations with 3 large ideals: 4000044
Mon Oct 29 15:28:12 2007  relations with 4 large ideals: 2861071
Mon Oct 29 15:28:12 2007  relations with 5 large ideals: 1140934
Mon Oct 29 15:28:12 2007  relations with 6 large ideals: 284873
Mon Oct 29 15:28:12 2007  relations with 7+ large ideals: 42604
Mon Oct 29 15:28:12 2007  commencing 2-way merge
Mon Oct 29 15:28:22 2007  merged 4021093 relations
Mon Oct 29 15:28:26 2007  reduce to 7812125 relation sets and 4945537 unique ideals
Mon Oct 29 15:28:26 2007  commencing full merge
Mon Oct 29 15:54:09 2007  found 4337930 cycles, need 4017737
Mon Oct 29 15:54:14 2007  weight of 4017737 cycles is about 261261627 (65.03/cycle)
Mon Oct 29 15:54:14 2007  distribution of cycle lengths:
Mon Oct 29 15:54:14 2007  1 relations: 501207
Mon Oct 29 15:54:14 2007  2 relations: 567458
Mon Oct 29 15:54:14 2007  3 relations: 563816
Mon Oct 29 15:54:14 2007  4 relations: 501809
Mon Oct 29 15:54:14 2007  5 relations: 436066
Mon Oct 29 15:54:14 2007  6 relations: 360973
Mon Oct 29 15:54:14 2007  7 relations: 295517
Mon Oct 29 15:54:14 2007  8 relations: 236101
Mon Oct 29 15:54:14 2007  9 relations: 187843
Mon Oct 29 15:54:14 2007  10+ relations: 366947
Mon Oct 29 15:54:14 2007  heaviest cycle: 14 relations
Mon Oct 29 15:54:14 2007  commencing cycle optimization
Mon Oct 29 16:07:27 2007  start with 19343807 relations
Mon Oct 29 16:09:02 2007  pruned 348420 relations
Mon Oct 29 16:09:05 2007  distribution of cycle lengths:
Mon Oct 29 16:09:05 2007  1 relations: 501207
Mon Oct 29 16:09:05 2007  2 relations: 575170
Mon Oct 29 16:09:06 2007  3 relations: 579640
Mon Oct 29 16:09:06 2007  4 relations: 511107
Mon Oct 29 16:09:06 2007  5 relations: 445215
Mon Oct 29 16:09:07 2007  6 relations: 364449
Mon Oct 29 16:09:07 2007  7 relations: 296816
Mon Oct 29 16:09:08 2007  8 relations: 234148
Mon Oct 29 16:09:09 2007  9 relations: 184350
Mon Oct 29 16:09:09 2007  10+ relations: 325635
Mon Oct 29 16:09:09 2007  heaviest cycle: 14 relations
Mon Oct 29 16:09:12 2007  
Mon Oct 29 16:09:15 2007  commencing linear algebra
Mon Oct 29 16:09:18 2007  factor base loaded:
Mon Oct 29 16:09:18 2007  3001134 rational ideals (max prime = 49999991)
Mon Oct 29 16:09:18 2007  3000158 algebraic ideals (max prime = 49999921)
Mon Oct 29 16:09:20 2007  read 4017737 cycles
Mon Oct 29 16:09:39 2007  cycles contain 10301456 unique relations
Mon Oct 29 16:11:27 2007  read 10301456 relations
Mon Oct 29 16:11:50 2007  using 32 quadratic characters above 950174294
Mon Oct 29 16:24:41 2007  matrix is 4014490 x 4017737 with weight 376772986 (avg 93.78/col)
Mon Oct 29 16:28:22 2007  filtering completed in 3 passes
Mon Oct 29 16:28:24 2007  matrix is 3976206 x 3976406 with weight 373785120 (avg 94.00/col)
Mon Oct 29 16:29:05 2007  saving the first 48 matrix rows for later
Mon Oct 29 16:29:10 2007  matrix is 3976158 x 3976406 with weight 287865421 (avg 72.39/col)
Mon Oct 29 16:29:10 2007  matrix includes 64 packed rows
Mon Oct 29 16:29:10 2007  using block size 43690 for processor cache size 1024 kB
Mon Oct 29 16:59:51 2007  commencing Lanczos iteration (2 threads)
Fri Nov  2 06:56:26 2007  lanczos halted after 62876 iterations
Fri Nov  2 06:56:50 2007  recovered 41 nontrivial dependencies
Fri Nov  2 06:56:52 2007  
Fri Nov  2 06:56:52 2007  commencing square root phase
Fri Nov  2 06:56:52 2007  reading relations for dependency 1
Fri Nov  2 06:56:57 2007  read 1986475 cycles
Fri Nov  2 06:57:05 2007  cycles contain 6247300 unique relations
Fri Nov  2 07:01:25 2007  read 6247300 relations
Fri Nov  2 07:02:29 2007  multiplying 9434098 relations
Fri Nov  2 07:46:05 2007  multiply complete, coefficients have about 520.95 million bits
Fri Nov  2 07:46:31 2007  initial square root is modulo 2226091841
Fri Nov  2 09:43:58 2007  prp58 factor: 2103157367614134948281973504071365425569967537340462000043
Fri Nov  2 09:43:58 2007  prp89 factor: 73439599379616488094871810663689279459773266178128387816795413342444947778160098979112621
Fri Nov  2 09:43:58 2007  elapsed time 90:46:06

[Joppe_Bos]

Done 1210 curves on P103# - 1 with B1=11e6
Done 1840 curves on P89# - 1 with B1=11e6
Done 1800 curves on P84# - 1 with B1=43e6
Done 10000 curves on P100# - 1 with B1=43e6

Ater 2350 curves with B1=43e6 I found the following factor for P89# - 1 = 461# - 1 = (c191) = p50 * c141
p50 = 23107891172756940484396791068944577893302431569651

[Joppe_Bos]

After 1250 curves with B1=43e6 I found the following factor of P91# - 1 with ECM:
p46 = 5609579787465154595799805307759566490414969773
This left a c134 which was factored with GNFS:
p58 = 1756183307980802269727138578347679764898569146415808901453
p77 = 19485587120325755278768508387246943402198432910615208963924812568401368267119
This finishes P91# - 1 = 467# - 1 = p17 * p46 * p58 * p77.

[Joppe_Bos]

Done 2380 additional curves on P76# + 1 with B1=43e6

After 700 curves with B1=43e6 the following factor was found for P84# - 1 = 433# - 1 with ECM
p45 = 129264659095401435055266029834790541947246421
This left a c112 which was factored into p56 * p56 with gnfs:
p56 = 45898718716440636206866279639797919472732283044407787227
p56 = 63938003365896934592276553936189944723957123752924390471

[sean]

Originally Posted by Joppe_Bos

After 700 curves with B1=43e6 the following factor was found for P84# - 1 = 433# - 1 with ECM
p45 = 129264659095401435055266029834790541947246421
This left a c112 which was factored into p56 * p56 with gnfs:
p56 = 45898718716440636206866279639797919472732283044407787227
p56 = 63938003365896934592276553936189944723957123752924390471

Nice work knocking off the smallest index on the -1 side

[Joppe_Bos]

Completed the remaining factor of from P89# - 1, c141 = p53 * p88 with gnfs.
p53 = 77098682931426841505300786722746403361806923380574191
and
p88 = 5670545015493947409048128570590300568420987574419794543227855765612508971630047212798309

[fivemack]

Joppe_Bos and I have now knocked off the smallest index on the +1 side, a nice ECM-proof C156:

P76#+1 C156 = 
p76 1252724596359114607416742220222030302294387892643573321852443386423988709173 *
p81 525745644577227350352675880086967107492595776746408796031609932313413723952581047

518-bit GNFS; it took a month on about half a dozen computers. Many thanks to jasonp for getting msieve up to the level of robustness that handled this without strain!

[jasonp]

Originally Posted by fivemack

518-bit GNFS; it took a month on about half a dozen computers. Many thanks to jasonp for getting msieve up to the level of robustness that handled this without strain!

My pleasure, Christmas came a day early this year :) This is easily the largest GNFS job the postprocessing has tackled to date.

[sean]

Originally Posted by fivemack

Joppe_Bos and I have now knocked off the smallest index on the +1 side, a nice ECM-proof C156:

P76#+1 C156 = 
p76 1252724596359114607416742220222030302294387892643573321852443386423988709173 *
p81 525745644577227350352675880086967107492595776746408796031609932313413723952581047

518-bit GNFS; it took a month on about half a dozen computers. Many thanks to jasonp for getting msieve up to the level of robustness that handled this without strain!

Excellent work. That's a nice Xmas present.