Cryptography: Theory and Practice by Douglas Stinson CRC Press, CRC Press LLC ISBN: 0849385210 Pub Date: 03/17/95 |
Previous | Table of Contents | Next |
Now, given that we have already successfully carried out the precomputation step, we compute a desired logarithm logα β by means of a Las Vegas type probabilistic algorithm. Choose a random integer s (1 ≤ s ≤ p - 2) and compute
Now attempt to factor γ over the factor base . If this can be done, then we obtain a congruence of the form
This can be written equivalently as
Since everything is now known except logαβ, we can easily solve for logαβ.
Here is a small, very artificial, example to illustrate the two steps in the algorithm.
Example 5.4
Suppose p = 10007 and α = 5 is the primitive element used as the base of logarithms modulo p. Suppose we take as the factor base. Of course log5 5 = 1, so there are three logs of factor base elements to be determined.
Some examples of lucky exponents that might be chosen are 4063, 5136 and 9865.
With x = 4063, we compute
This yields the congruence
Similarly, since
and
we obtain two more congruences:
and
We now have three congruences in three unknowns, and there happens to be a unique solution modulo 10006, namely log5 2 = 6578, log5 3 = 6190 and log5 7 = 1301.
Now, lets suppose that we wish to find log5 9451. Suppose we choose the random exponent s = 7736, and compute
Since 8400 = 24315271 factors over , we obtain
To verify, we can check that 56087 = 9451 (mod 10007).
Heuristic analyses of various versions of the algorithm have been done. Under reasonable assumptions, the asymptotic running time of the precomputation is , and the time to find an individual discrete phase log is .
We now look at the question of partial information about discrete logs. In particular, we consider whether individual bits of a discrete logarithm are easy or hard to compute. To be precise, consider the problem presented in Figure 5.5, which we call the ith Bit problem.
Figure 5.5 ith bit of discrete logarithm
We will first show that computing the least significant bit of a discrete logarithm is easy. In other words, if i = 1, the ith Bit problem can be solved efficiently. This follows from Eulers criterion concerning quadratic residues modulo p, where p is prime.
Consider the mapping defined by
Denote by QR(p) the set of quadratic residues modulo p; then
First, observe that f(x) = f(p - x). Next note that
if and only if
which happens if and only if
It follows that
for every y ∈ QR(p), and hence
That is, exactly half the residues in are quadratic residues and half are not.
Now, suppose a is a primitive element of . Then αa ∈ QR(p) if a is even. Since the (p - 1)/2 elements α0 mod p, α2 mod p,..., αp-3 mod p are all distinct, it follows that
Hence, β is a quadratic residue if and only if logα β is even, that is, if and only it L1(β) = 0. But we already know, by Eulers criterion, that β is a quadratic residue if and only if
So we have the following efficient formula to calculate L1 (β):
Lets now consider the computation of Li(β) for values of i exceeding 1. Suppose
where t is odd. Then it can be shown that it is easy to compute Li(β) if i ≤ s. On the other hand, computing Ls+1 (β) is (probably) difficult, in the sense that any hypothetical algorithm (or oracle) to compute Ls+1 (β) could be used to find discrete logarithms in .
We shall prove this result in the case s = 1. More precisely, if p ≡ 3 (mod 4) is prime, then we show how any oracle for computing L2(β) can be used to solve the Discrete Log problem in .
Recall that, if β is a quadratic residue in and p ≡ 3 (mod 4), then the two square roots of β modulo p are ± β(p+1)/4 mod p. It is also important that, for any β ≠ 0,
if p ≡ 3 (mod 4). We see this as follows. Suppose
then
Since p ≡ 3 (mod 4), the integer (p - 1)/2 is odd, and the result follows.
Now, suppose that β = αa for some (unknown) even exponent a. Then either
or
We can determine which of these two possibilities is correct if we know the value L2 (β), since
This fact is exploited in our algorithm, which we present in Figure 5.6.
At the end of the algorithm, the xis comprise the bits in the binary representation of logα β; that is,
We will work out a small example to illustrate the algorithm.
Figure 5.6 Computing discrete logs in for p ≡ 3 (mod 4), given an oracle for L2(β)
Previous | Table of Contents | Next |
Copyright © CRC Press LLC