G - Discrete Logarithm Problems Editorial by en_translator
First of all, spend \(O(\sqrt{P})\) time to factorize \(P-1\). Let \(P-1=\prod_{k=1}^{n} p_k ^{e_k}\).
For \(1\leq x < P\), the minimum positive integer \(m\) satisfying \(x^m=1 \bmod P\) is called its order (on \((\mathbb{Z}/P\mathbb{Z})^*\)). The order of any \(x\) is a factor of \((P-1)\).
Proof
Let $m$ be the order of $x$, and $d=\gcd(m,P-1)$ (GCD: Greatest Common Divisor). By the extended Euclidean algorithm, there exist integers $a$ and $b$ such that $am+b(P-1)=d$. By Fermat's little theorem, $x^{P-1}\equiv 1$, so $x^d = x^{am+b(P-1)} = (x^m)^a(x^{P-1})^{-b}\equiv 1$; by the minimality of order, $d\geq m$. Meanwhile, by the property of GCD, $d|m$, so $d=m$; $d|P-1$, so $m|P-1$.Therefore, the order of any \(x\) can be found by the following procedure:
- Let \(M\) be \(P-1\).
- For \(k=1,2,\ldots,n\), repeat the following:
- While \(p_k|M\) and \(x^{\frac{M}{p_k}}=1 \bmod p\), replace \(M\) with \(\frac{M}{p_k}\).
- After the loop terminates, \(M\) is the order of \(x\).
The loop runs \(\sum_i e_i=O(\log P)\) times, each costing \(O(\log P)\) time for the check, so it can be done in a total of \(O((\log P)^2)\) time.
Let \(B_i\) be the order of \(A_i\). Then the following two conditions are equivalent:
- There exists a positive integer \(k\) such that \(A_i^k=A_j \bmod P\).
- \(B_j | B_i\).
Proof
Take a primitive root $g$ $\bmod P$.Lemma 1: the order of $g^e$ is $\frac{(P-1)}{\gcd(P-1,e)}$.
Proof: let $o$ be the order of $g^e$, and $d$ be $\gcd(P-1,e)$. By definition of order, $o$ is the minimum non-negative integer such that $(g^e)^o\equiv 1 \bmod P$; by definition of primitive root, this condition is to $eo\equiv 0 \bmod P-1$, so $eo=\mathrm{lcm}(e,P-1)$. Since $(P-1)e=\gcd(e,P-1)\mathrm{lcm}(e,P-1)$, we have $do=P-1$, concluding the proof.
Lemma 2: The following are equivalent: (1) there exists a non-negative integer $k$ such that $(g^{e_1})^k\equiv g^{e_2} \bmod P$. (2) $\gcd(e_1,P-1)|\gcd(e_2,P-1)$.
Proof: the former holds if and only if there exists $k$ such that $e_1k\equiv e_2 \bmod P-1$; we consider this proposition. (1)⇒(2)
We prove the contraposition. When $\gcd(e_1,P-1) \not |\gcd(e_2,P-1)$, there exists a divisor $d$ of $\gcd(P-1,e)$ that is not a divisor of $\gcd(e_2,P-1)$. For such $d$, we have that $e_2 \not\equiv 0\equiv e_1k \mod d$ for all $k$, which holds even modulo $(P-1)$, which is a multiple of $d$.
(2)⇒(1)
Let $d_i=\gcd(e_i,P-1)$ and $e_i'=\frac{e_i}{d_i}$. It suffices to show the existence of $k$ such that $e_1k \equiv e_2 \bmod P-1$. Dividing both hand sides by $d_1$, we obtain $e_1'k\equiv e_2'\frac{d_2}{d_1} \bmod\frac{P-1}{d_1}$. Since $e_1'$ is by definition coprime to $(P-1)$, so there exists $e_1'^{-1}\bmod\frac{P-1}{d_1}$, and any non-negative integer $k$ with $k\equiv e_1'^{-1}e_2'\frac{d_2}{d_1} \bmod\frac{P-1}{d_1}$ suffices.
Lemma 3: When $x|z$ and $y|z$, it holds that $x|y$ if and only if $\displaystyle \frac{z}{y} |\frac{z}{x}$.
Proof: omitted.
Proof of the original claim:
Let $B_i'$ be the minimum non-negative integer such that $A_i\equiv g^{B_i'} \bmod P$. By lemma 2, there exists non-negative integer $k$ such that $A_i^k\equiv A_j \bmod P$ if and only if $\gcd(B_i',P-1)|\gcd(B_j',P-1)$. By lemma 3, it is holds if and only if $\frac{P-1}{\gcd(B_j',P-1)}|\frac{P-1}{\gcd(B_i',P-1)}$, which is in turn equivalent to $B_j|B_i$ by lemma 1.
Therefore, once we actually obtain each \(B_i\), the problem can be rephrased as follows.
Problem (★): Given \(N\) integers \(B_1,\ldots,B_N\) that are divisors of \((P-1)\), find the number of integer pairs \((i,j)\) with \(1\leq i,j \leq N\), such that \(B_j | B_i\).
Since the values \(B_i\) are all divisors of \((P-1)\), one can check the divisibility for each \(B_i\) (instead of each \(i\)) to solve problem (★) in a total of \(\Theta((\text{The number of divisors of }(P-1))^2)\) time. Under the constraints of the problem, the number of divisors is at most \(10080\), when \(P-1=6746328388800, 9092877393600\); so you can get AC (accepted) verdict in most languages.
Problem (★) can be solved even faster. For \(B_i=\prod_{k=1}^{n}p_k^{e_{i,k}}\), it holds that \(B_j | B_i\) if and only if \(e_{j,k}\leq e_{i,k}\) for all \(e_{j,k}\leq e_{i,k}\). Considering the fast zeta transform (multi-dimensional cumulative sum), one can easily find the number of \(j\) such that \(B_j | B_i\) for each \(i\) (if it does not ring the bell, consider easy cases like \(P=13,37,109\)). The complexity is \(O(n*(\text{The number of divisors of }(P-1)))\), where \(n=O(\log P / \log\log P)\).
When finding the order, one can maintain the prime factorization of \(M\), so that \(e_{i,k}\) is found without additional computation.
posted:
last update: