Many people know Baby-step Giant-step as an algorithm for solving the Discrete Logarithm Problem. However, I couldn't find any articles dealing with arbitrary mods, so I will write about that.
First, the discrete logarithm problem refers to the following problems. (If you know the solution by Baby-step Giant-step, please skip it)
Given the integers $ X, Y $, which are the positive integers $ M $ and $ 0 \ leq X, Y \ lt M $.
Find the (minimum) non-negative integer $ K $ that satisfies
You can solve this problem as follows.
First, let's handle the simple case of $ X = 0 $. If $ Y = 0 $, then $ K = 1 $, and if $ Y \ neq 0 $, then $ K = -1 $ (does not exist). However, here, $ 0 ^ 0 = 1 $ is set.
Next, consider the case of $ X \ neq 0 $. $ p = \ left \ lceil \ sqrt {M} \ right \ rceil $, a non-negative integer such that $ K = p * i + q \ (0 \ leq q \ lt p) $ satisfies $ (1) $ Let's search for $ i, q $. From Fermat's Little Theorem, it is sufficient to check the range of $ 0 \ leq i \ lt p $.
Now, since $ M $ is a prime number and $ 0 \ lt X \ lt M $, $ \ gcd (X, M) = 1 $ holds. Therefore, there is only one $ X ^ {-1} $ that satisfies $ X * X ^ {-1} \ equiv 1 \ pmod M $ in the range of $ 0 \ lt X ^ {-1} \ lt M $. To do. Using this $ X ^ {-1} $, the $ (1) $ expression is transformed as follows.
\begin{align}
X^K&\equiv Y\pmod M\\
X^{p*i+q}&\equiv Y\pmod M\\
X^q&\equiv Y*A^i\pmod M\tag{2}\\
\end{align}
In the transformation of the 2nd to 3rd lines, we put $ A = (X ^ {-1}) ^ p $.
The value that the left side of $ (2) $ can take is $ X ^ 0 \ bmod M, X ^ 1 \ bmod M, \ dots, X ^ {p-1} \ bmod M $ at most $ p = \ left \ lceil \ sqrt {M} \ right \ rceil $ Kind. Therefore, we will calculate in advance an associative array (ʻunordered_maporHashMap) that will be copied to $ X ^ j \ bmod M \ mapsto j $. At this time, if key has already been inserted, do not overwrite value`.
From the above, if you check all $ i = 0,1, \ dots, p-1 $ on the right side of $ (2) $, you can get the desired $ i, q $ (if not found, $ K = -1 $). By not overwriting the value in the associative array and scanning $ i $ in ascending order, the first $ i, q $ found constitutes the smallest $ K $ that satisfies $ (1) $. I also understand.
The computational complexity of the above solution,
-Calculation of $ p $ is a binary search $ O (\ log M) $ -$ X ^ {-1} $ is calculated by Euclidean algorithm $ O (\ log M) $ -$ A = (X ^ {-1}) ^ p $ is calculated as $ O (p) = O (\ sqrt {M}) $ --Precalculation of associative array is $ O (p) = O (\ sqrt {M}) $ -Full search of $ i = 0, \ dots, p-1 $ is $ O (p) = O (\ sqrt {M}) $
Therefore, the whole is $ O (\ sqrt {M}) $.
This is the main subject of this article. When $ M $ becomes a composite number, the above algorithm cannot be applied as it is. This is because $ X ^ {-1} $ may not exist. However, if $ M $ is a composite number, the problem can be solved with almost the same algorithm.
The solution is shown below.
First, process the case of $ M = 1 $. In this case, for any $ X, Y $, $ K = 0 $ satisfies $ (1) $ and is the minimum.
Hereafter, $ M> 1 $.
Let's say $ g: = \ gcd {(X, M)} $. If $ g = 1 $, $ X ^ {-1} $ exists, so the algorithm described above can be applied as it is, so it ends here. If it is $ g \ neq 1 $, that is not the case, so I will devise a little.
It decomposes $ X and M $ into products such as $ X = g * X'$ and $ M = g * M'$.
Substituting these into $ (1) $ yields $ (g * X') ^ K \ equiv Y \ pmod {(g * M')} $. Therefore, there is an integer $ n
When $ K> 0 $, $ Y $ must be a multiple of $ g $, so $ Y $ is also decomposed as $ Y = g * Y'$ ($ Y $ is $). There is no $ K $ that satisfies $ (1) $ unless it is a multiple of g $). You can proceed with the calculation of the $ (3) $ formula and get the formula $ (4) $.
\begin{align}
g*X'*(g*X')^{K-1}-g*Y'&=n*g*M'\\
X'*(g*X')^{K-1}-Y'&=n*M'\\
X'*(g*X')^{K-1}&\equiv Y'\pmod{M'}\tag{4}
\end{align}
Furthermore, since $ \ gcd {(X', M')} = 1 $ holds, $ X'* {X'} ^ {-1} \ equiv 1 \ pmod {M'} $, $ 0 \ lt {X' } ^ {-1} \ lt There is only one $ {X'} ^ {-1} $ that is M'$. By using this, we get the $ (5) $ equation.
\begin{align}
X'*(g*X')^{K-1}&\equiv Y'\pmod{M'}\\
(g*X')^{K-1}&\equiv Y'*{X'}^{-1}\pmod{M'}\\
X^L&\equiv Z\pmod{M'}\tag{5}\\
\end{align}
In the transformation of the 2nd to 3rd lines, we put $ L = K-1, \ Z = Y'* {X'} ^ {-1} $.
Since $ (5) $ is a discrete logarithmic problem that is smaller in size than the original problem, we can solve this problem recursively. Also, considering the computational complexity analysis described later, we can see that this recursion always ends. If the smallest non-negative integer $ L $ that satisfies $ (5) $ exists, then $ L + 1 $ is the answer, and if $ L $ does not exist, there is no solution to the original problem.
One thing to note is that $ \ gcd {(X, M')} = 1 $ is not always the case.
For example, if $ (X, M) = (20, 24) $, then $ g = \ gcd {(X, M)} = 4 $, so $ M'= M / g = 6 $. At this time, $ \ gcd {(X, M')} = 2 \ neq 1 $.
The computational complexity of this solution is
(Computational complexity of recursion until $ \ gcd {(X, M)} = 1 $) + (Computational complexity of Baby-step Giant-step)
is. You need to recurse for $ \ gcd {(X, M)} \ neq 1 $, where $ (X, M) $ is $ (X, M / \ gcd {(X, M)}) $ Move on to. At this time, since $ \ gcd {(X, M)}> = 2 $, $ M $ is reduced to less than half each time the recursion occurs. Therefore, the number of recursion is $ O (\ log M) $, and the Euclidean algorithm is performed only a certain number of times for each recursion, so the amount of recursion calculation is $ O ((\ log M) ^ 2) $. ..
From the above, we were able to solve the discrete logarithm problem with arbitrary mods with a total computational complexity of $ O (\ sqrt M) $.
Finally, I would like to conclude with a Java program that solves the discrete logarithm problem with arbitrary mods.
Problem used for verify: Discrete Logarithm Submission: Discrete Logarithm
DiscreteLogarithm.java
public class DiscreteLogarithm {
/**
*Solve the discrete logarithm problem with an arbitrary mod. That is, x^k=Find the smallest non-negative integer k that satisfies y mod m.
* @Bottom of param x log
* @param y {@code x}Exponentiation
* @param m mod
* @return x^k=The smallest non-negative integer that satisfies y mod m k. If it does not exist-Returns 1.
*/
public static long log(long x, long y, long m) {
if ((x %= m) < 0) x += m;
if ((y %= m) < 0) y += m;
// m =Handle 1 case
if (m == 1) return 0;
// y = 1 (k = 0)Handle cases
if (y == 1) return 0;
long[] gi = gcdInv(x, m);
// g=gcd(x,m), ix*x=g mod m
long g = gi[0], ix = gi[1];
if (g != 1) {
//y is gcd(x, g)Must be a multiple of
if (y % g != 0) return -1;
m /= g;
y = (y / g) * ix;
//Solve small size problems
long log = log(x, y, m);
//If there is no solution for the small size problem, there is no solution for the original problem
if (log < 0) return -1;
//If the answer to the small size question is l, then the answer to the original question is l+ 1
return log + 1;
}
// gcd(x, g) =1 is Baby-step Giant-Can be solved with step
return coprimeLog(x, y, m, ix);
}
/**
*Baby when x and m are relatively prime-step Giant-Solve the discrete logarithm problem by step.
* @Bottom of param x log
* @param y {@code x}Exponentiation
* @param m mod
* @param ix mod {@code m}In{@code x}Multiplication inverse element x^{-1}
* @return x^k=The smallest non-negative integer that satisfies y mod m k. If it does not exist-Returns 1.
*/
private static long coprimeLog(long x, long y, long m, long ix) {
long p = ceilSqrt(m);
java.util.HashMap<Long, Long> memo = new java.util.HashMap<>();
for (long i = 0, powx = 1; i < p; i++) {
memo.putIfAbsent(powx, i);
powx = powx * x % m;
}
long a = pow(ix, p, m);
for (long i = 0, ypowa = y; i < p; i++) {
long q = memo.getOrDefault(ypowa, -1l);
if (q >= 0) return p * i + q;
ypowa = ypowa * a % m;
}
return -1l;
}
/**
* (x-1)^2 < n <= x^Binary search for x that satisfies 2.
* @An integer that takes param n sqrt
* @return (x-1)^2 < n <= x^Satisfy 2 x
*/
private static long ceilSqrt(long n) {
long l = -1, r = n;
while (r - l > 1) {
long m = (r + l) >> 1;
if (m * m >= n) r = m;
else l = m;
}
return r;
}
/**
* a^b mod m is calculated by the dichotomous power method.
* @param a bottom
* @param b index
* @param m mod
* @return a^b mod m
*/
private static long pow(long a, long b, long m) {
if (m == 1) return 0;
if ((a %= m) < 0) a += m;
long pow = 1;
for (long p = a, c = 1; b > 0;) {
long lsb = b & -b;
while (lsb != c) {
c <<= 1;
p = (p * p) % m;
}
pow = (pow * p) % m;
b ^= lsb;
}
return pow;
}
/**
* g = gcd(x, m), a * x =A pair that satisfies g mod m(g, x)Is calculated by the Euclidean algorithm.
* @param a
* @param m mod
* @return g = gcd(x, m), a * x =A pair that satisfies g mod m(g, x)
*/
private static long[] gcdInv(long a, long m) {
if ((a %= m) < 0) a += m;
if (a == 0) return new long[]{m, 0};
long s = m, t = a;
long m0 = 0, m1 = 1;
while (t > 0) {
long u = s / t;
s -= t * u;
m0 -= m1 * u;
long tmp;
tmp = s; s = t; t = tmp;
tmp = m0; m0 = m1; m1 = tmp;
}
if (m0 < 0) m0 += m / s;
return new long[]{s, m0};
}
}
Recommended Posts