Dear GAP forum,

Miguel A. Borges Trenard wrote:

>
>Dear GAP forum,
>
>I would like to know how to solve the Discrete Logarithmic Problem by
>means
>of GAP.
>
>Probably, it could be solved by using a stabilizer chain but I don't
>know
>how.
>
>Thank you, Miguel Angel Borges-Trenard.
>
>
>
>
The manual states:

LogMod( n, r, m )

computes the discrete r-logarithm of the integer n modulo the integer m.
It returns a number x such that r^x = n mod m if such a number exists.
Otherwise fail is returned.

Although the manual indicates that the method used is "naive", the current method
used is Pollard-rho, written by Sean Gage and Alexander Hulpke (8-2002).
D Joyner wrote a version of the Shanks Baby-Step/Giant Step method, which goes by

LogModshanks( n, r, m ),

and is available for teaching purposes. However, before Pollard-rho was used,
Shank's method was used (and before Shank's method was used, the naive method
was used). So, the method used to compute LogMod depends on which version of GAP
you have.

Since you mention stabilizer chains, perhaps you are looking for
a solution not only working for Z/mZ, but want
to have an algorithm working in a more general case -- this certainly can be
arbitrary difficult (finite permutation groups should be quite an easy case,
and maybe one still can do something in matrix groups, for example,
but e.g. for finitely presented groups with unsolvable word problem the
situation probably seems to be hopeless).

- Stefan Kohl and David Joyner

Miles-Receive-Header: reply