mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2010-12-16, 18:08   #12
tal
 
Nov 2010

32 Posts
Default

Hey Jason, I didn't want to make a new thread - but I had a followup question. First off, I have to say the msieve code is gorgeous. After reading a lot of code in a lot of different open source projects I have a history of hating "other people's code" - but this is a breath of fresh air; it's downright enjoyable to read.

Since my last post, I kept a lot of logs on sieving times across my various machines, as well as the final combine - comparing results on different computers, results when I have just-barely enough relations compared to oversieving, and so on. I factored RSA100 a few times more, and RSA120 as well - using a job-distribution system I finished the sieving (actually overseiving by 20%) in under an hour. I'm spending a lot of time trying to get a good distribution system set up, so polynomial selection and sieving can be done very quickly on a massive scale. Because sieving is completely parallelizable I envision sieving 512 bit numbers in a day or less, completely automated.

Now I'm spending time looking closely at the polynomial search phase, and how to distribute it - looking closely at the behavior when you specify a range using -np X,Y. Based on a lot of reading and and a few assumptions, it seems the best way to split the polynomial search range is into the ranges generated by msieve in stage1.c:search_coeffs - where you're only going into search_coeffs_core when you have a batch of at least 40 non-trivially divisible numbers. Any other range seems like it will be worse-off at finding a possble polynomial, because the batch won't be full. Is that correct? (I have four paragraphs worth of explanation into how I came up with that... but decided to spare it unless needed.)
tal is offline   Reply With Quote
Old 2010-12-16, 19:30   #13
debrouxl
 
debrouxl's Avatar
 
Sep 2009

97910 Posts
Default

Quote:
Because sieving is completely parallelizable I envision sieving 512 bit numbers in a day or less, completely automated.
Given enough dozens of cores, 512-bit RSA keys (a.k.a "GNFS tasks of difficulty 154-155") can definitely be sieved enough in less than 24h per key.

Distributing sieving work across computers can be done by ad-hoc scripts, or by infrastructure such as BOINC. There are two BOINC-based sieving grids:
* RSALS, using the 14e siever, whose original goal was precisely to speed up factorization of a set of 512-bit RSA keys used for signing OS and applications in TI-Z80 and TI-68k calculators;
* NFS@Home, using the 15e/16e/16f/16g sievers for harder factorizations, currently ramping up to the hardest factorizations ever performed using open source software (SNFS difficulty > 300).
debrouxl is offline   Reply With Quote
Old 2010-12-16, 20:54   #14
tal
 
Nov 2010

32 Posts
Default

Quote:
Originally Posted by debrouxl View Post
using the 15e/16e/16f/16g sievers for harder factorizations
This is the first I've heard of 16f/16g sievers... And a regex across ggnfs source doesn't mention them... Could you elaborate on where they come from?

Based on the factmsieve script, the sievers are (generally) to be used as 11 => <95 digits, 12 => <110 digits, 13 => <140 digits, 14 => <158 digits, 15 => <185 digits, 16 => <999 digits. I'm curious where these come in, since (I thought) RSA-190 was sieved with specialized programs (AFAIK).
tal is offline   Reply With Quote
Old 2010-12-17, 03:21   #15
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

32·5·79 Posts
Default

Quote:
Originally Posted by tal View Post
First off, I have to say the msieve code is gorgeous
Aw shucks :)
Quote:
Now I'm spending time looking closely at the polynomial search phase, and how to distribute it - looking closely at the behavior when you specify a range using -np X,Y. Based on a lot of reading and and a few assumptions, it seems the best way to split the polynomial search range is into the ranges generated by msieve in stage1.c:search_coeffs - where you're only going into search_coeffs_core when you have a batch of at least 40 non-trivially divisible numbers. Any other range seems like it will be worse-off at finding a possble polynomial, because the batch won't be full.
Larger batches are better but it's not vital to chop the range into optimal-size pieces. If you just make every range larger than a few thousand, you're pretty much guaranteed to have several maximum-size batches.

Also, jrk and I have been working on much better poly selection code, especially for CPUs, and if you're gearing up for bigger jobs then you can play around with the specialq branch. The different algorithm used there doesn't lose efficiency if you give it one leading coefficient at a time.
jasonp is offline   Reply With Quote
Old 2011-05-15, 02:18   #16
Hian
 
May 2011

310 Posts
Default

Hi, if your code is working, may I ask for your favour to factorise this 122-digit-semiprime: 87080933638459254990190759549329249427007327139393378403507376787968543052358925725338774979411611152080797622523844393187
Hian is offline   Reply With Quote
Old 2011-05-15, 04:38   #17
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

7,507 Posts
Default

Quote:
Originally Posted by Hian View Post
Hi, if your code is working, may I ask for your favour to factorise this 122-digit-semiprime: 87080933638459254990190759549329249427007327139393378403507376787968543052358925725338774979411611152080797622523844393187
If you have not factored it, how do you know it is a P_2?

What is the source of this number?
R.D. Silverman is offline   Reply With Quote
Old 2011-05-15, 15:24   #18
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

67438 Posts
Default

Probably a crackme. Reverse engineers love to give each other little puzzles, but a 512-bit made-up RSA key is a rather large puzzle :)
jasonp is offline   Reply With Quote
Old 2011-05-15, 16:31   #19
Christenson
 
Christenson's Avatar
 
Dec 2010
Monticello

70316 Posts
Default

Student question, ignoring the obvious ethics issues raised by Jason:
Suppose I know nothing of Hian's number. How, besides feeding it to TF, or otherwise factoring it, would I show that it was indeed a semiprime? (I'm still working on MPQS as an introduction to NFS)
Christenson is offline   Reply With Quote
Old 2011-05-15, 16:55   #20
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

11101010100112 Posts
Default

Quote:
Originally Posted by Christenson View Post
Student question, ignoring the obvious ethics issues raised by Jason:
Suppose I know nothing of Hian's number. How, besides feeding it to TF, or otherwise factoring it, would I show that it was indeed a semiprime? (I'm still working on MPQS as an introduction to NFS)
If *he* knows the factors then he can conduct a ZKP with you to convince
you. Otherwise, you are SOL.
R.D. Silverman is offline   Reply With Quote
Old 2011-05-15, 17:09   #21
debrouxl
 
debrouxl's Avatar
 
Sep 2009

11×89 Posts
Default

Well, a GNFS task of difficulty 122 is at most two days of work for a fairly recent dual-core computer, between one and two orders of magnitude easier than a 512-bit RSA key
debrouxl is offline   Reply With Quote
Old 2011-05-15, 17:35   #22
RichD
 
RichD's Avatar
 
Sep 2008
Kansas

3×7×181 Posts
Default

Quote:
Originally Posted by Hian View Post
Hi, if your code is working, ...
Why don't you try it and let us know how it works. It is a demo program freely available to anyone that wants to use it.

The author along with several contributors read this forum. If you could report back with parameters selected and timings, it might be helpful for others to see.
RichD is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Semiprime and n-almost prime candidate for the k's with algebra for the Sierpinski/Riesel problem sweety439 sweety439 11 2020-09-23 01:42
Generating a uniform random n-bit semiprime danaj Programming 17 2017-09-15 16:41
Factored vs. Completely factored aketilander Factoring 4 2012-08-08 18:09
2,709+ factored JHansen Factoring 47 2005-06-29 17:59
RSA-200 factored xilman Factoring 23 2005-06-02 03:24

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


Sun Jan 29 02:31:53 UTC 2023 up 164 days, 26 secs, 0 users, load averages: 1.28, 1.04, 1.11

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, 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.

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