mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2021-08-03, 15:39   #1
AuroreGuillevic
 
"Aurore Guillevic"
Aug 2021

3 Posts
Default 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.<x> = ZZ[]
f0 = ZZx((R[0]).list())
f1 = ZZx((R[1]).list())
f2 = ZZx((R[2]).list())
f3 = ZZx((R[3]).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
AuroreGuillevic is offline   Reply With Quote
Old 2021-08-03, 16:28   #2
charybdis
 
charybdis's Avatar
 
Apr 2020

53910 Posts
Default

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.
charybdis is offline   Reply With Quote
Old 2021-08-05, 07:13   #3
AuroreGuillevic
 
"Aurore Guillevic"
Aug 2021

3 Posts
Default

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.
AuroreGuillevic is offline   Reply With Quote
Old 2021-08-08, 14:42   #4
charybdis
 
charybdis's Avatar
 
Apr 2020

72·11 Posts
Default

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.
charybdis is offline   Reply With Quote
Old 2021-08-14, 08:54   #5
AuroreGuillevic
 
"Aurore Guillevic"
Aug 2021

3 Posts
Default

Thanks, I will try with cado-nfs and these parameters next week.
AuroreGuillevic is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
SNFS polynomials via lindep fivemack YAFU 22 2012-03-12 18:48
SNFS polynomials. chris2be8 FactorDB 1 2012-03-10 16:49
SNFS polynomials for k*b^n+-1 mdettweiler Factoring 15 2010-01-14 21:13
SNFS 200 parameters JoeCrump Factoring 3 2009-12-06 14:50
SNFS parameters for M2376 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.