(Extended) bsgs and higher order congruence equation

Preface ：

Today more BSGS Algorithm . Commonly known as the big step and small step algorithm (Big-Step G…-Step), It's also called towering 、 To the north, to the wide, to the deep 、 White shit .
 
 

problem ：

Solve the exponential congruence equation ：$a^x\equiv b(modp)$ The minimum natural number solution of .
 
 

BSGS Algorithm ： The template questions

This algorithm only considers $gcd(a,p)=1$ The situation of .
 
that , How to do it? .
In fact, it's very simple , Namely enumeration .
 
Let's start with Violence enumeration .
It's enumeration $x$ from $[0,p-1]$, Then check that the answer is correct .
Those who know Euler's theorem should know that as long as they enumerate to $\phi (p)-1$, but $p$ When it is a prime number, the Euler function is still $p-1$.
seen Order and primitive root You should know that as long as you enumerate to $p$ The order of , But it's $p$ We still have to enumerate with violence .
So here we just need to enumerate one by one .
 
however $o(p)$ My violent enumeration doesn't deserve such a tall name , So there is room for optimization .
We can consider Half enumeration .
How to halve , That's the essence of this algorithm .
We make $x=kn+i$, among $n$ A fixed value set for us ,$k$ and i$i$ All variables .
So the original formula becomes $a^{kn+i}\equiv b(modp)$.
because $gcd(a,p)=1$, We can $a^i$ Multiply the inverse of to the right , become $a^{kn}\equiv b(a^i{)}^{-1}(modp)$.
So we can enumerate all $i$, Store the corresponding value on the right in the hash table ( Also available unordered_map). Then enumeration $k$ In the process of , Go to the table and find what you are satisfied with $i$, After finding $kn+i$ That's the answer. . Of course, because you're looking for the smallest , Just do something in the enumeration process .
So this $n$ Your settings , Using the idea of blocking ,$n$ Set to $\sqrt{p}$ Just fine , such $k$ Just enumerate to $\sqrt{p}$,$i$ Only enumerating $\sqrt{p}$. The total complexity is $\sqrt{n}$.

Code up ：

#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;

ll fpow(ll a,ll n,ll mod)
{
    
    ll sum=1,base=a%mod;
    while(n!=0)
    {
    
        if(n%2)sum=sum*base%mod;
        base=base*base%mod;
        n/=2;
    }
    return sum;
}

ll ex_gcd(ll a,ll b,ll& x,ll& y)
{
    
    if(b==0)
    {
    
        x=1;y=0;
        return a;
    }
    ll ans=ex_gcd(b,a%b,x,y);
    ll tmp=x;
    x=y;
    y=tmp-a/b*y;
    return ans;
}

ll inv(ll a,ll mod)// Existence of inverse element condition ：gcd(a,mod)=1
{
    
    ll x,y;
    ll g=ex_gcd(a,mod,x,y);
    if(g!=1)return -1;
    return (x%mod+mod)%mod;
}

ll BSGS(ll a,ll b,ll p)
{
    
    b%=p;
    if(b==1||p==1)return 0;
    ll n=sqrt(p);
    static unordered_map<ll,ll>Bmp;
    Bmp.clear();
    ll inva=inv(fpow(a,n-1,p),p)*b%p;
    for(ll i=n-1;i>=0;i--)
    {
    
        Bmp[inva]=i;inva=inva*a%p;
    }
    ll ta=1,powa=fpow(a,n,p);
    for(ll k=0;k<=p;k+=n)
    {
    
        if(Bmp.count(ta))return k+Bmp[ta];
        ta=ta*powa%p;
    }
    return -1;
}

int main()
{
    
    ll p,b,n;
    scanf("%lld%lld%lld",&p,&b,&n);
    ll ans=BSGS(b,n,p);
    if(ans==-1)printf("no solution\n");
    else printf("%lld\n",ans);
    return 0;
}

Expand BSGS： The template questions

since BSGS Can only solve $gcd(a,p)=1$ The situation of , Well, of course $gcd(a,p)$ May not equal $1$ The situation of .
At this time, the algorithm needs to be extended .
 
because $gcd(a,p)=1$, So we can't reverse the element as before .
So we think about putting $gcd$ First extract .
We make $d=gcd(a,p)$.
We will use the original formula $a^x\equiv b(modp)$ Unfold into $a^x+kp=b$.
And then divide by $d$ become $\frac{a^x}{d}+k\frac{p}{d}=\frac{b}{d}$.
Then take the mold at the same time $\frac{p}{d}$ Got it. $\frac{a^x}{d}\equiv \frac{b}{d}(mod\frac{p}{d})$
Easy to find $b$ Must be $d$ Multiple , Otherwise, return directly to no solution .
And then at this point $gcd(\frac{a}{d},\frac{p}{d})=1$, So you can multiply it by its inverse .
become $a^{x-1}\equiv \frac{b}{d}(\frac{a}{d}{)}^{-1}(mod\frac{p}{d})$.
It becomes a new problem .
At this time, observe $gcd(a,\frac{p}{d})$ Whether it must be $1$.
Of course not , give an example $a=2,p=8$, that $d=2$, take $p$ Divide $d$ after , Can still be divided by $d$, Don't worry , Then divide it again .
I'm lazy , Wrote a recursive version , This process can be done in one step , Recursion may be slower , But compared with the inherent $\sqrt{p}$ Complexity , Multiple $log$ It doesn't hurt .
 
Then the idea of recursion is very clear .
If $gcd(a,p)=1$, Then use BSGS solve .
If $gcd(a,p)\ne 1$, Then use the above method to mold $p$ The problem becomes modular $\frac{p}{gcd(a,p)}$ The problem of , Then call this function recursively .
 
Non recursive thinking ：
If $gcd(a,p)=1$, Then use BSGS solve .
If $gcd(a,p)\ne 1$, Then use the above method to $p$ Divide $gcd(a,p)$, Just divide by how many to find out , Just do it once .
 
Finally, my recursive version of the code ：

#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;

ll fpow(ll a,ll n,ll mod)
{
    
    ll sum=1,base=a%mod;
    while(n!=0)
    {
    
        if(n%2)sum=sum*base%mod;
        base=base*base%mod;
        n/=2;
    }
    return sum;
}

ll ex_gcd(ll a,ll b,ll& x,ll& y)
{
    
    if(b==0)
    {
    
        x=1;y=0;
        return a;
    }
    ll ans=ex_gcd(b,a%b,x,y);
    ll tmp=x;
    x=y;
    y=tmp-a/b*y;
    return ans;
}

ll inv(ll a,ll mod)// Existence of inverse element condition ：gcd(a,mod)=1
{
    
    ll x,y;
    ll g=ex_gcd(a,mod,x,y);
    if(g!=1)return -1;
    return (x%mod+mod)%mod;
}

ll gcd(ll a,ll b)
{
    
    return b?gcd(b,a%b):a;
}

ll BSGS(ll a,ll b,ll p)
{
    
    b%=p;
    if(b==1||p==1)return 0;
    ll n=sqrt(p);
    static unordered_map<ll,ll>Bmp;
    Bmp.clear();
    ll inva=inv(fpow(a,n-1,p),p)*b%p;
    for(ll i=n-1;i>=0;i--)
    {
    
        Bmp[inva]=i;inva=inva*a%p;
    }
    ll ta=1,powa=fpow(a,n,p);
    for(ll k=0;k<=p;k+=n)
    {
    
        if(Bmp.count(ta))return k+Bmp[ta];
        ta=ta*powa%p;
    }
    return -1;
}

ll exBSGS(ll a,ll b,ll p)
{
    
    b%=p;
    if(a==0&&b==0)return 1;
    else if(a==0&&b!=0)return -1;
    if(b==1||p==1)return 0;
    ll d=gcd(a,p);
    if(b%d!=0)return -1;
    p=p/d;
    b=b/d*inv(a/d,p)%p;
    if(d!=1)
    {
    
        ll ans=exBSGS(a,b,p);
        if(ans==-1)return -1;
        return ans+1;
    }
    ll ans=BSGS(a,b,p);
    if(ans==-1)return -1;
    return ans+1;
}

int main()
{
    
    ll a,p,b;
    while(scanf("%lld%lld%lld",&a,&p,&b)!=EOF)
    {
    
        if(a==0&&p==0&&b==0)break;
        ll ans=exBSGS(a,b,p);
        if(ans==-1)printf("No Solution\n");
        else printf("%lld\n",ans);
    }
    return 0;
}

Finally, add an example ,Mod Tree. Note that the same after taking the mold in the title is not the same in the meaning of the mold .
 
 

Higher order congruence equation ：

I do not know! Primordial root Go out and turn left .
Finally, one more BSGS Application .
Solving equations $x^n\equiv a(modp)$.
 
We only consider $p$ As a prime number The solution of .
practice ：
Let's find out first $p$ The original root $g$.
According to the nature of primitive root , When $p$ When it's a prime number ,$g$ A complete residue system can be obtained .
So we can make $x=g^k$, Can also make $a=g^{x_0}$.
here , We just need to solve $k$, You can solve $x$ 了 .
The equation becomes $g^{kn}\equiv g^{x_0}(modp)$.
Equivalent to equation $kn\equiv x_0(modp-1)$.（ This can be based on Fermat's small Theorem , It can also be based on $or{d}_{p}g=p-1$）
Because there's no guarantee $gcd(n,p-1)=1$, So you can't multiply the inverse element .
In fact, the equation is equivalent to solving the equation $nk+(p-1)y=x_0$, Use extended Euclidean .
At this point, the answer will be solved .
 
Um. ？ What I want to say BSGS Well ？
Oh , You'll find this $x_0$ Not yet .
$g^{x_0}\equiv a(modp)$, So we need $x_0$ Is to find the exponential congruence equation .
Come here , Ask for completion .
 
This doesn't write code , I'm lazy , Don't even think about it. .
 
So about $p$ Not prime .
Actually, I won't , But I can still talk nonsense , It may or may not , Keep your mind when you read on , So as not to be misled by the author .
 
Consider decomposing the composite number $p=p_1^{k_1}{p}_2^{k_2}\dots p_n^{k_n}$.
Oh , It doesn't seem feasible .
But when $p=p_1{p}_2\dots p_n$, That is, the number of times of each prime is $1$ When the time , There is still a way to work .
We just need to solve the equation for each modulus $x^n\equiv a(mod{p}_i)$ Solution $x\equiv a_0(modp)$.
Then merge with the Chinese remainder theorem .
If you think so , If there is a way to solve $x^n\equiv a(mod{p}_i^{k_i})$ Words , You can solve the problem of arbitrary modulus , I haven't thought about it yet .
Finish .

Add ：

New learning .. From network security RSA Encryption and decryption algorithm .
Add a solution to the equation $x^n\equiv a(modp)$ In the meet $gcd(n,\phi (p))=1$ Practice under conditions .
We open a power on both sides of the equation $b$, obtain $x^{nb}\equiv a^b(modp)$.
Found that when $nb\equiv 1(mod\phi (p))$ when ,$a^b$ Is a solution of the equation .
therefore , We just need to find one $b$, bring $nb\equiv 1(mod\phi (p))$ establish , Then the problem becomes Expand Euclid The classic question of .
So you can do it $o(logp)$ It's time complexity , Compared with $o(\sqrt{p})$ Your practice is so excellent , Of course, the premise must be met $gcd(n,\phi (p))=1$, This condition also comes from the necessary and sufficient condition for the solution of the tuou equation .