![]() |
|
|||
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
|
![]() |
[an error occurred while processing this directive]
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 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 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 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 5.1.2 Bit Security of Discrete LogsWe 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.
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 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 Now, suppose a is a primitive element of 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 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.
Copyright © CRC Press LLC
![]() |
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
![]() |