Discussion related to cado-nfs

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

OK. For these sizes, experiments are quick. I'll do it in the next few
days.

Pierrick

On Fri, Apr 17, 2020 at 05:15:25AM +0000, Filip Fifka wrote:
> Yes I do. I'm specifically interested in primes around 25-27 digits. I
> don't want to take too much of your time but that would be great.
> 
> Best,
> Filip
> 
> On Fri, 17 Apr 2020 at 05:09, Pierrick Gaudry <pierrick.gaudry@loria.fr>
> wrote:
> 
> > Do you target a particular size ? If yes, I might find the time to
> > produce parameters for just this size.
> >
> > What takes (too) long is to cover all sizes.
> >
> > Regards,
> > Pierrick
> >
> > On Fri, Apr 17, 2020 at 05:07:54AM +0000, Filip Fifka wrote:
> > > Dear Pierrick,
> > >
> > > Thank you for the explanation, I'll give it a try.
> > >
> > > Best regards,
> > > Filip
> > >
> > > On Thu, 16 Apr 2020 at 09:37, Pierrick Gaudry <pierrick.gaudry@loria.fr>
> > > wrote:
> > >
> > > > 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
> > > >
> > > >
> >