CADO NFS

[VBCurtis]

Originally Posted by RichD

So what happens when you get a power outage after a factorization completes in the middle of the night during a thunderstorm? Oh, don't get me started about weather related power issues in the Midwest.

That's how I lost the first job! This time, I learned screen -r doesn't work after the process completed. I really like that the data is auto-deleted; I've run out of disk more times than I can count because I forgot to delete relations from a previous factorization (or two). So, I don't want to manually direct the factorization data away from /tmp.

[pinhodecarlos]

This can be off topic or not but distributed.net posted last night (GMT) on facebook the following: "Do you have a math project which is looking for a huge processing power? We can help."


I can't find anything on this on their website but maybe they can support on a distributed CADO NFS.

[Dubslow]

Originally Posted by VBCurtis

This time, I learned screen -r doesn't work after the process completed.

Not if you run the process from within screen! (As opposed to being an argument to screen, like you quoted before)

[VictordeHolland]

Originally Posted by Gimarel

The comparison was run on an i7-3770K @ 4GHz.

YAFU/msieve with patches for better parametrisation
Poly selection: 02:21:19
Sieving: 41:05:55
Matrix: 01:45:36
Total: 45:45:00

CADO with default parameters
Poly selection: 01:58:30
Sieving: 95:00:34
Matrix: 14:13:40
Total: 112:04:07

Total time includes setup, filtering, and square root.
Note that the CADO poly had a msieve score that was about 5% better than the score of the YAFU poly.

Could you share the better parameters?

[EdH]

I may have to figure out some more details, but the rsa155 hybrid run is finished. It was not without trouble, though. Again I had the negative leading coefficient trouble and had to run the square root phase again with a modified .fb file. I will have to add a check for this to my poly to .fb binary.

I will probably need to dig out more details, but for now:

cado-nfs was started at day 1 08:13:10
sieving completed at day 1 18:11:49
msieve filtering started at day 1 18:17:05

Filtering had a huge error -11 problem, with a few error -1's thrown in:

Tue May 15 18:17:05 2018  Msieve v. 1.54 (SVN 1015)
Tue May 15 18:17:05 2018  random seeds: b0c7282b 1f9fcba3
Tue May 15 18:17:05 2018  factoring 10941738641570527421809707322040357612003732945449205990913842131476349984288934784717997257891267332497625752899781833797076537244027146743531593354333897 (155 digits)
Tue May 15 18:17:06 2018  searching for 15-digit factors
Tue May 15 18:17:06 2018  commencing number field sieve (155-digit input)
Tue May 15 18:17:06 2018  R0: -612027504584914645235174827421
Tue May 15 18:17:06 2018  R1: 25879721744003857318699
Tue May 15 18:17:06 2018  A0: 182745817499024369420760271832448384
Tue May 15 18:17:06 2018  A1: -427211473195034674829019757212
Tue May 15 18:17:06 2018  A2: -3743757388243368106451009
Tue May 15 18:17:06 2018  A3: 10289593997537051662
Tue May 15 18:17:06 2018  A4: 15468757262920
Tue May 15 18:17:06 2018  A5: -8954400
Tue May 15 18:17:06 2018  skew 1.00, size 5.406e-15, alpha -7.580, combined = 4.712e-14 rroots = 3
Tue May 15 18:17:06 2018  
Tue May 15 18:17:06 2018  commencing relation filtering
Tue May 15 18:17:06 2018  estimated available RAM is 15926.6 MB
Tue May 15 18:17:06 2018  commencing duplicate removal, pass 1
Tue May 15 18:17:06 2018  error -1 reading relation 0 (line 21)
Tue May 15 18:17:06 2018  error -11 reading relation 1
Tue May 15 18:17:06 2018  error -11 reading relation 2
...
Tue May 15 18:17:10 2018  error -11 reading relation 224097
Tue May 15 18:17:10 2018  error -11 reading relation 224098
Tue May 15 18:17:10 2018  error -11 reading relation 224099 (line 224120)
Tue May 15 18:29:02 2018  error -1 reading relation 97073091
Tue May 15 18:29:10 2018  error -1 reading relation 98240030
Tue May 15 18:29:23 2018  error -1 reading relation 100033046
...

LA started at day 1 18:58:32 and finished at day 2 06:18:23:

Tue May 15 18:58:32 2018  commencing linear algebra
Tue May 15 18:58:33 2018  read 4811300 cycles
Tue May 15 18:58:39 2018  cycles contain 16143189 unique relations
Tue May 15 19:01:43 2018  read 16143189 relations
Tue May 15 19:01:59 2018  using 20 quadratic characters above 4294917295
Tue May 15 19:03:09 2018  building initial matrix
Tue May 15 19:05:04 2018  memory use: 2101.0 MB
Tue May 15 19:05:06 2018  read 4811300 cycles
Tue May 15 19:05:07 2018  matrix is 4811123 x 4811300 (1457.0 MB) with weight 456267854 (94.83/col)
Tue May 15 19:05:07 2018  sparse part has weight 329008565 (68.38/col)
Tue May 15 19:05:48 2018  filtering completed in 2 passes
Tue May 15 19:05:49 2018  matrix is 4807229 x 4807405 (1456.7 MB) with weight 456143785 (94.88/col)
Tue May 15 19:05:49 2018  sparse part has weight 328985188 (68.43/col)
Tue May 15 19:06:11 2018  matrix starts at (0, 0)
Tue May 15 19:06:12 2018  matrix is 4807229 x 4807405 (1456.7 MB) with weight 456143785 (94.88/col)
Tue May 15 19:06:12 2018  sparse part has weight 328985188 (68.43/col)
Tue May 15 19:06:12 2018  saving the first 48 matrix rows for later
Tue May 15 19:06:12 2018  matrix includes 64 packed rows
Tue May 15 19:06:13 2018  matrix is 4807181 x 4807405 (1411.2 MB) with weight 363261148 (75.56/col)
Tue May 15 19:06:13 2018  sparse part has weight 321855481 (66.95/col)
Tue May 15 19:06:13 2018  using block size 8192 and superblock size 786432 for processor cache size 8192 kB
Tue May 15 19:06:27 2018  commencing Lanczos iteration (8 threads)
Tue May 15 19:06:27 2018  memory use: 1140.4 MB
Tue May 15 19:06:40 2018  linear algebra at 0.0%, ETA 11h29m
Tue May 15 19:06:44 2018  checkpointing every 430000 dimensions
Wed May 16 06:18:18 2018  lanczos halted after 76017 iterations (dim = 4807178)
Wed May 16 06:18:23 2018  recovered 25 nontrivial dependencies
Wed May 16 06:18:23 2018  BLanczosTime: 40791
Wed May 16 06:18:23 2018  
Wed May 16 06:18:23 2018  commencing square root phase
Wed May 16 06:18:23 2018  cannot handle negative leading algebraic polynomial coefficient
Wed May 16 06:18:23 2018  sqrtTime: 0
Wed May 16 06:18:23 2018  elapsed time 12:01:18

But, as shown, the square root phase failed. The square root phase was restarted at day 2 09:37:21 with the modified .fb file and it completed at day 2 10:19:10:

Wed May 16 09:37:21 2018  Msieve v. 1.54 (SVN 1015)
Wed May 16 09:37:21 2018  random seeds: d021314b 0b59fad8
Wed May 16 09:37:21 2018  factoring 10941738641570527421809707322040357612003732945449205990913842131476349984288934784717997257891267332497625752899781833797076537244027146743531593354333897 (155 digits)
Wed May 16 09:37:21 2018  searching for 15-digit factors
Wed May 16 09:37:22 2018  commencing number field sieve (155-digit input)
Wed May 16 09:37:22 2018  R0: -612027504584914645235174827421
Wed May 16 09:37:22 2018  R1: 25879721744003857318699
Wed May 16 09:37:22 2018  A0: -182745817499024369420760271832448384
Wed May 16 09:37:22 2018  A1: 427211473195034674829019757212
Wed May 16 09:37:22 2018  A2: 3743757388243368106451009
Wed May 16 09:37:22 2018  A3: -10289593997537051662
Wed May 16 09:37:22 2018  A4: -15468757262920
Wed May 16 09:37:22 2018  A5: 8954400
Wed May 16 09:37:22 2018  skew 1.00, size 5.406e-15, alpha -7.580, combined = 4.712e-14 rroots = 3
Wed May 16 09:37:22 2018  
Wed May 16 09:37:22 2018  commencing square root phase
Wed May 16 09:37:22 2018  reading relations for dependency 1
Wed May 16 09:37:22 2018  read 2403030 cycles
Wed May 16 09:37:25 2018  cycles contain 8068356 unique relations
Wed May 16 09:40:02 2018  read 8068356 relations
Wed May 16 09:40:35 2018  multiplying 8068356 relations
Wed May 16 09:48:37 2018  multiply complete, coefficients have about 463.52 million bits
Wed May 16 09:48:39 2018  initial square root is modulo 207512621
Wed May 16 09:58:16 2018  GCD is N, no factor found
Wed May 16 09:58:16 2018  reading relations for dependency 2
Wed May 16 09:58:16 2018  read 2403705 cycles
Wed May 16 09:58:19 2018  cycles contain 8076686 unique relations
Wed May 16 10:00:56 2018  read 8076686 relations
Wed May 16 10:01:29 2018  multiplying 8076686 relations
Wed May 16 10:09:30 2018  multiply complete, coefficients have about 464.00 million bits
Wed May 16 10:09:32 2018  initial square root is modulo 211638667
Wed May 16 10:19:09 2018  sqrtTime: 2507
Wed May 16 10:19:10 2018  p78 factor: 102639592829741105772054196573991675900716567808038066803341933521790711307779
Wed May 16 10:19:10 2018  p78 factor: 106603488380168454820927220360012878679207958575989291522270608237193062808643
Wed May 16 10:19:10 2018  elapsed time 00:41:49

Summary from above:

cado-nfs was started at     day 1 08:13:10
sieving completed at        day 1 18:11:49
msieve filtering started at day 1 18:17:05
LA started at               day 1 18:58:32
LA finished at              day 2 06:18:23

Sqrt restarted at           day 2 09:37:21
Sqrt completed at           day 2 10:19:10

Total wall clock time       22:47:02

Compared to the earlier times, this one took slightly longer than the original ggnfs/msieve run with all the same machines.

Originally Posted by EdH

Total wall time:

22:21:21

if my clock math is correct. I think cado-nfs came in at:

27:06:32

[Gimarel]

Originally Posted by VictordeHolland

Could you share the better parameters?

The patches are not very clean.
The msieve patches are against ^/trunk revision 983.
The yafu patches are against ^/branches/wip revision 366.
The yafu patches won't work without the msieve patches and will probably break SNFS.

The values for c145 can probably be optimised. The values for c150 are a complete guess. I don't have values above c150.
The crossover 13e to 14e is about 0.5 to 1.0 digits to low, but I didn't care enough to get more precise values.

The crossover SIQS to GNFS is at about 91 digits with these patches. But yafu tune will generate wrong results.

[VictordeHolland]

Originally Posted by Gimarel

The patches are not very clean.
The msieve patches are against ^/trunk revision 983.
The yafu patches are against ^/branches/wip revision 366.
The yafu patches won't work without the msieve patches and will probably break SNFS.

The values for c145 can probably be optimised. The values for c150 are a complete guess. I don't have values above c150.
The crossover 13e to 14e is about 0.5 to 1.0 digits to low, but I didn't care enough to get more precise values.

The crossover SIQS to GNFS is at about 91 digits with these patches. But yafu tune will generate wrong results.

+/* digits, r/alim, lpbr/a, mfbr/a, r/alambda, siever, min-rels, q-range, sievestart */
+    {105,   700000, 29, 58, 2.50, 12,  9100000,   5000,  500000},
+    {110,   700000, 29, 58, 2.50, 12, 11000000,   5000,  500000},
+    {115,   900000, 29, 58, 2.50, 12, 15200000,   5000,  800000},
+    {120,  1400000, 29, 58, 2.50, 12, 20400000,   5000,  800000},
+    {120,  1400000, 29, 58, 2.50, 13, 17500000,   5000, 1200000},
 +    {125,  2200000, 29, 58, 2.50, 13, 23400000,   5000, 1800000},

Thanks for sharing! I only did a quick test with RSA110 by editing the def-par.txt and using the factmsieve.py script. Using the 12e siever instead of the 13e for 110 digits does indeed seem faster, but I don't understand why would you want to use lpb of 29 for these small composites?? That seems a bit excessive and creates bigger data files and requires more relations??

RSA110 - 2500k @4.0GHz
13e siever - lbp: 27 (defaults from def-par.txt)
1:21:00 (17,739 CPUsec according to ggnfs.log)
7,760,669 raw relations
349123 x 349349 matrix (0:02:24)

13e siever - lbp: 29
1:16:35 (16,704 CPUsec)
8,810,357 raw relations
276548 x 276796 (0:01:34)

12e siever - lbp: 27
1:10:31 (15,759 CPUsec)
7,582,183 raw relations
409071 x 409300 matrix (0:03:33)

12e siever - lbp: 26
1:08:18 (15,434 CPUsec)
5,674,595 raw relations
455269 x 455495 matrix (0:03:56)

PS: If this is too offtopic for the CADO thread or worthy of a new thread that is fine with me.

[VictordeHolland]

Originally Posted by VictordeHolland

RSA-110
Factmsieve(v0.86) + Msieve + GGNFS sievers (with asm routines)

Mon May 14 13:26:50 2018 -> factmsieve.py (v0.86)
Mon May 14 13:26:50 2018 -> This is client 1 of 1
Mon May 14 13:26:50 2018 -> Running on 16 Cores with 2 hyper-threads per Core
Mon May 14 13:26:50 2018 -> Working with NAME = RSA110
Mon May 14 13:26:50 2018 -> Running polynomial selection ...
Mon May 14 13:26:50 2018 -> ./msieve -s ./RSA110.dat.T0 -l ./RSA110.log.T0 -i ./RSA110.ini.T0 -nf ./RSA110.fb.T0 -np 1,1000 -v > ./RSA110.msp.T0
..
Mon May 14 13:28:44 2018 Best score so far: # norm 2.170012e-10 alpha -6.451622 e 1.047e-09 rroots 5
Mon May 14 13:28:44 2018 -> Selected lattice siever: gnfs-lasieve4I13e
Mon May 14 13:28:44 2018 -> entering sieving loop
...
Mon May 14 13:57:57 2018 Found 8210614 relations, 111.7% of the estimated minimum (7350000).

Mon May 14 13:57:58 2018  commencing relation filtering
...
Mon May 14 14:00:47 2018 -> Running matrix solving step
...
Mon May 14 14:02:47 2018  commencing square root phase
...
Mon May 14 14:04:16 2018  p55 factor: 5846418214406154678836553182979162384198610505601062333
Mon May 14 14:04:16 2018  p55 factor: 6122421090493547576937037317561418841225758554253106999

0:02:54 Poly
0:29:13 Sieving
0:02:50 Filtering
0:02:00 LA
0:01:29 SQR
----------
0:38:26 total (2306 seconds)

CADO-NFS 3.0-dev

./cado-nfs.py 35794234179725868774991807832568455403003778024228226193532908190484670252364677411513516111204504060317568667 workdir=/tmp/RSA110
Info:root: Using default parameter file ./parameters/factor/params.c110
Info:root: No database exists yet
Info:root: Set tasks.threads=32 based on detected logical cpus
...
Info:HTTP server: 127.0.0.1 Sending workunit c110_polyselect1_0-5000 to client localhost
...
Info:HTTP server: 127.0.0.1 Sending workunit c110_polyselect1_45000-50000 to client localhost+9
...
Info:Polynomial Selection (root optimized): Finished, best polynomial from file /tmp/RSA110/c110.upload/c110.polyselect2.pfbrex9n.opt_72 has Murphy_E = 2.59e-09
...
Info:Square Root: Factors: 6122421090493547576937037317561418841225758554253106999 5846418214406154678836553182979162384198610505601062333
Info:Polynomial Selection (size optimized): Aggregate statistics:
Info:Polynomial Selection (size optimized): potential collisions: 11711.3
Info:Polynomial Selection (size optimized): raw lognorm (nr/min/av/max/std): 11672/31.850/38.956/44.950/1.139
Info:Polynomial Selection (size optimized): optimized lognorm (nr/min/av/max/std): 11672/31.310/34.551/39.370/0.976
Info:Polynomial Selection (size optimized): Total time: 1176.67
Info:Polynomial Selection (root optimized): Aggregate statistics:
Info:Polynomial Selection (root optimized): Total time: 489.95
Info:Polynomial Selection (root optimized): Rootsieve time: 488.36
Info:Generate Factor Base: Total cpu/real time for makefb: 4.37/0.373342
Info:Generate Free Relations: Total cpu/real time for freerel: 109.26/3.60933
Warning:Lattice Sieving: some stats could not be displayed for sieving (see log file for debug info)
Info:Lattice Sieving: Aggregate statistics:
Info:Lattice Sieving: Total number of relations: 5412839
Info:Lattice Sieving: Average J: 1893.28 for 79582 special-q
Info:Lattice Sieving: Total CPU time: 28220.8s
Info:Filtering - Duplicate Removal, splitting pass: Total cpu/real time for dup1: 18.96/16.6092
Info:Filtering - Duplicate Removal, splitting pass: Aggregate statistics:
Info:Filtering - Duplicate Removal, splitting pass: CPU time for dup1: 16.0s
Info:Filtering - Duplicate Removal, removal pass: Total cpu/real time for dup2: 113.86/54.6661
Warning:Filtering - Duplicate Removal, removal pass: some stats could not be displayed for duplicates2 (see log file for debug info)
Info:Filtering - Singleton removal: Total cpu/real time for purge: 97.19/51.8443
Info:Filtering - Merging: Total cpu/real time for merge: 106.71/89.2541
Info:Filtering - Merging: Total cpu/real time for replay: 9.6/7.87395
Info:Linear Algebra: Total cpu/real time for bwc: 1904.82/190.56
Info:Linear Algebra: Aggregate statistics:
Info:Linear Algebra: Krylov: WCT time 105.61, iteration CPU time 0.01, COMM 0.0, cpu-wait 0.0, comm-wait 0.0 (8000 iterations)
Info:Linear Algebra: Lingen CPU time 110.81, WCT time 10.02
Info:Linear Algebra: Mksol: WCT time 59.48, iteration CPU time 0.01, COMM 0.0, cpu-wait 0.0, comm-wait 0.0 (4000 iterations)
Info:Quadratic Characters: Total cpu/real time for characters: 13.74/2.61752
Info:Square Root: Total cpu/real time for sqrt: 260.73/37.302
Info:HTTP server: Shutting down HTTP server
Info:Complete Factorization: Total cpu/elapsed time for entire factorization: 42899.5/1549.64
6122421090493547576937037317561418841225758554253106999 5846418214406154678836553182979162384198610505601062333

1550 seconds WCT!! Remember those 2300 seconds it took GGNFS?
1550 seconds works out to 25:50 for us mortals.

Rerunning RSA110 with GGNFS/Msieve using the 12e and lpb 26 improved the time only a little bit.


0:01:10 Poly Select
0:22:40 Sieving
0:03:40 Filtering
0:04:04 Linear Algebra
0:03:45 SQR
--------
0:35:19

Even though I shaved off almost 2 min at Poly Select and 6 minutes at Sieving. It had to filter twice (first time barely failed) and the LA took a bit longer. It got a bit unlucky at the SQR (only found the factors at the 3rd dependency).
Total CPUtime spend sieving (35079) is now much closer to CADO (28220).

[Gimarel]

Originally Posted by VictordeHolland

Using the 12e siever instead of the 13e for 110 digits does indeed seem faster, but I don't understand why would you want to use lpb of 29 for these small composites?? That seems a bit excessive and creates bigger data files and requires more relations??

Because it's faster, at least for me.

The relation count for lpb 29 seems to low for me, it should be about 11000000.
Did you notice, that the comment is a bit misleading: The algebraic factor base is set at a different place to 999999999. This will be limited to the beginning of the sieved range by the siever.

Also note, that the parameters are only good, if the sieving starts at the value, that's computed by yafu.

[Gimarel]

I sieved the c145 with the cado siever and the parameters that were used by yafu (with my patches).
The sieving time until a matrix could be built was about 48h. This is almost halve the time of the cado default parameters.

The commandline was like:

las -v -T -T -stats-stderr -I 14 -lim0 6721882 -lpb0 30 -lpb1 30 -mfb0 60 -mfb1 60 -lambda0 2.25 -lambda1 2.25 -poly c145.poly -fb c145.fb -out c145.dat -lim1 4912000 -q0 4912000 -q1 4917000

Note that -lim1 is set to the same value as -q0. The sieving started at 4912000 in 5k steps.

[henryzz]

Originally Posted by Gimarel

I sieved the c145 with the cado siever and the parameters that were used by yafu (with my patches).
The sieving time until a matrix could be built was about 48h. This is almost halve the time of the cado default parameters.

The commandline was like:

las -v -T -T -stats-stderr -I 14 -lim0 6721882 -lpb0 30 -lpb1 30 -mfb0 60 -mfb1 60 -lambda0 2.25 -lambda1 2.25 -poly c145.poly -fb c145.fb -out c145.dat -lim1 4912000 -q0 4912000 -q1 4917000

Note that -lim1 is set to the same value as -q0. The sieving started at 4912000 in 5k steps.

It is worth noting that unlike the ggnfs siever cado can sieve below the fb bound.