mersenneforum.org Factored my first SemiPrime -Some Questions
 Register FAQ Search Today's Posts Mark Forums Read

 2010-12-16, 18:08 #12 tal   Nov 2010 32 Posts 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.)
2010-12-16, 19:30   #13
debrouxl

Sep 2009

97910 Posts

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).

2010-12-16, 20:54   #14
tal

Nov 2010

32 Posts

Quote:
 Originally Posted by debrouxl 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).

2010-12-17, 03:21   #15
jasonp
Tribal Bullet

Oct 2004

32·5·79 Posts

Quote:
 Originally Posted by tal 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.

 2011-05-15, 02:18 #16 Hian   May 2011 310 Posts Hi, if your code is working, may I ask for your favour to factorise this 122-digit-semiprime: 87080933638459254990190759549329249427007327139393378403507376787968543052358925725338774979411611152080797622523844393187
2011-05-15, 04:38   #17
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

7,507 Posts

Quote:
 Originally Posted by Hian 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?

 2011-05-15, 15:24 #18 jasonp Tribal Bullet     Oct 2004 67438 Posts 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 :)
 2011-05-15, 16:31 #19 Christenson     Dec 2010 Monticello 70316 Posts 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)
2011-05-15, 16:55   #20
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

11101010100112 Posts

Quote:
 Originally Posted by Christenson 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.

 2011-05-15, 17:09 #21 debrouxl     Sep 2009 11×89 Posts 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
2011-05-15, 17:35   #22
RichD

Sep 2008
Kansas

3×7×181 Posts

Quote:
 Originally Posted by Hian 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post sweety439 sweety439 11 2020-09-23 01:42 danaj Programming 17 2017-09-15 16:41 aketilander Factoring 4 2012-08-08 18:09 JHansen Factoring 47 2005-06-29 17:59 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