LogMod

The purpose of this notebook is to show how to use the Mathematica packages LogMod', which is available via
	 http://www.mat.univie.ac.at/pub/teschl/notebooks/LogMod.m
and needs to be  stored in the AddOns/Applications subfolder of your Mathematica folder. On multi-user systems, you can install an add-on either in the central Mathematica directory (provided you have access to it) or else in your individual user's Mathematica directory (usually ~/.Mathematica/). (You can also put them  somewhere else, as long as you change the $PATH variable in Mathematica such that the files can be found by Mathematica or evaluate the packages before using this  notebook.) 

The latest version of this notebook is available from
	 http://www.mat.univie.ac.at/pub/teschl/notebooks/LogMod.nb

©2023 by Gerald Teschl  <mailto:Gerald.Teschl@univie.ac.at>, <http://www.mat.univie.ac.at/~gerald/>

SetDirectory[NotebookDirectory[]];

Needs["LogMod`"]

Let us generate some random input:

p=RandomPrime[{(10^7),(10^8)-1}];a=RandomInteger[{1,p-1}];m=MultiplicativeOrder[a,p];x=RandomInteger[{1,m-1}];b=PowerMod[a,x,p];{m,x}

There is a built-in command for solving discrete log problems:

Timing[MultiplicativeOrder[a,p,{b}]]

The present code first uses a Pohlig - Hellman reduction and then Shank’s baby-step/giant-step algorithm, which gives better performance for large numbers:

Timing[LogMod[a,b,p]]

Alternatively, you could also use Pollard' s rho method :

Timing[LogMod[a,b,p,Method->"Rho"]]

or index calculus (without sieving, hence slow):

Timing[LogMod[a,b,p,Method->"IC",Verbose->2]]

The code is mainly for educational purpose and you are invited to look at the implementation. There are more advanced algorithms, namely index calculus in combination with sieve methods. The package does not provide these methods.