Bug in LogFFE for "large" finite fields

[fingolfin]

The following was reported by Joey Iverson on the GAP Forum:

gap> z:=Z(359^2); 
z
gap> LogFFE(z^4,z^2);
fail

The expected result is 2, not fail.

[Stefan-Kohl]

Actually, I get the following:

gap> List(Primes,p->LogFFE(Z(p^2)^4,Z(p^2)^2));                       
[ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 
  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 
  2, 2, 2, 2, 33026, 34586, 36182, 2, fail, fail, 40046, fail, fail, 2, fail, 
  50246, 54782, 2, fail, fail, 62306, fail, fail, 2, 71822, 2, fail, 2, 
  80402, 2, 87782, fail, 92882, 93746, 2, 98126, 100802, fail, fail, 2, fail, 
  114722, 118586, 120542, 2, fail, 2, 2, 136766, 2, 2, 2, 158486, fail, 
  163022, 2, 2, fail, 2, 2, 2, 2, fail, 2, fail, fail, 2, 209306, 2, 217142, 
  218462, fail, 229166, 233246, 2, 2, fail, 258482, 264266, 268646, 2, fail, 
  282002, 2, fail, 2, fail, 2, 2, 2, 2, fail, fail, 2, 343622, 2, 2, 367226, 
  fail, 2, 384566, 2, fail, 393386, 411326, fail, 422282, 2, 2, 442742, 
  448406, 454106, fail, 471422, 477266, 2, 2, fail ]

[fingolfin]

@Stefan-Kohl and the first failing prime is 281, and 281^2 > 2^16, so this affects only "large" prime fields, as described in the title.

I already fixed part of the bug locally (a bad recursion), but there's more wrong there.

[Stefan-Kohl]

@fingolfin I get the first 'fail' for 277. -- Though still 277^2 > 2^16, so that probably doesn't make much difference.

[fingolfin]

Yeah, my number was with my partial fix. BTW, there are even failures when both arguments are equal!

[fingolfin]

A lot of the code for large FFE support was written by @stevelinton ; perhaps he can take a look at this bug and has an idea how to resolve it?

[frankluebeck]

I did not see an easy way to fix the library code.
But the package StandardFF contains and installs a more efficient method for LogFFE. It makes the examples given above work as expected.

[fingolfin]

@frankluebeck you mentioned some time ago that you'd be willing to migrate your new LogFFE implementation to the GAP library. That would be really nice.

[ThomasBreuer]

As far as I see, there are several bugs in the GAP library code used by LogFFE.
I think one of them is that the calls of FFECONWAY.LogFFERhoIterate ignore the possibility that "Pollard's rho algorithm for logarithms" can fail in the sense that bd - b is zero; this does not explain all of the abovementioned wrong results. Like @frankluebeck, I see no easy way to fix this code.

Since an alternative (and even faster) implementation is available in the StandardFF package, I propose to remove the code of FFECONWAY.LogFFERhoIterate, FFECONWAY.DoLogFFERho, FFECONWAY.DoLogFFE.
These functions are not documented, and inside the GAP library they are used only in methods for LogFFE.
The question is how to keep the functionality of LogFFE (or rather to get functionality that is better).

I am not sure that @frankluebeck had proposed to move his code to the GAP library. Another interpretation of his statement would be that everything is fine as soon as the StandardFF package is loaded. Thus one solution would be to turn StandardFF into a needed package of GAP and then to remove the three functions from the record FFECONWAY.

If we do not want to introduce another needed package of GAP then I propose to copy the relevant code from the StandardFF package (the functions DLogShanks and DLog, and the code for the LogFFE method) to the GAP library; but first I would like to ask what @frankluebeck thinks about this solution.

[stevelinton]

On 29 Aug 2023, at 10:22, Thomas Breuer ***@***.***> wrote: As far as I see, there are several bugs in the GAP library code used by LogFFE. I think one of them is that the calls of FFECONWAY.LogFFERhoIterate ignore the possibility that "Pollard's rho algorithm for logarithms" can fail in the sense that bd - b is zero; this does not explain all of the abovementioned wrong results. Like @frankluebeck<https://github.com/frankluebeck>, I see no easy way to fix this code. Since an alternative (and even faster) implementation is available in the StandardFF package, I propose to remove the code of FFECONWAY.LogFFERhoIterate, FFECONWAY.DoLogFFERho, FFECONWAY.DoLogFFE. These functions are not documented, and inside the GAP library they are used only in methods for LogFFE. The question is how to keep the functionality of LogFFE (or rather to get functionality that is better). I am not sure that @frankluebeck<https://github.com/frankluebeck> had proposed to move his code to the GAP library. Another interpretation of his statement would be that everything is fine as soon as the StandardFF package is loaded. Thus one solution would be to turn StandardFF into a needed package of GAP and then to remove the three functions from the record FFECONWAY. If we do not want to introduce another needed package of GAP then I propose to copy the relevant code from the StandardFF package (the functions DLogShanks and DLog, and the code for the LogFFE method) to the GAP library; but first I would like to ask what @frankluebeck<https://github.com/frankluebeck> thinks about this solution. Happy with any of these approaches Steve — Reply to this email directly, view it on GitHub<#3784 (comment)>, or unsubscribe<https://github.com/notifications/unsubscribe-auth/ABQQIRR3EDF7N67O4KUHHOLXXWYE7ANCNFSM4J3Y5HBQ>. You are receiving this because you were mentioned.Message ID: ***@***.***> [ { ***@***.***": "http://schema.org", ***@***.***": "EmailMessage", "potentialAction": { ***@***.***": "ViewAction", "target": "#3784 (comment)", "url": "#3784 (comment)", "name": "View Issue" }, "description": "View this Issue on GitHub", "publisher": { ***@***.***": "Organization", "name": "GitHub", "url": "https://github.com" } } ]

[fingolfin]

The discussion I had with @frankluebeck explicitly was about copying the code to the GAP library, not adding StandardFF as another dependency. Note that there is lots of code out there using LogFEE.

I am opposed to adding another package to the list of needed packages (to the contrary the goal always was to reduce this list). Especially not for this feature -- implementing Shank or some other discrete logarithm is not that hard, so I'd rather rewrite it yet again from scratch if Frank doesn't want us to copy his code.

[ThomasBreuer]

Thanks for the feedback. I will create a pull request for the situation that the code from StandardFF gets added to the GAP library.

[frankluebeck]

Sorry, I'm in holidays know. But I will shortly confirm that I proposed and agreed to move the discussed code from StandardFF into the GAP library (instead of trying to repair the buggy code).
My main problem that prevented me from doing this was that I was unsure what should be removed from the library for a clean solution.
I will have a close look at PR #5495 by @ThomasBreuer when I'm back (end of next week). If that looks fine I will remove the moved code from the StandardFF package and make a new release.

[fingolfin]

Finally fixed, yay!!!