newb needs help - factoring RSA512 error

barthmaul · 2014-11-03, 09:49

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

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

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

EdH · 2014-11-03, 15:59

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.

VBCurtis · 2014-11-03, 19:21

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.

Dubslow · 2014-11-03, 21:34

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.

debrouxl · 2014-11-04, 06:34

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

VBCurtis · 2014-11-04, 06:57

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.

debrouxl · 2014-11-04, 12:18

Code:

Sat Nov 01 09:13:15 2014  using 20 quadratic characters above 536867844

suggests 29-bit LPs instead

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.

barthmaul · 2014-11-04, 12:38

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

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.

debrouxl · 2014-11-04, 16:20

In fact, msieve has built-in help, accessible through `msieve --help`

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.

VBCurtis · 2014-11-04, 17:02

Quote:

Originally Posted by debrouxl

Code:

Sat Nov 01 09:13:15 2014  using 20 quadratic characters above 536867844

suggests 29-bit LPs instead

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.

Thanks for this explanation!

barthmaul · 2014-11-05, 12:14

Quote:

Originally Posted by debrouxl

In fact, msieve has built-in help, accessible through `msieve --help`

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.

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.

2014-11-04, 12:18	#7
debrouxl Sep 2009 2²×5×7² Posts	Code: Sat Nov 01 09:13:15 2014 using 20 quadratic characters above 536867844 suggests 29-bit LPs instead 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.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Newb who needs help with PC	EddieTheBear	Hardware	19	2015-10-23 13:22
Newb question	PicGrabber	Msieve	20	2014-10-31 20:06
today ,i factoring rsa512 is ok,only 3 day	jackchina	Factoring	7	2012-04-13 17:57
how much time to Factoring rsa512?	wsgtrsys	Factoring	21	2010-07-15 08:16
Newb help (it crashes)	Proggie	Software	4	2005-01-05 07:35

2014-11-03, 15:59	#2
EdH "Ed Hall" Dec 2009 Adirondack Mtns 2²×13×107 Posts	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.

2014-11-03, 19:21	#3
VBCurtis "Curtis" Feb 2005 Riverside, CA 1011011011110₂ Posts	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.

2014-11-03, 21:34	#4
Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 1110000110101₂ Posts	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.

2014-11-04, 06:34	#5
debrouxl Sep 2009 2²·5·7² Posts	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

2014-11-04, 06:57	#6
VBCurtis "Curtis" Feb 2005 Riverside, CA 2·2,927 Posts	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.

2014-11-04, 16:20	#9
debrouxl Sep 2009 2²·5·7² Posts	In fact, msieve has built-in help, accessible through `msieve --help` 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.