Discussion related to cado-nfs

[Pierrick Gaudry <pierrick.gaudry@loria.fr>]

Dear Filip,

Yes, having parameter files is required. And no, this is not so easy to
do it, not only the hint file...

Unfortunately I am busy with other things and won't be able to help you
with this. If you are familiar with the number field sieve algorithm, you
can give it a try. Otherwise, it might be just a waste of your time.

Here is the meaning of a hint file line :
21@1 1 1 I=11 20000,18,36 20000,18,36

To descend a special-q of 21 bits on side 1, use a sieve with
  I=11
  lim0=lim1=20000
  lpb0=lpb1=18
  mfb0=mfb1=36
the first block 20000,18,36 corresponding to side0 and the second to
side1.

The "1 1" in second and third positions can be safely ignored.

Each line gives therefore a rule about how to handle a node in the
descent tree.

I am sorry if all the above is cryptic and really hope to find the time
soon to complete this GF(p^2) DLP support which is still very partial.

Regards,
Pierrick

On Wed, Apr 15, 2020 at 11:38:10PM +0000, Filip Fifka wrote:
> Hi Aurore,
> 
> Thank you for the suggestion. After inspecting the polynomials in PARI and
> cado it indeed turns out that this was the issue as I had exactly the same
> difference regarding the polynomials. Your walk-through for the conversion
> was helpful as well.
> 
> Running cado with the new representations you computed gave the exact h
> (note that in this specific case I chose g and x in PARI to be in the
> subgroup of order ell, so the log modulo ell is the exact logarithm for the
> complete equation and we don't need to project with the cofactor).
> 
> Quick follow-up question: as params.p2dd20 is the only parameter file for
> GF(p^2), should I try to come with alternative parameters if I want to
> experiment with larger primes (25 digits and beyond) or should these work
> reasonably well as long as I don't go too far ? I guess the former option
> would require to tweak the p2dd20.hint file used during the descent as
> well, for which the format is a bit cryptic.
> 
> Best,
> Filip
> 
> On Wed, 15 Apr 2020 at 21:31, Aurore Guillevic <
> guillevic@lix.polytechnique.fr> wrote:
> 
> > 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 Francehttps://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 
> > listCado-nfs-discuss@lists.gforge.inria.frhttps://lists.gforge.inria.fr/mailman/listinfo/cado-nfs-discuss
> >
> > _______________________________________________
> > Cado-nfs-discuss mailing list
> > Cado-nfs-discuss@lists.gforge.inria.fr
> > https://lists.gforge.inria.fr/mailman/listinfo/cado-nfs-discuss
> >

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