Factorization of RSA704 - Page 2

xilman · 2012-07-04, 19:21

Quote:

Originally Posted by Dubslow

The smallest is RSA-210, and I'm pretty sure NFS@Home could sieve that, much like B200. RSA-704 was 212 digits.

Agreed, but what's the point?

The CADO people could reasonably claim that it (RSA-704) is the biggest one they've done and useful practice for doing something bigger. If they want to do something bigger RSA-250 would make more sense, IMAO, because it would be a record factorization. Factoring something smaller wouldn't appeal to me. But, there again, I'm not a member of their team and so I'm just making virtually meaningless comments from the sidelines.

Paul

Dubslow · 2012-07-04, 19:40

Quote:

Originally Posted by xilman

Agreed, but what's the point?

OCD?

I'd do it myself if I didn't think that the post-processing was beyond my capabilities. (And also so I can tell my friends I factored an RSA number, that would be pretty cool

)

otchij · 2013-08-04, 00:20

I have the following successful attempt to factor RSA-704 based on the msieve and customized sieving usages. Part of this job was done before knowing of start CADO-NFS factorization of RSA-704. Thus it was a decision to complete job with some new research features:

1) Develop and apply OPENCL version of msieve for polynomial search;
2) Usage of extremely low large prime bounds 2^32 on both sides.

Polynomial selection was done by developed OPENCL msieve based on version 1.49. At the start moment only one GPU (ATI Radeon HD 5970 Black Edition) was available. It takes 7 days in January 2012 to get the following polynomial at the beginning of search area (see poly.log in zip attachment).

The sieving was done from 9 January 2012 to 7 May 2013 using only small free night resources from national grid segment. It was enough to use different customized 2^32 sievers from public ones to get 697616848 raw relations from both algebraic and rational sides for filtering (see filtr.log).

Linear algebra utilized MPI version of msieve (v. 1.51) on 8 nodes (Intel Xeon X5570 2.93GHz, IB QDR) with 64 processes (see solve.log).

Last square root step was quite painful because the usage of Intel icc compiler gives the following error message for dependencies:

Code:

dependency does not form a congruence of squares!

The only found working configuration of msieve for square root RSA-704 is msieve (v.1.52), gcc compiler and new gmp library (v.5.1.2) (see sqrt.log):

Code:

Sat Aug  3 10:18:22 2013  
Sat Aug  3 10:18:22 2013  
Sat Aug  3 10:18:22 2013  Msieve v. 1.52 (SVN 935M)
Sat Aug  3 10:18:22 2013  random seeds: 337c3156 b60ae527
Sat Aug  3 10:18:22 2013  factoring 74037563479561712828046796097429573142593188889231289084936232638972765034028266276891996419625117843995894330502127585370118968098286733173273108930900552505116877063299072396380786710086096962537934650563796359 (212 digits)
Sat Aug  3 10:18:23 2013  no P-1/P+1/ECM available, skipping
Sat Aug  3 10:18:23 2013  commencing number field sieve (212-digit input)
Sat Aug  3 10:18:23 2013  R0: -39027496707248421577379010492365904
Sat Aug  3 10:18:23 2013  R1: 420071037399772421207
Sat Aug  3 10:18:23 2013  A0: -13926959839338064260304606049644539443789930578936745705
Sat Aug  3 10:18:23 2013  A1: 61583281540796946979801933372206079122580034078
Sat Aug  3 10:18:23 2013  A2: 953595681796462639224727873498081249852
Sat Aug  3 10:18:23 2013  A3: -3243948711272672811333799050610
Sat Aug  3 10:18:23 2013  A4: -11075164935077271440363
Sat Aug  3 10:18:23 2013  A5: 11017568767316
Sat Aug  3 10:18:23 2013  A6: 20952
Sat Aug  3 10:18:23 2013  skew 352731087.16, size 1.085e-15, alpha -12.008, combined = 4.777e-16 rroots = 6
Sat Aug  3 10:18:23 2013  
Sat Aug  3 10:18:23 2013  commencing square root phase
Sat Aug  3 10:18:23 2013  handling dependencies 18 to 20
Sat Aug  3 10:18:23 2013  reading relations for dependency 18
Sat Aug  3 10:19:10 2013  read 43131498 cycles
Sat Aug  3 10:20:37 2013  cycles contain 135472694 unique relations
Sat Aug  3 10:39:58 2013  read 135472694 relations
Sat Aug  3 10:57:55 2013  multiplying 135472694 relations
Sat Aug  3 17:59:46 2013  multiply complete, coefficients have about 7875.25 million bits
Sat Aug  3 18:01:25 2013  initial square root is modulo 678434651
Sun Aug  4 00:53:36 2013  sqrtTime: 52513
Sun Aug  4 00:53:37 2013  prp106 factor: 8143859259110045265727809126284429335877899002167627883200914172429324360133004116702003240828777970252499
Sun Aug  4 00:53:37 2013  prp106 factor: 9091213529597818878440658302600437485892608310328358720428512168960411528640933367824950788367956756806141
Sun Aug  4 00:53:37 2013  elapsed time 14:35:15

Best regards!

c10ck3r · 2013-08-04, 01:38

Quote:

Originally Posted by otchij

I have the following successful attempt to factor RSA-704 based on the msieve and customized sieving usages. Part of this job was done before knowing of start CADO-NFS factorization of RSA-704. Thus it was a decision to complete job with some new research features:

1) Develop and apply OPENCL version of msieve for polynomial search;
2) Usage of extremely low large prime bounds 2^32 on both sides.

Polynomial selection was done by developed OPENCL msieve based on version 1.49. At the start moment only one GPU (ATI Radeon HD 5970 Black Edition) was available. It takes 7 days in January 2012 to get the following polynomial at the beginning of search area (see poly.log in zip attachment).

The sieving was done from 9 January 2012 to 7 May 2013 using only small free night resources from national grid segment. It was enough to use different customized 2^32 sievers from public ones to get 697616848 raw relations from both algebraic and rational sides for filtering (see filtr.log).

Linear algebra utilized MPI version of msieve (v. 1.51) on 8 nodes (Intel Xeon X5570 2.93GHz, IB QDR) with 64 processes (see solve.log).

Last square root step was quite painful because the usage of Intel icc compiler gives the following error message for dependencies:

Code:

dependency does not form a congruence of squares!

The only found working configuration of msieve for square root RSA-704 is msieve (v.1.52), gcc compiler and new gmp library (v.5.1.2) (see sqrt.log):

Code:

Sat Aug  3 10:18:22 2013  
Sat Aug  3 10:18:22 2013  
Sat Aug  3 10:18:22 2013  Msieve v. 1.52 (SVN 935M)
Sat Aug  3 10:18:22 2013  random seeds: 337c3156 b60ae527
Sat Aug  3 10:18:22 2013  factoring 74037563479561712828046796097429573142593188889231289084936232638972765034028266276891996419625117843995894330502127585370118968098286733173273108930900552505116877063299072396380786710086096962537934650563796359 (212 digits)
Sat Aug  3 10:18:23 2013  no P-1/P+1/ECM available, skipping
Sat Aug  3 10:18:23 2013  commencing number field sieve (212-digit input)
Sat Aug  3 10:18:23 2013  R0: -39027496707248421577379010492365904
Sat Aug  3 10:18:23 2013  R1: 420071037399772421207
Sat Aug  3 10:18:23 2013  A0: -13926959839338064260304606049644539443789930578936745705
Sat Aug  3 10:18:23 2013  A1: 61583281540796946979801933372206079122580034078
Sat Aug  3 10:18:23 2013  A2: 953595681796462639224727873498081249852
Sat Aug  3 10:18:23 2013  A3: -3243948711272672811333799050610
Sat Aug  3 10:18:23 2013  A4: -11075164935077271440363
Sat Aug  3 10:18:23 2013  A5: 11017568767316
Sat Aug  3 10:18:23 2013  A6: 20952
Sat Aug  3 10:18:23 2013  skew 352731087.16, size 1.085e-15, alpha -12.008, combined = 4.777e-16 rroots = 6
Sat Aug  3 10:18:23 2013  
Sat Aug  3 10:18:23 2013  commencing square root phase
Sat Aug  3 10:18:23 2013  handling dependencies 18 to 20
Sat Aug  3 10:18:23 2013  reading relations for dependency 18
Sat Aug  3 10:19:10 2013  read 43131498 cycles
Sat Aug  3 10:20:37 2013  cycles contain 135472694 unique relations
Sat Aug  3 10:39:58 2013  read 135472694 relations
Sat Aug  3 10:57:55 2013  multiplying 135472694 relations
Sat Aug  3 17:59:46 2013  multiply complete, coefficients have about 7875.25 million bits
Sat Aug  3 18:01:25 2013  initial square root is modulo 678434651
Sun Aug  4 00:53:36 2013  sqrtTime: 52513
Sun Aug  4 00:53:37 2013  prp106 factor: 8143859259110045265727809126284429335877899002167627883200914172429324360133004116702003240828777970252499
Sun Aug  4 00:53:37 2013  prp106 factor: 9091213529597818878440658302600437485892608310328358720428512168960411528640933367824950788367956756806141
Sun Aug  4 00:53:37 2013  elapsed time 14:35:15

Best regards!

Umm...this number was factored some 14 months ago...

frmky · 2013-08-04, 02:56

Quote:

Originally Posted by otchij

I have the following successful attempt to factor RSA-704 based on the msieve and customized sieving usages. Part of this job was done before knowing of start CADO-NFS factorization of RSA-704. Thus it was a decision to complete job with some new research features:

Nice. What sieving parameters, sieve binary, and range of q did you use?

debrouxl · 2013-08-04, 06:00

Nice indeed

Filtering removed little excess, there wasn't much oversieving, but that's partially a consequence of a significant duplicate rate:

Code:

found 287426789 duplicates and 410210478 unique relations

According to the job file contained in the ZIP attached to the post above, the sieving parameters were:

Code:

rlim: 565600000
alim: 282799999
lpbr: 32
lpba: 32
mfbr: 96
mfba: 67
rlambda: 3.6
alambda: 2.6
q0: 282800000
qintsize: 10000
#q1:282810000

That doesn't answer for sieve binary, and probably does not answer for range of q either, though.

Any chance the OpenCL polynomial selection code could be upgraded to contemporary msieve (which has a completely different Makefile, etc.) and integrated upstream, in collaboration with jasonp ?

jasonp · 2013-08-04, 11:49

Quote:

Originally Posted by c10ck3r

Umm...this number was factored some 14 months ago...

Read the reasons he proceeded anyway...

otchij · 2013-08-04, 13:33

Quote:

Originally Posted by frmky

Nice. What sieving parameters, sieve binary, and range of q did you use?

All used sievers work under linux x86_64 with sieving region parameter I=16.

Sieving was done according to the following scheme:

1) algebraic side with special q from alim=282800000 to lpba=2^32 using customized gnfs-lasieve4I16 (up to 2^31) and binary BOINC lasievef (up to 2^32);

2) rational side with special q from rlim=565600000 to lpbr=2^32 using binary BOINC lasievef from NFS@Home;

3) again on algebraic side with special q from lpba=2^32 to 5600M using customized las from CADO-NFS.

First two steps give 96% of useful relations over unique ideals. Implementation of last third step with ratio 110% was enough to complete filtering and start to build matrix.

Special research should be done to clarify whether the usage of lpba=lpbr=2^33 for RSA-704 be faster or not in total timing?

otchij · 2013-08-04, 13:36

Quote:

Originally Posted by debrouxl

Any chance the OpenCL polynomial selection code could be upgraded to contemporary msieve (which has a completely different Makefile, etc.) and integrated upstream, in collaboration with jasonp ?

Porting of msieve version 1.49 to OPENCL was not difficult. The only missing component was multiple-precision arithmetic. OPENCL version of msieve exists in whole development tree and doesn't conflict with CUDA because of usage special OCL target in Makefile:

Code:

make x86_64 OCL=1

For new 1.52 version with extra radix sorting on GPU porting to OPENCL requires special efforts.

bai · 2013-08-08, 04:05

Congratulations for the factorization. The root property of the polynomial is pretty good. Do you still have the raw polynomial (say before size/root optimization)?

Quote:

Originally Posted by otchij

Polynomial selection was done by developed OPENCL msieve based on version 1.49. At the start moment only one GPU (ATI Radeon HD 5970 Black Edition) was available. It takes 7 days in January 2012 to get the following polynomial at the beginning of search area (see poly.log in zip attachment).

Shi

otchij · 2013-08-25, 21:38

Quote:

Originally Posted by bai

Congratulations for the factorization. The root property of the polynomial is pretty good. Do you still have the raw polynomial (say before size/root optimization)?
Shi

Each msieve run for searching polynomial was done in temporary directory. Only final outputs of msieve are available currently.

The best polynomial with Murphy 7.673e-16

Quote:

R0: -13809389165368716253128053782111564
R1: 1833678692857438123387
A0: 49530222010674969328191427797117813757970214195
A1: 191331813520448676883521878200795262403315
A2: 95972834230111630003811915807608695
A3: -46224686466137367034601959619
A4: -2797391562967354298194
A5: 1444998931179880
A6: 10675728
skew 4688427.96, size 1.940e-15, alpha -10.058, combined = 7.673e-16 rroots = 4

was found later on after start of sieving

2013-08-04, 06:00	#17
debrouxl Sep 2009 977 Posts	Nice indeed Filtering removed little excess, there wasn't much oversieving, but that's partially a consequence of a significant duplicate rate: Code: found 287426789 duplicates and 410210478 unique relations According to the job file contained in the ZIP attached to the post above, the sieving parameters were: Code: rlim: 565600000 alim: 282799999 lpbr: 32 lpba: 32 mfbr: 96 mfba: 67 rlambda: 3.6 alambda: 2.6 q0: 282800000 qintsize: 10000 #q1:282810000 That doesn't answer for sieve binary, and probably does not answer for range of q either, though. Any chance the OpenCL polynomial selection code could be upgraded to contemporary msieve (which has a completely different Makefile, etc.) and integrated upstream, in collaboration with jasonp ?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Factorization of RSA-180	Robert Holmes	Factoring	19	2010-11-08 18:46
Factorization on 2^p +1	kurtulmehtap	Math	25	2010-09-12 14:13
RSA704, ggnfs? (good polynoms?)	Random_zh	Factoring	8	2006-12-13 13:13
Factorization of 7,254+	dleclair	NFSNET Discussion	1	2006-03-21 05:11
Factorization of 11,212+	Wacky	NFSNET Discussion	1	2006-03-20 23:43