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
[/CODE]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
[/CODE]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
[/CODE]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
[/CODE]

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.

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
[/CODE]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
[/CODE]

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
[/CODE]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
[/CODE]I'm interested in comparing the two.