Exponential Congruences - Introduction to Cryptography with Java Applets - page 255

Taking the logarithm base 6 of both sides, and by using the properties of discrete loga-
rithms, we get

log57 + 38 log5 + log7

35 + 23

58 (mod 106).

Thus, we obtain our final result,

log 6,107 57 = 58 38 = 20. (Verify!)

Some parts of this algorithm are not clear; for instance, how many primes t should be in
the set S ? The answer is not clear, since it depends on the abilities of the computing device.
If t is too large, the corresponding system of congruences may take up too much memory,
and take too long to solve. On the other hand, if t is too small, it will be harder to find ele-
ments which can be written as a product of members of S ; the search for these elements
could take too long. This type of time-memory tradeoff always depends on the hardware
being used; thus, we leave this part of the algorithm unspecified.
Another part of the algorithm that is unclear is when it directs one to “attempt to write
the element as a product of members from S .” If we are using the first t primes, we can do
this by simply taking the prime factorization of the element (say E ), and checking if each
factor of E is in the set S . However, if E is a large prime, or is composite but is difficult to
factor because it has large prime factors, the time to do this could be prohibitive. Thus, we
should probably submit E to a primality test; if it turns out to be a probable prime, we should
reject E and choose another random integer. Otherwise, we can try to factor E , but enforce
some time limit to do this.
Many of these decisions for the index-calculus algorithm are heavily dependent on the
hardware, and the software, such as the implementation of large integer arithmetic. Thus,
the decisions on how to implement the index-calculus algorithm are often made based on
experimentation.

EXERCISES

1. Prove part (b) of proposition 37.

2. Write a logPohligHellman() method in the BigIntegerMath class to compute discrete

logs using the Pohlig-Hellman algorithm.

3. Prove part (c) of proposition 43.

4. The BigInteger class provides a modPow() method to perform modular exponentia-

tion, but you should consider how to write such a method. Write an efficient method to
perform modular exponentiation, say a modPow(BigInteger base, BigInteger exponent,
BigInteger modulus) method. Put it in the BigintegerMath class. For help, refer to the
following: