 mersenneforum.org SNFS integer factoring with Joux-Lercier polynomials, how to find optimized sieve parameters?
 Register FAQ Search Today's Posts Mark Forums Read 2021-08-03, 15:39 #1 AuroreGuillevic   "Aurore Guillevic" Aug 2021 3 Posts SNFS integer factoring with Joux-Lercier polynomials, how to find optimized sieve parameters? Hi, I'm interested in ianteger factoring of a special form. In pairing-based cryptography, there are numbers of the form N = (p^4-p^2+1)/r, for example these parameters come from the BLS12-381 elliptic curve: Code: r = 52435875175126190479447740508185965837690552500527637822603658699938581184513 p = 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787 N = 4893928114585159410883253572318349434697260627536543127673143787635577013247573657951145569649455045371933135273331436655020524457945919286800884612463535847205871396556049495795446161178202464289525760157481578764179879456252000021461149480913048298580688352512594533579025647331945356418790935689117298357778419459780374425317529106012206555148879480645692101032144730178994813561 Thanks to ECM, it is possible to get these small factors, and a composite unfactored 267 digits (886 bits) number: Code: N == 4513 * 584529700689659162521 * 165391339247941725652149853 * 59725043846501295875107579177 * 411704828694123300223991585955463801 * 456173935631752304885650486765112604850199392611702201661195921228133867409383701253115176518121975048107351746982365740047344277697718117371458565486402798760550777458823612791406155300612996683841366608175777157226663453314676448557207068297461591565950753048237397 ECM was run to search for prime factors of up to 60 digits (200 bits). Factoring a 267-digit number with GNFS is out of reach now. But maybe with SNFS? The number does not have a 2^n-1 shape, however this is possible to obtain two non-linear polynomials with the Joux-Lercier technique, SageMath code below: Code: N0 = 456173935631752304885650486765112604850199392611702201661195921228133867409383701253115176518121975048107351746982365740047344277697718117371458565486402798760550777458823612791406155300612996683841366608175777157226663453314676448557207068297461591565950753048237397 M = matrix(ZZ, 4, 4, [N0,0,0,0, -p,1,0,0, 0,-p,1,0, 0,0,-p,1]) R = M.LLL() ZZx. = ZZ[] f0 = ZZx((R).list()) f1 = ZZx((R).list()) f2 = ZZx((R).list()) f3 = ZZx((R).list()) f = 6760297223379314085829228193717083303698063976104735049266489470370*x^3 - 390640595389483974920068455489794437727032266089936615110475658728*x^2 - 4606053420600359516142919974697553454025603172815941707504022110667*x - 6593767881369371137009764629718637135710033040745402390803874245259 f == -f0 - 2*f2 + f3 g = x^4 - x^2 + 1 assert ((f.resultant(g)) % N0) == 0 A side remark: Joux--Lercier polynomial selection with LLL is working on these inputs because cofactors of (p^4-p^2+1) are known. But factoring a composite number of the form a^4-a^2+1 with a Joux-Lercier polynomial selection, without knowing already cofactors of a^4-a^2+1, is not possible: LLL will not find a short vector, as the shortest vector is (x-a). Here is a polynomial file in cado-nfs format. How can I find optimized parameters to run SNFS on this number? Cado-nfs only has parameters for SNFS with one rational side, such as the 9-th Fermat number, at cado-nfs/parameters/factor/parameters.F9 Code: # Special-NFS for the cofactor of (p^4-p^2+1)/r for the BLS12-381 curve # deg 3: 6760297223379314085829228193717083303698063976104735049266489470370*x^3 + 390640595389483974920068455489794437727032266089936615110475658728*x^2 - 4606053420600359516142919974697553454025603172815941707504022110667*x + 6593767881369371137009764629718637135710033040745402390803874245259 # deg 4: x^4-x^2+1 # resultant of the two polys is 9*N # n: 456173935631752304885650486765112604850199392611702201661195921228133867409383701253115176518121975048107351746982365740047344277697718117371458565486402798760550777458823612791406155300612996683841366608175777157226663453314676448557207068297461591565950753048237397 Y3: 6593767881369371137009764629718637135710033040745402390803874245259 Y2: -4606053420600359516142919974697553454025603172815941707504022110667 Y1: 390640595389483974920068455489794437727032266089936615110475658728 Y0: 6760297223379314085829228193717083303698063976104735049266489470370 c4: 1 c3: 0 c2: -1 c1: 0 c0: 1 skew: 0.995 # lognorm: 153.47, alpha: -2.66 (proj: -0.01), E: 150.81, nr: 1 # lognorm: -0.62, alpha: 2.57 (proj: -0.00), E: 1.95, nr: 0 # MurphyE(Bf=1.000e+07,Bg=5.000e+06,area=1.000e+16)=5.514e-20 Last fiddled with by LaurV on 2021-08-04 at 06:49 Reason: link to criptocoin blog removed, not relevant for the question   2021-08-03, 16:28 #2 charybdis   Apr 2020 53910 Posts Let's try to compare this to something we know how to deal with: an SNFS job with similar-sized norms but a linear rational polynomial. One of your polynomials is quartic with small coefficients, so we can compare to SNFS quartics which will have similar algebraic norms. For a normal SNFS job, the rational norm is b*g(a/b), but for your job it is b^3*g(a/b). Guesstimating that typical values of b will be on the order of 10^8, we're making the rational norm about 16 orders of magnitude larger, so your job is comparable to a "normal" quartic SNFS with the coefficients of the rational polynomial being ~10^83 rather than ~10^67. This would be a difficulty-332 quartic which unfortunately is totally out of reach.   2021-08-05, 07:13 #3 AuroreGuillevic   "Aurore Guillevic" Aug 2021 3 Posts Hi, Thanks for the very quick reply. This is unfortunate that it is out of reach. What about a smaller instance of such (p^4-p^2+1)/r number to factor with SNFS? Here is an example that can be done with GNFS, and I'm curious to know if SNFS could work faster. This one is for BN curves (other pairing-friendly curves). It is not relevant for cryptography as the sizes are too small, but it provides a reachable example. Code: u=ZZ(-0x4010000001) p = 36*u**4 + 36*u**3 + 24*u**2 + 6*u + 1 r = 36*u**4 + 36*u**3 + 18*u**2 + 6*u + 1 N = (p**4 - p**2 + 1) // r N0 = N // (13 * 1880653 * 550434037) N0 == 652702273337486118591289246502527198675752000661284402036387450936642895344974801892355337469920066571976037508566767438517329 N0 is 418 bits long (126 digits). One can factor N0 with ECM or with GNFS, one obtains Code: ... Info:Complete Factorization / Discrete logarithm: Total cpu/elapsed time for entire factorization: 1.64671e+06/13370.6 171145804004108305381291235737889101601398915679755263399264230968820309060043793 3813720570805336190699180685739875776775769153 It is possible to obtain degree 4 + degree 1 SNFS polynomials: Code: # Special-NFS for the cofactor of (p^4-p^2+1)/r for the BN-158 curve # deg 1: # x - p where p = 206327671360737302491015800744139033450591027219 # deg 4: # x^4-x^2+1 # resultant of the two polys is r * 13 * 1880653 * 550434037 * n # where r = 206327671360737302491015346511080613560608358413 # n: 652702273337486118591289246502527198675752000661284402036387450936642895344974801892355337469920066571976037508566767438517329 Y1: 1 Y0: -206327671360737302491015800744139033450591027219 c4: 1 c3: 0 c2: -1 c1: 0 c0: 1 skew: 1.060 # lognorm: -0.60, alpha: 2.57 (proj: -0.00), E: 1.97, nr: 0 # MurphyE(Bf=1.000e+07,Bg=5.000e+06,area=1.000e+16)=1.154e-11 # MurphyE(Bf=1.342e+08,Bg=1.342e+08,area=1.236e+14)=3.335e-08 It is also possible to get degree 4 + degree 3 SNFS polynomials: Code: # Special-NFS for the cofactor of (p^4-p^2+1)/r for the BN-158 curve # deg 3: # 20396385982555374779626924573863*x^3 + 8632836133516405871487584759740*x^2 + 10770692399320472684513624555244*x - 10825312190237491314420268152990 # deg 4: # x^4-x^2+1 # resultant of the two polys is n # n: 652702273337486118591289246502527198675752000661284402036387450936642895344974801892355337469920066571976037508566767438517329 Y3: 20396385982555374779626924573863 Y2: 8632836133516405871487584759740 Y1: 10770692399320472684513624555244 Y0: -10825312190237491314420268152990 c4: 1 c3: 0 c2: -1 c1: 0 c0: 1 skew: 0.932 # lognorm: 71.54, alpha: -0.10 (proj: -0.41), E: 71.44, nr: 1 # lognorm: -0.60, alpha: 2.57 (proj: -0.00), E: 1.97, nr: 0 # MurphyE(Bf=1.000e+07,Bg=5.000e+06,area=1.000e+16)=1.322e-11 # MurphyE(Bf=1.342e+08,Bg=1.342e+08,area=1.236e+14)=7.681e-08 I'm interested in comparing the two.   2021-08-08, 14:42 #4 charybdis   Apr 2020 72·11 Posts Apologies for not seeing this sooner. The first SNFS polynomial is a standard quartic of difficulty 190. This is easily doable on a single machine, but it's still much harder than 126-digit GNFS because quartic polynomials are suboptimal at this size. For the degree 3+4 polynomial, we'll try and estimate the equivalent degree 1+4 difficulty as before. This is smaller so maybe a typical b value is 10^6 or 10^7 rather than 10^8. So the difficulty is comparable to a standard quartic with rational coefficients about 13 digits larger, which would be difficulty 178. This is better than the first SNFS polynomial but I still would expect it to be substantially slower than the GNFS job, maybe comparable to GNFS-140. If you want to try it out, take 140-digit GNFS parameters and skew them towards the rational side (well, not really rational anymore) by adding tasks.sieve.sqside = 0 and making lpb0, mfb0, lim0 larger than lpb1, mfb1, lim1.   2021-08-14, 08:54 #5 AuroreGuillevic   "Aurore Guillevic" Aug 2021 3 Posts Thanks, I will try with cado-nfs and these parameters next week.  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post fivemack YAFU 22 2012-03-12 18:48 chris2be8 FactorDB 1 2012-03-10 16:49 mdettweiler Factoring 15 2010-01-14 21:13 JoeCrump Factoring 3 2009-12-06 14:50 fivemack ElevenSmooth 35 2008-03-28 20:06

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

Sat Nov 27 02:50:26 UTC 2021 up 126 days, 21:19, 0 users, load averages: 1.20, 1.28, 1.27 