2022.5.14 BSGS(ex) & Mobius Inversion(2022.5.14 BSGS(ex) & Mobius Inversion)

\(\rm I\) – \(\text{Baby Step Giant Step}\)

本质:根号分治
基本功能: 求解 \(a^x\equiv b(\mod p)\)

令 \(x=A\cdot\sqrt p+B\;(A,b\in[0,\sqrt p])\)
那么即求 \(a^{A\cdot\sqrt p+B}\equiv b(\mod p)\)
那么在 \(a, p\) 互质的情况下,有 \(a^{A\cdot\sqrt p}\equiv b\cdot a^B(\mod p)\)
于是,分别求出 \(\underset{A\in [1,\sqrt p]}{a^{A\cdot\sqrt p}}\) 和 \(\underset{B\in [1,\sqrt p]}{b\cdot a^B}\),并判断两者是否有重合的值即可。

\(\rm II\) – \(\text{ex Baby Step Giant Step}\)

用于处理 \(\text{baby Step Giant Step}\) 中 \(\gcd(a, p) \not= 1\) 的情况。
考虑将 \(a, p\) 同除以 \(d=\gcd(a, p)\),则原式化为
\(\dfrac{a^x}{d}\equiv\dfrac{b}{d}(\mod \dfrac{p}{d})\)
其中 \(\dfrac{b}{d}\) 不保证能整除,若不能整除,说明无解。
( 原方程有解 \(\Leftrightarrow\) \(\gcd(a, p)|b\) )

————————

\(\rm I\) – \(\text{Baby Step Giant Step}\)

Essence: root division
Basic functions: solve \ (a ^ x \ equiv B (\ mod p) \)

Make \ (x = a \ cdot \ sqrt P + B \; (a, B \ in [0, \ sqrt P]) \)
Then find \ (a ^ {a \ cdot \ sqrt P + B} \ equiv B (\ mod p) \)
Then in the case of \ (a, P \) coprime, there is \ (a ^ {a \ cdot \ sqrt P} \ equiv B \ cdot a ^ B (\ mod p) \)
Then, calculate \ (\ underset {a \ in [1, \ sqrt P]} {a ^ {a \ cdot \ sqrt P} \) and \ (\ underset {B \ in [1, \ sqrt P]} {B \ cdot a ^ B} \) respectively, and judge whether they have coincident values.

\(\rm II\) – \(\text{ex Baby Step Giant Step}\)

Used to handle \ (\ GCD (a, P) \ not = 1 \) in \ (\ text {baby step giant step} \).
Consider dividing \ (a, P \) by \ (d = \ GCD (a, P) \), and the original formula is
\(\dfrac{a^x}{d}\equiv\dfrac{b}{d}(\mod \dfrac{p}{d})\)
Where \ (\ dfrac{b}{d} \) is not guaranteed to be divisible. If it is not divisible, there is no solution.
(the original equation has a solution \ (\ leftrightarrow \) \ (\ GCD (a, P) |b \))