Discussion related to cado-nfs

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

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
> >
> >