Discussion related to cado-nfs

[Aurore Guillevic <guillevic@lix.polytechnique.fr>]

Hi,

Here is a possible explanation : the irreducible polynomial that defines the quadratic extension GF(p^2) over GF(p) is not the same in PARI-gp and in cado-nfs.

In PARI:

p = 262086107969265031
ell = 32760763496158129 \\ (largest prime factor of p^2 - 1)
c = ffgen([p,2], X)
g=216232938003097459*c + 190041067314658365
target=117385794987197527*c + 235757958534339998
exponent=11818731183008556
c.mod \\ will print the irreducible polynomial P(x): this is x^2 + x - 4 = x^2 + x + 262086107969265027
fforder(g) == ell
g^exponent == target

In cado-nfs:
the command is
cado-nfs/cado-nfs.py 262086107969265031 -dlp -ell 32760763496158129 -gfpext 2 --workdir=/data/cado-nfs/test
The irreducible polynomial to define GF(p^2) is given in a file p2dd20.py (in /data/cado-nfs/test)
cat p2dd20.poly # (this file is generated at the beginning of the command)

n: 262086107969265031
skew: 1.0
# f
poly0: 1,0,0,0,1
# f lognorm -0.49, skew 1.00, alpha 2.63, E 2.14, exp_E -0.49
# g
poly1: 1529428992,-472061699,1529428992
# g lognorm 21.18, skew 1.00, alpha -0.31, E 20.87, exp_E 21.18
# gcd(f, g) = phi = 1,-34471592128557630,1

the last line is important: the polynomial is named phi.
phi = 1 -34471592128557630*x + x^2
This is not the same as in PARI-GP. A conversion into this representation is needed.

cado-nfs/cado-nfs.py /data/cado-nfs/test/p2dd20.parameters_snapshot.0 target=216232938003097459,190041067314658365
the problem is the representation of the target. It is given modulo x^2 + x - 4, but we would like to use phi.

phi = 1 -34471592128557630*x + x^2
T = Mod(1,p)*phi
P = c.mod
R = polrootsff(T, p, P)[1]
\\ To map something mod phi to mod P, we have  xi = 60470699907903726*c + 47471146018230678
\\ To map something mod P to mod phi, we have  (xi - 47471146018230678)/60470699907903726 = c

u = 1/Mod(60470699907903726,p)
v = - 47471146018230678 * u

xi = 60470699907903726*c + 47471146018230678
c  == 10171266721348391*xi + 212219866433972631

now, generator is g = 216232938003097459*c + 190041067314658365 (216232938003097459,190041067314658365)
this is 216232938003097459*(10171266721348391*xi + 212219866433972631) + 190041067314658365

Mod(216232938003097459,p)*(Mod(10171266721348391,p)*XI + Mod(212219866433972631,p)) + Mod(190041067314658365,p)
%23 = Mod(72670631844203435, 262086107969265031)*XI + Mod(102945478732893391, 262086107969265031)

Consequently we need to give (72670631844203435,102945478732893391) to cado-nfs

Target is
target=117385794987197527*c + 235757958534339998
this becomes

C = Mod(10171266721348391,p)*XI + Mod(212219866433972631,p)
Mod(117385794987197527,p)*C + Mod(235757958534339998,p)

Mod(254505989833957736, 262086107969265031)*XI + Mod(87040225854068861, 262086107969265031)
and we need to give (254505989833957736,87040225854068861) to cado-nfs

Maybe you could try the following:

cado-nfs/cado-nfs.py /data/cado-nfs/test/p2dd20.parameters_snapshot.0 target=72670631844203435,102945478732893391
cado-nfs/cado-nfs.py /data/cado-nfs/test/p2dd20.parameters_snapshot.0 target=254505989833957736,87040225854068861

And also, clearing the cofactor (p^2-1)/ell is needed to obtain exact equality.

For the examples you have (the following is in Sage):
p = 262086107969265031
ell = 32760763496158129 # (largest prime factor of p^2 - 1)
cofact = (p^2 -1)//ell # this is 2096688863754120240, that is, (p-1)*8
Fl = GF(ell)
Fp = GF(p)
Fpx.<X> = Fp[]
phi = 1 -34471592128557630*X + X^2
Fp2.<x> = Fp.extension(phi)

target1=216232938003097459*x + 190041067314658365
log1 = 13394876329845831
target2=117385794987197527*x + 235757958534339998
log2 = 30091716292081506

(target1^log2)^cofact == (target2^log1)^cofact
(target1^(Fl(log2/log1)))^cofact == target2^cofact

Your logarithms are correct, but the elements (target1 and target2) are expressed in an extension defined by phi = X^2-34471592128557630*X+1.

Best regards,

Aurore.

Aurore Guillevic
Chargée d'enseignement, École Polytechnique
Bâtiment Turing, bureau 2042, Palaiseau
Chargée de recherche Inria
Équipe Caramba, bureau B258
Inria Nancy -- Grand Est
615 rue du jardin botanique, CS 20101
54603 Villers-lès-Nancy Cedex France
https://members.loria.fr/AGuillevic/

Le 15/04/2020 à 16:17, Filip Fifka a écrit :

Hello,

I'm trying to compute discrete logarithms in GF(p^2) as outlined by the last section of README.dlp (p = 7 mod 8 and roughly 20 digits).

Cado runs without issues but the computed values seem inconsistent.

Here's an example (generated with PARI/GP):

p = 262086107969265031

ell = 32760763496158129 #(largest prime factor of p^2 - 1)

c = ffgen([p,2])

g=216232938003097459*c + 190041067314658365

x=117385794987197527*c + 235757958534339998

h=11818731183008556

We can check that g is generating the subgroup of order ell in GF(p^2) with fforder(g) and g^h = x.

Now I want to compute h with Cado-nfs using the following commands:

cado-nfs/cado-nfs.py 262086107969265031 -dlp -ell 32760763496158129 -gfpext 2 --workdir=/data/cado-nfs/test

-> Runs and builds the logs of the factor base elements without issue.

cado-nfs/cado-nfs.py /data/cado-nfs/test/p2dd20.parameters_snapshot.0 target=216232938003097459,190041067314658365

-> Info:root: target = 216232938003097459,190041067314658365
    Info:root: log(target) = 13394876329845831

cado-nfs/cado-nfs.py /data/cado-nfs/test/p2dd20.parameters_snapshot.1 target=117385794987197527,235757958534339998

-> Info:root: target = 117385794987197527,235757958534339998
    Info:root: log(target) = 30091716292081506

Now back to PARI/GP: h_cado = Mod(30091716292081506,ell)/Mod(13394876329845831,ell)

g^h_cado isn't equal to x as h_cado != h

What went wrong here ? Is my formatting of the target parameter correct (undocumented, I tried to guess by looking at scripts/descent.py) ? I tried several other examples with different primes but I never seem to get the correct answer.

I run the latest git master pulled a few days ago and can provide log files and factor bases if needed.

Unrelated to this example, I also tried to compute the dlp for the same pair of targets (and same field GF(p^2)) on two different factor bases by running the computations twice in two different workdirs, and the resulting h_cado after rebasing the log(target) to g were different. Is that to be expected ?

Best regards,

Filip

_______________________________________________
Cado-nfs-discuss mailing list
Cado-nfs-discuss@lists.gforge.inria.fr
https://lists.gforge.inria.fr/mailman/listinfo/cado-nfs-discuss