In mathematics Discrete Logarithms are group-theoretic analogues of ordinary logarithms. Consider the equation ax ≡p b, whereas a,b ∈ (ℤp)×, p is prime. To compute x you have to solve a Discrete Logarithm problem. A concrete example would be 6x ≡8101 7531. That is an integer x is sought so that 6x divided by 8101 gives the remainder 7531. The basic number is called generator if every number within the cyclic group can be written as gk for some integer k. In the given example the order of 6 is equal to 8100, hence 6 is generator of the group (ℤ8101)×.
The idea of the Pohlig-Hellman-Algorithmus is to break down the DL-problem within a group of order n into DL-problems of groups with lesser order. Therefore we must compute the prime factorization of the original group order and after we have solved some lesser DL problems within the subgroups we use the Chinese Remainder Theorem to compute the solution for the original problem. If you are interested please review the detailed Derivation or consult e.g. Annette Werner's "Elliptische Kurven in der Kryptographie" which contains an explanation of a Pohlig-Hellman-variant suitable for the DL-problem of groups based upon Elliptic Curves.
The program performs a computation on several basic crypto-problems related to the discrete logarithm defined within batch/pohlighellman-batch.xml.
A copy of the attached batch file can be reviewed here. The
first two tasks make use of a generator as basic number, that is a solution for every possible b within the multiplicative group given by
(ℤ2017)×
and accordingly (ℤ71)× does exist. The next two problems do highlight the situation when the basic number
a isn't a generator. Then a solution does exist if
b is within the subgroup given by a and vice versa. The fifth problem uses a fermat prime as prime modulus.
In this case the Chinese Reaminder Theorem isn't necessary to compute a solution. Apparent incorrect provided orders will be refused by the program, see task[id=6].
On the other side numbers which are multiples of the correct order cannot be foreseen by the program (task[id=7]). This may cause problems for the
PollardRho-algorithm which is one
variant to compute the subordinate DL-problems. You may pass in your own problem parameter. Prime numbers can be taken from the PrimeBase
and generators can be computed by task[id=14]. Don't forget to reference a redefined task by a corresponding job within the appropriate
algorithmus section. The extensions-flag indicates that intermediary results will be printed, too. The results will be provided in the file
batch/pohlighellman-batch-result.xml. Look at this copy for the results of the original argument list.
The batch can be used to extract a factor from an integer by using Pollards (p-1)-algorithm, too. The implementation uses a precomputed database which contains all least common
multiples of 1..i·10j with
i∈[1,9] and j∈[2,5] for this. The datafile used by the implementation stores the
LCMs as a byte stream for efficiency reasons. A human-readable format is provided as well.
The Pohlig-Hellman-algorithm matters when considering cryptographic systems whose security are supposed to be based upon the difficulty to compute such Discrete Logarithms for certain public known parameter. An example of a cryptosystem based upon the Discrete Logarithm problem is the ElGamal Signature. The Digital Signature Algorithm (DSA) specified by the National Institute of Standards (NIST) is a widely used variant of the ElGamal signature scheme. The Java Cryptographic Architecture framework provides a DSA implementation as well.
