Ilya Mironov has pointed out in comments that there's a specialized algorithm for solving just this problem. However, I believe that it's more educational to learn to solve this problem using the understanding of the underlying math structure and standard algorithms that come with it. The object we're studying is remainders modulo p with the operation of multiplication. All remainders except 0 form the multiplicative group modulo p, and there's a well-known theorem that says that this group is always cyclic - in other words, isomorphic to the additive group of remainders modulo p-1. This isomorphism maps taking an element to the power of k to multiplication by k modulo p-1, and we know how to inverse that - it's just division by k modulo p-1.
That gives us a full solution to our problem: first, find out to which remainder modulo p-1 does the isomorphism map a. Then divide that remainder by k. Finally, apply the inverse of the isomorphism to get the answer. We also have to handle the case of a=0 separately since 0 doesn't belong to the multiplicative group, but there the solution is easy: b=0.
Of course, there are still implementation details to figure out. How does the isomorphism work, and how to evaluate it quickly? It's not hard to see that the isomorphism is completely defined by the multiplicative remainder g that maps to 1 in the additive group, as all other elements then have to be some powers of g, since gd must map to d for each d from 0 to p-2. Such remainder g is called a generator or a primitive root.
Moreover, all powers gd for d that are relatively prime with p-1 are also generators. Because we need to find any generator, and there are plenty, the most practical strategy for finding one is just trying a few remainders and checking if they are generators. In order to check if a remainder g is a generator, we must see if all its powers from 0 to p-2 are different, but since its order must divide the order of the multiplicative group, it suffices to check that gd is not equal to 1 for all values of d that are proper divisors of p-1.
Finally, having found a generator g, evaluating the isomorphism is called the discrete logarithm which can be solved using a meet-in-the-middle approach, also known as baby-step-giant-step here. Let's pick a number q around sqrt(p-1), and pre-compute baby steps d0, d1, ..., dq-1, and giant steps dq, d2q, ... (up to the first giant step with power that exceeds p-1). Now it's not hard to see that if we try multiplying our number a by all giant steps we will at some point get a result equal to some baby step: a*duq=dv, and then a=dv-uq, so a maps to v-uq mod p-1 under our isomorphism. The giant and baby steps can be precomputed since p is fixed.
The final missing trick is dividing a remainder w by k modulo p-1. This also comes naturally with the understanding of remainders modulo p-1. First, let's represent k as m*n where m is gcd(k, p-1), and n is relatively prime with p-1. If m does not divide w, there's no solution. If m does divide w, then we now need to divide w/m by n modulo (p-1)/m. Since n is relatively prime with (p-1)/m, it has an inverse o such that n*o=1 modulo (p-1)/m, and thus our division result can be found as o*(w/m) modulo (p-1)/m. The numbers o and m can be precomputed since k and p are fixed.
Phew! This looks like one hell of a solution, but actually it's much easier to code it than to explain. And since all steps come naturally from understanding of how remainders work, you don't need to memorize any of them - you can construct them on the fly using just a few clues that you remember.
Thanks for reading, and see you next week!
0 komentar:
Post a Comment