newb needs help - factoring RSA512 error
 

Hello,
i'm new in this bussiness and i have a problem with factoring RSA512.
Polynomial selection - 5 days on Tesla K20 , sieving 4 days on 5 servers (7 cores each), found 444870517 relations, 737.5% of the estimated minimum (60323676).
And now i have someting like this :

[CODE]Sat Nov 01 09:09:04 2014 -> Running matrix solving step ...
Sat Nov 01 09:09:04 2014
Sat Nov 01 09:09:04 2014
Sat Nov 01 09:09:04 2014 Msieve v. 1.50 (SVN Official Release)
Sat Nov 01 09:09:04 2014 random seeds: 041eb5f8 8f6798e7
Sat Nov 01 09:09:04 2014 factoring 10807561426505345052016343192843324674003752183584439431855278468457615148415828451132399374576833616654358191612829629246076273020826999666784140736359641 (155 digits)
Sat Nov 01 09:09:05 2014 searching for 15-digit factors
Sat Nov 01 09:09:06 2014 commencing number field sieve (155-digit input)
Sat Nov 01 09:09:06 2014 R0: -1148862696576247991128008723087
Sat Nov 01 09:09:06 2014 R1: 132920060949705133
Sat Nov 01 09:09:06 2014 A0: -175221820052441334929633397566648043896
Sat Nov 01 09:09:06 2014 A1: 1066282257861769640439151209947372
Sat Nov 01 09:09:06 2014 A2: 371117678219451318054521018
Sat Nov 01 09:09:06 2014 A3: 11720645312502938107
Sat Nov 01 09:09:06 2014 A4: -718769358546
Sat Nov 01 09:09:06 2014 A5: 5400
Sat Nov 01 09:09:06 2014 skew 20962266.38, size 7.259e-015, alpha -8.407, combined = 3.530e-012 rroots = 5
Sat Nov 01 09:09:06 2014
Sat Nov 01 09:09:06 2014 commencing linear algebra
Sat Nov 01 09:09:06 2014 read 695609 cycles
Sat Nov 01 09:09:07 2014 cycles contain 1363559 unique relations
Sat Nov 01 09:13:14 2014 read 1363559 relations
Sat Nov 01 09:13:15 2014 using 20 quadratic characters above 536867844
Sat Nov 01 09:13:24 2014 building initial matrix
Sat Nov 01 09:13:29 2014 memory use: 176.6 MB
Sat Nov 01 09:13:30 2014 read 695609 cycles
Sat Nov 01 09:13:30 2014 matrix is 54839 x 695609 (32.7 MB) with weight 493777 ( 0.71/col)
Sat Nov 01 09:13:30 2014 sparse part has weight 218571 ( 0.31/col)
Sat Nov 01 09:13:30 2014 filtering completed in 2 passes
Sat Nov 01 09:13:30 2014 matrix is 34890 x 11904 (1.2 MB) with weight 380655 (31.98/col)
Sat Nov 01 09:13:30 2014 sparse part has weight 169594 (14.25/col)
Sat Nov 01 09:13:30 2014 matrix starts at (0, 0)
Sat Nov 01 09:13:30 2014 matrix is 34890 x 11904 (1.2 MB) with weight 380655 (31.98/col)
Sat Nov 01 09:13:30 2014 sparse part has weight 169594 (14.25/col)
Sat Nov 01 09:13:30 2014 matrix needs more columns than rows; try adding 2-3% more relations[/CODE]

When I try to restart the job (on one server only) i have something like this:
[CODE]Mon Nov 03 08:21:03 2014 -> factmsieve.py (v0.76)
Mon Nov 03 08:21:03 2014 -> This is client 1 of 1
Mon Nov 03 08:21:03 2014 -> Running on 7 Cores with 1 hyper-thread per Core
Mon Nov 03 08:21:03 2014 -> Working with NAME = liczba512
Mon Nov 03 08:21:03 2014 -> Selected lattice siever: gnfs-lasieve4I14e
Mon Nov 03 08:21:03 2014 -> Creating param file to detect parameter changes...
Mon Nov 03 08:21:03 2014 -> Running setup ...
Mon Nov 03 08:21:03 2014 -> Estimated minimum relations needed: 6.03237e+07
Mon Nov 03 08:21:03 2014 -> cleaning up before a restart
Mon Nov 03 08:21:05 2014 -> Running lattice siever ...
Mon Nov 03 08:21:05 2014 -> entering sieving loop
Mon Nov 03 08:21:05 2014 -> Running matrix solving step ...
Mon Nov 03 08:21:05 2014
Mon Nov 03 08:21:05 2014
Mon Nov 03 08:21:05 2014 Msieve v. 1.50 (SVN Official Release)
Mon Nov 03 08:21:05 2014 random seeds: 19fe11e8 b45df540
Mon Nov 03 08:21:05 2014 factoring 10807561426505345052016343192843324674003752183584439431855278468457615148415828451132399374576833616654358191612829629246076273020826999666784140736359641 (155 digits)
Mon Nov 03 08:21:06 2014 searching for 15-digit factors
Mon Nov 03 08:21:07 2014 commencing number field sieve (155-digit input)
Mon Nov 03 08:21:07 2014 R0: -1148862696576247991128008723087
Mon Nov 03 08:21:07 2014 R1: 132920060949705133
Mon Nov 03 08:21:07 2014 A0: -175221820052441334929633397566648043896
Mon Nov 03 08:21:07 2014 A1: 1066282257861769640439151209947372
Mon Nov 03 08:21:07 2014 A2: 371117678219451318054521018
Mon Nov 03 08:21:07 2014 A3: 11720645312502938107
Mon Nov 03 08:21:07 2014 A4: -718769358546
Mon Nov 03 08:21:07 2014 A5: 5400
Mon Nov 03 08:21:07 2014 skew 20962266.38, size 7.259e-015, alpha -8.407, combined = 3.530e-012 rroots = 5
Mon Nov 03 08:21:07 2014
Mon Nov 03 08:21:07 2014 commencing linear algebra
Mon Nov 03 08:21:07 2014 read 11904 cycles
Mon Nov 03 08:21:07 2014 cycles contain 11904 unique relations
Mon Nov 03 08:21:07 2014 read 0 relations
Mon Nov 03 08:21:07 2014 error: cannot locate relation 65531248[/CODE]

How to add 2-3% relations ?
Please help :)

I have run into this when I have done too much over-sieving. Try to cut a 65M chunk out of the 400M+ current file.

I'm with Ed; one day on 5 servers likely would have been sufficient. You could also try building the matrix with target-density=128 to encourage it to work harder in filtering. I would try 100M relations from your file, and target-density 128.

The matrix size for GNFS-155 is usually 4M by 4M to 5M by 5M when not oversieved; yours is less than one-tenth that. Setting target-density to 128 instead of default 70 will build a smaller matrix, but I don't know how small- perhaps 3M by 3M? If you figure out the flags in msieve and try it, please let me know what comes out.

Some people around here might actually be interested in analyzing your massively over-sieved data set; please don't delete anything while filtering with fewer relations. :smile:

100M relations for a 512-bit RSA key would probably still bring filtering to its knees. RSALS, and two later solo 512-bit RSA key factorizations of mine, usually used up to 70M raw relations, which is already sizable oversieving, and reduces the matrix's size quite a bit.

Indeed, the 7x oversieved dataset could be interesting for analysis purposes, though the filtering collapse already occurs with much smaller datasets :smile:

His log suggests 60M minimum relations, which suggests it picked 30-bit large primes, and 75-80M relations minimum would be needed to build any matrix. But I've hacked those settings on my own script, so maybe this is a 29-bit job after all?

OP- My advice assumed the *.fb file contains "SALPMAX 1073741824" and SRLPMAX the same. That number is 2^30. If that number is around 500M (2^29, specifically), then 100M relations is indeed way too many to test out matrix building and the other advice in this thread should be your plan.

[code]Sat Nov 01 09:13:15 2014 using 20 quadratic characters above 536867844[/code]
suggests 29-bit LPs instead :smile:
I've checked my post-processing logs for 29-bit LPs tasks and 30-bit LPs tasks to confirm: the numbers on those lines are always slighly less than 2^(number of bits for single large primes).
All RSALS factorizations, and my own, used 29-bit LPs, so the ~70M raw relations figure holds. A 30-bit LPs task would require ~120-130M raw relations.

My .fb file looks like this :
[CODE]N 10807561426505345052016343192843324674003752183584439431855278468457615148415828451132399374576833616654358191612829629246076273020826999666784140736359641
SKEW 20962266.38
A5 5400
A4 -718769358546
A3 11720645312502938107
A2 371117678219451318054521018
A1 1066282257861769640439151209947372
A0 -175221820052441334929633397566648043896
R1 132920060949705133
R0 -1148862696576247991128008723087
FAMAX 27100000
FRMAX 27100000
SALPMAX 536870912
SRLPMAX 536870912[/CODE]
i know it's a lame question - where can i find a manual for msieve ?
I don't know (yet) how to cut 65m relations (i believe. there's a different method than manually in notepad :) and how to change a target density.

In fact, msieve has built-in help, accessible through `msieve --help` :smile:
Nowadays, in the latest msieve versions, changing the number of relations and target density is done through "filter_maxrels=X" and "target_density=X" arguments following (immediately ?) -nc or -nc1.

[QUOTE=debrouxl;386844][code]Sat Nov 01 09:13:15 2014 using 20 quadratic characters above 536867844[/code]
suggests 29-bit LPs instead :smile:
I've checked my post-processing logs for 29-bit LPs tasks and 30-bit LPs tasks to confirm: the numbers on those lines are always slighly less than 2^(number of bits for single large primes).
All RSALS factorizations, and my own, used 29-bit LPs, so the ~70M raw relations figure holds. A 30-bit LPs task would require ~120-130M raw relations.[/QUOTE]

Thanks for this explanation! :tu:

[QUOTE=debrouxl;386857]In fact, msieve has built-in help, accessible through `msieve --help` :smile:
Nowadays, in the latest msieve versions, changing the number of relations and target density is done through "filter_maxrels=X" and "target_density=X" arguments following (immediately ?) -nc or -nc1.[/QUOTE]
Thank You very much.
Is there a way to use the relations in spairs.save.gz file for msieve ? I don't have a .dat file (GGNFS deleted it after restart) but I have a 30 gb spairs file. I tried gunzip -c spairs.save.gz >> msieve.dat but now i have "error -1 reading relation 0" (and so on) in my msieve.log file.