Discussion related to cado-nfs

[Filip Fifka <filip.fifka@gmail.com>]

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