View Single Post
Old 2019-04-04, 18:42   #4
VBCurtis's Avatar
Feb 2005
Riverside, CA

22·1,321 Posts

RSA768 was factored with the equivalent of I=16 on CADO (same sieve region as NFS@home's 16fV5 siever). I=17 may be faster, but has a memory footprint too large for most users (I failed to get a single instance to start on a 24GB system a few months ago). Alas, I haven't yet figured out how to test-sieve within CADO; so instead I tried a little test with the 16f siever. "top" reported 3.5GB memory use for rlim=980M, alim=1640M. I also tested rlim=alim=1070M, but memory use only dropped to 2.9GB while yield was more than 10% worse and sec/rel was little changed.
My test-sieve used mfbr=71, lpbr=37, mfba=110, lpba=40.
These settings are a bit tighter than those used by the group that factored RSA-768: They used smaller lim's to save memory but 40LP on both sides, mfbr=110, mfba=140 (4 large primes!). I initially tried 107/39 for a-side, but 110/40 had approximately twice the yield.
#37-40/71-110, lambda 2.7/3.7: dQ=500
#Q=100M  7736 rels, 0.296 sec/rel
#Q=600M  5041 rels, 0.441 sec/rel
#Q=1100M 5154 rels, 0.483 sec/rel
#Q=1600M 3088 rels, 0.571 sec/rel
#Q=2100M 1741 rels, 0.634 sec/rel
#Q=2600M 2818 rels, 0.648 sec/rel
#Q=3100M 2683 rels, 0.674 sec/rel
#Q=3600M 3516 rels, 0.696 sec/rel
#Q=4100M 1574 rels, 0.775 sec/rel
The team that cracked RSA-768 used 40LP on both sides, 3 rational large primes and 4 algebraic large primes. They sieved 64G raw relations, and observed that this was substantial oversieving (the estimated by a factor of 2). So, moving down to 37LP and 2 large primes on r side, with 3 large primes on a side, suggests less than half as many relations would be required; say, somewhere between 25G and 30G relations.
Yield is over 10 from 100M to 1200M, good for ~12G relations.
Yield is over 5 for the rest of the Q-range, say 1200M to 3800M for ~15G relations.
So, as a proof-of-concept, the 16f siever appears sufficient to crack RSA-232. If I had hundreds of cores at my disposal, I'd aim the large-memory cores to CADO with I = 17 to run Q=50M to 200M, and for medium-memory cores I'd use 16f with 3.5GB/core. Once I solve CADO test-sieving, I'll report I=16 memory use and yield.
Sec/rel is measured on a Haswell i7-5820, a 6-core 3.3ghz CPU with 6 other tasks running. At half a second per relation, we're looking at 14 gigacoreseconds, or 450 core-years. This is massively less than the 2000 CPU-years that RSA-768 took, but those were measured on c. 2008 2.2ghz AMD processors. However, my CPU is not 4 times faster than theirs were, which suggests my test-sieving is flawed in some way. I don't see any problem with yields with just 2RLP/3ALP, while the RSA-768 team sieved Q=450M-11G using 3RLP/4ALP; again, this suggests my test-sieving is flawed. Then again, they used rlim=200M & alim =1100M to fit into 2GB/core, which may have impacted yield and efficiency more than I realize. Their matrix was ~190M by 190M, and better param choice + fewer large primes should lead to a yet-smaller matrix for RSA232.
If anyone is interested in taking another baby step toward such a factorization, they are invited to find a better polynomial. Poly select has improved quite a lot in 10 years, so we should be able to beat the RSA-768 score by at least 5%. If we do improve on my poly by 20% or more, a more detailed test-sieve could demonstrate that we need fewer than 400 core-years for sieving, a level possible within this forum.
VBCurtis is offline   Reply With Quote