mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2014-11-03, 09:49   #1
barthmaul
 
Nov 2014

3 Posts
Default 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
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 :)
barthmaul is offline   Reply With Quote
Old 2014-11-03, 15:59   #2
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

485610 Posts
Default

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.
EdH is offline   Reply With Quote
Old 2014-11-03, 19:21   #3
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

10101010111112 Posts
Default

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.
VBCurtis is offline   Reply With Quote
Old 2014-11-03, 21:34   #4
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

11100001101012 Posts
Default

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.
Dubslow is offline   Reply With Quote
Old 2014-11-04, 06:34   #5
debrouxl
 
debrouxl's Avatar
 
Sep 2009

17228 Posts
Default

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
debrouxl is offline   Reply With Quote
Old 2014-11-04, 06:57   #6
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

5,471 Posts
Default

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.
VBCurtis is offline   Reply With Quote
Old 2014-11-04, 12:18   #7
debrouxl
 
debrouxl's Avatar
 
Sep 2009

2×3×163 Posts
Default

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.
debrouxl is offline   Reply With Quote
Old 2014-11-04, 12:38   #8
barthmaul
 
Nov 2014

3 Posts
Default

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.
barthmaul is offline   Reply With Quote
Old 2014-11-04, 16:20   #9
debrouxl
 
debrouxl's Avatar
 
Sep 2009

2·3·163 Posts
Default

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.
debrouxl is offline   Reply With Quote
Old 2014-11-04, 17:02   #10
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

10101010111112 Posts
Default

Quote:
Originally Posted by debrouxl View Post
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!
VBCurtis is offline   Reply With Quote
Old 2014-11-05, 12:14   #11
barthmaul
 
Nov 2014

310 Posts
Default

Quote:
Originally Posted by debrouxl View Post
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.
barthmaul is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 12:02.


Sun Sep 25 12:02:21 UTC 2022 up 38 days, 9:30, 0 users, load averages: 0.87, 1.02, 1.05

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔