# 2022.5.14 BSGS(ex) & Mobius Inversion(2022.5.14 BSGS(ex) & Mobius Inversion)-其他

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

### $$\rm II$$ – $$\text{ex Baby Step Giant Step}$$

$$\dfrac{a^x}{d}\equiv\dfrac{b}{d}(\mod \dfrac{p}{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 \))