20101216, 18:08  #12 
Nov 2010
3^{2} 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 justbarely enough relations compared to oversieving, and so on. I factored RSA100 a few times more, and RSA120 as well  using a jobdistribution 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 nontrivially divisible numbers. Any other range seems like it will be worseoff 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.) 
20101216, 19:30  #13  
Sep 2009
979_{10} Posts 
Quote:
Distributing sieving work across computers can be done by adhoc scripts, or by infrastructure such as BOINC. There are two BOINCbased sieving grids: * RSALS, using the 14e siever, whose original goal was precisely to speed up factorization of a set of 512bit RSA keys used for signing OS and applications in TIZ80 and TI68k 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). 

20101216, 20:54  #14 
Nov 2010
3^{2} Posts 
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) RSA190 was sieved with specialized programs (AFAIK). 
20101217, 03:21  #15  
Tribal Bullet
Oct 2004
3^{2}·5·79 Posts 
Aw shucks :)
Quote:
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. 

20110515, 02:18  #16 
May 2011
3_{10} Posts 
Hi, if your code is working, may I ask for your favour to factorise this 122digitsemiprime: 87080933638459254990190759549329249427007327139393378403507376787968543052358925725338774979411611152080797622523844393187

20110515, 04:38  #17  
"Bob Silverman"
Nov 2003
North of Boston
7,507 Posts 
Quote:
What is the source of this number? 

20110515, 15:24  #18 
Tribal Bullet
Oct 2004
6743_{8} Posts 
Probably a crackme. Reverse engineers love to give each other little puzzles, but a 512bit madeup RSA key is a rather large puzzle :)

20110515, 16:31  #19 
Dec 2010
Monticello
703_{16} 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) 
20110515, 16:55  #20  
"Bob Silverman"
Nov 2003
North of Boston
1110101010011_{2} Posts 
Quote:
you. Otherwise, you are SOL. 

20110515, 17:09  #21 
Sep 2009
11×89 Posts 
Well, a GNFS task of difficulty 122 is at most two days of work for a fairly recent dualcore computer, between one and two orders of magnitude easier than a 512bit RSA key

20110515, 17:35  #22 
Sep 2008
Kansas
3×7×181 Posts 
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. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Semiprime and nalmost prime candidate for the k's with algebra for the Sierpinski/Riesel problem  sweety439  sweety439  11  20200923 01:42 
Generating a uniform random nbit semiprime  danaj  Programming  17  20170915 16:41 
Factored vs. Completely factored  aketilander  Factoring  4  20120808 18:09 
2,709+ factored  JHansen  Factoring  47  20050629 17:59 
RSA200 factored  xilman  Factoring  23  20050602 03:24 