Add generic_discrete_logarithm and order computation using Pollard's rho algorithm

[93749b3a-c0a4-47a7-b178-004ba08b0b97]

The computational cost of Shanks' Baby-Step Giant-Step algorithm and Pollard's rho and lambda algorithms are more or less the same, but the memory costs is much worse for Shanks' algorithm. It would be nice to have better discrete log algos and group structure computations, ala E. Teske, A Space Efficient Algorithm for Group Structure Computation (1998).

Component: group theory

Keywords: discrete log shanks pollard rho order group structure

Issue created by migration from https://trac.sagemath.org/ticket/277

[e13df781-8644-42aa-9d66-1e8d332e25bb]

comment:2

See also Sutherland's thesis

http://theory.lcs.mit.edu/~cis/theses/sutherland-phd.pdf

which gives a better algorithm for computing group orders

[JohnCremona]

Attachment: 8758.patch.gz

patch applies to 2.10.3.rc0 after 8682.patch in #2356

[JohnCremona]

comment:4

The attached patch (8758.patch) is a first stab at doing these things more generically. For any multiplicative or additive situation the new version of discrete_log_generic() now works, using a baby-step-giant-step approach. For example (see doctest) this gives a BSGS implementation of DLOGS for elliptic curves.

If people think this is a reasonable way to go (and it is certainly a simple interface) then there is more which can be added very easily: a more general BSGS function (solve a=b^n with n in some specified interval) which would be called by discrete_log() and also allow for computation of orders of elements in any group, etc.

Then one could have other algorithms implemented in the same framework such as Pollard Rho or the more sophisticated ones mentioned in earlier comments.

More comments please!

[robertwb]

comment:5

I like it.

One comment I have is that you might want to look at the python operator module rather than using lambda functions.

sage: _ = var('x,y')
sage: operator.neg(x)
-x
sage: operator.add(x,y) # the order is actually respected, this is just a maxima thing
y + x
sage: operator.invert(x)
1/x
sage: operator.mul(x,y)
x*y

[JohnCremona]

apply after 8758.patch

[JohnCremona]

comment:6

Attachment: 8759.patch.gz

I liked the suggestion of using operators: 8759.patch does that (needs to be applied after 8758.patch). At the same time it adds some more doctests, and makes a couple of minor efficiency savings.

If there are going to be more generic functions like this (and I hope there are) we need a better place for them than rings/arith.py. I see that in structure/element.pyx there are also some generic things, including generic powering. Perhaps this function should be moved to a new .py file under structures? Or at least renamed generic.py.

[robertwb]

comment:7

Looks and works great.

As far as your comments of a new .py file for generic functions, most of them will make sense in a category and will go there (in which case they will be automatically attached to every element and/or object of that category).

[JohnCremona]

comment:8

Thanks for the positive review.

Note that these patches do not fulfill all the wish-list requirements, so while I hope they can be merged as soon as possible, the ticket should be be closed. If that is possible!

[85eec1a4-3d04-4b4d-b711-d4db03337c41]

comment:9

Merged both patches in Sage 2.10.3.rc2