当前位置:网站首页>(Extended) bsgs and higher order congruence equation
(Extended) bsgs and higher order congruence equation
2022-04-23 09:35:00 【Zimba_】
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 ≡ b ( m o d p ) a^{x}\equiv b(mod\; p) ax≡b(modp) The minimum natural number solution of .
BSGS Algorithm : The template questions
This algorithm only considers g c d ( a , p ) = 1 gcd(a,p)=1 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 x x from [ 0 , p − 1 ] [0,p-1] [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 φ ( p ) − 1 \varphi(p)-1 φ(p)−1, but p p p When it is a prime number, the Euler function is still p − 1 p-1 p−1.
seen Order and primitive root You should know that as long as you enumerate to p p p The order of , But it's p p p We still have to enumerate with violence .
So here we just need to enumerate one by one .
however o ( p ) o(p) 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 = k n + i x=kn+i x=kn+i, among n n n A fixed value set for us , k k k and i i i i All variables .
So the original formula becomes a k n + i ≡ b ( m o d p ) a^{kn+i}\equiv b(mod\;p) akn+i≡b(modp).
because g c d ( a , p ) = 1 gcd(a,p)=1 gcd(a,p)=1, We can a i a^{i} ai Multiply the inverse of to the right , become a k n ≡ b ( a i ) − 1 ( m o d p ) a^{kn}\equiv b(a^{i})^{-1}(mod\;p) akn≡b(ai)−1(modp).
So we can enumerate all i i i, Store the corresponding value on the right in the hash table ( Also available unordered_map). Then enumeration k k k In the process of , Go to the table and find what you are satisfied with i i i, After finding k n + i kn+i 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 n n Your settings , Using the idea of blocking , n n n Set to p \sqrt{p} p Just fine , such k k k Just enumerate to p \sqrt{p} p, i i i Only enumerating p \sqrt{p} p. The total complexity is n \sqrt{n} 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 g c d ( a , p ) = 1 gcd(a,p)=1 gcd(a,p)=1 The situation of , Well, of course g c d ( a , p ) gcd(a,p) gcd(a,p) May not equal 1 1 1 The situation of .
At this time, the algorithm needs to be extended .
because g c d ( a , p ) = 1 gcd(a,p)=1 gcd(a,p)=1, So we can't reverse the element as before .
So we think about putting g c d gcd gcd First extract .
We make d = g c d ( a , p ) d=gcd(a,p) d=gcd(a,p).
We will use the original formula a x ≡ b ( m o d p ) a^{x}\equiv b(mod\;p) ax≡b(modp) Unfold into a x + k p = b a^{x}+kp=b ax+kp=b.
And then divide by d d d become a x d + k p d = b d \frac{a^{x}}{d}+k\frac{p}{d}=\frac{b}{d} dax+kdp=db.
Then take the mold at the same time p d \frac{p}{d} dp Got it. a x d ≡ b d ( m o d p d ) \frac{a^{x}}{d}\equiv \frac{b}{d}(mod\;\frac{p}{d}) dax≡db(moddp)
Easy to find b b b Must be d d d Multiple , Otherwise, return directly to no solution .
And then at this point g c d ( a d , p d ) = 1 gcd(\frac{a}{d},\frac{p}{d})=1 gcd(da,dp)=1, So you can multiply it by its inverse .
become a x − 1 ≡ b d ( a d ) − 1 ( m o d p d ) a^{x-1}\equiv \frac{b}{d}(\frac{a}{d})^{-1}(mod\;\frac{p}{d}) ax−1≡db(da)−1(moddp).
It becomes a new problem .
At this time, observe g c d ( a , p d ) gcd(a,\frac{p}{d}) gcd(a,dp) Whether it must be 1 1 1.
Of course not , give an example a = 2 , p = 8 a=2,p=8 a=2,p=8, that d = 2 d=2 d=2, take p p p Divide d d d after , Can still be divided by d d 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 p \sqrt{p} p Complexity , Multiple l o g log log It doesn't hurt .
Then the idea of recursion is very clear .
If g c d ( a , p ) = 1 gcd(a,p)=1 gcd(a,p)=1, Then use BSGS solve .
If g c d ( a , p ) ≠ 1 gcd(a,p)\neq 1 gcd(a,p)=1, Then use the above method to mold p p p The problem becomes modular p g c d ( a , p ) \frac{p}{gcd(a,p)} gcd(a,p)p The problem of , Then call this function recursively .
Non recursive thinking :
If g c d ( a , p ) = 1 gcd(a,p)=1 gcd(a,p)=1, Then use BSGS solve .
If g c d ( a , p ) ≠ 1 gcd(a,p)\neq 1 gcd(a,p)=1, Then use the above method to p p p Divide g c d ( a , p ) gcd(a,p) 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 ≡ a ( m o d p ) x^{n}\equiv a(mod\;p) xn≡a(modp).
We only consider p p p As a prime number The solution of .
practice :
Let's find out first p p p The original root g g g.
According to the nature of primitive root , When p p p When it's a prime number , g g g A complete residue system can be obtained .
So we can make x = g k x=g^{k} x=gk, Can also make a = g x 0 a=g^{x_{0}} a=gx0.
here , We just need to solve k k k, You can solve x x x 了 .
The equation becomes g k n ≡ g x 0 ( m o d p ) g^{kn}\equiv g^{x_{0}}(mod\;p) gkn≡gx0(modp).
Equivalent to equation k n ≡ x 0 ( m o d p − 1 ) kn\equiv x_{0}(mod\;p-1) kn≡x0(modp−1).( This can be based on Fermat's small Theorem , It can also be based on o r d p g = p − 1 ord_{p}g=p-1 ordpg=p−1)
Because there's no guarantee g c d ( n , p − 1 ) = 1 gcd(n,p-1)=1 gcd(n,p−1)=1, So you can't multiply the inverse element .
In fact, the equation is equivalent to solving the equation n k + ( p − 1 ) y = x 0 nk+(p-1)y=x_{0} nk+(p−1)y=x0, 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 x_{0} x0 Not yet .
g x 0 ≡ a ( m o d p ) g^{x_{0}}\equiv a(mod\;p) gx0≡a(modp), So we need x 0 x_{0} x0 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 p 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 … p n k n p=p_{1}^{k_{1}}p_{2}^{k_{2}}…p_{n}^{k_{n}} p=p1k1p2k2…pnkn.
Oh , It doesn't seem feasible .
But when p = p 1 p 2 … p n p=p_{1}p_{2}…p_{n} p=p1p2…pn, That is, the number of times of each prime is 1 1 1 When the time , There is still a way to work .
We just need to solve the equation for each modulus x n ≡ a ( m o d p i ) x^{n}\equiv a(mod\;p_{i}) xn≡a(modpi) Solution x ≡ a 0 ( m o d p ) x\equiv a_{0}(mod\;p) x≡a0(modp).
Then merge with the Chinese remainder theorem .
If you think so , If there is a way to solve x n ≡ a ( m o d p i k i ) x^{n}\equiv a(mod\;p_{i}^{k_{i}}) xn≡a(modpiki) 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 ≡ a ( m o d p ) x^{n}\equiv a(mod\;p) xn≡a(modp) In the meet g c d ( n , φ ( p ) ) = 1 gcd(n,\varphi (p))=1 gcd(n,φ(p))=1 Practice under conditions .
We open a power on both sides of the equation b b b, obtain x n b ≡ a b ( m o d p ) x^{nb}\equiv a^{b}(mod\;p) xnb≡ab(modp).
Found that when n b ≡ 1 ( m o d φ ( p ) ) nb\equiv 1(mod\;\varphi(p)) nb≡1(modφ(p)) when , a b a^{b} ab Is a solution of the equation .
therefore , We just need to find one b b b, bring n b ≡ 1 ( m o d φ ( p ) ) nb\equiv 1(mod\;\varphi(p)) nb≡1(modφ(p)) establish , Then the problem becomes Expand Euclid The classic question of .
So you can do it o ( l o g p ) o(logp) o(logp) It's time complexity , Compared with o ( p ) o(\sqrt{p}) o(p) Your practice is so excellent , Of course, the premise must be met g c d ( n , φ ( p ) ) = 1 gcd(n,\varphi (p))=1 gcd(n,φ(p))=1, This condition also comes from the necessary and sufficient condition for the solution of the tuou equation .
版权声明
本文为[Zimba_]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204230621425650.html
边栏推荐
- 1 + X cloud computing intermediate -- script construction, read-write separation
- Little girl walking
- Emuelec compilation summary
- Base de la technologie électronique numérique 3.1 aperçu du circuit de porte, 3.2 circuit de porte à diode semi - conductrice
- Thread scheduling (priority)
- ABAP CDs view with association example
- 机器学习(六)——贝叶斯分类器
- MySQL of database -- overview and installation
- [reading notes] Chapter 5 conditional statements, circular statements and block statements of Verilog digital system design tutorial (with answers to thinking questions)
- NLLLoss+log_ SoftMax=CE_ Loss
猜你喜欢
Leetcode题库78. 子集(递归 c实现)
What is monitoring intelligent playback and how to use intelligent playback to query video recording
亚马逊云科技入门资源中心,从0到1轻松上云
108. 将有序数组转换为二叉搜索树
Pre parsing of JS
Yyds dry goods inventory ubuntu18 0.4 install MySQL and solve error 1698: access denied for user ''root' '@' 'localhost' '
Amazon cloud technology entry Resource Center, easy access to the cloud from 0 to 1
Kettle experiment
Go language learning notes - language interface | go language from scratch
Practice of Flink streaming batch integration in Xiaomi
随机推荐
Your guide to lowering your cholesterol with TLC (continuously updated)
Go language learning notes - structure | go language from scratch
nn. Explanation of module class
Thread scheduling (priority)
SQL used query statements
[geek challenge 2019] havefun1
Colorui solves the problem of blocking content in bottom navigation
Secrets in buffctf file 1
3、 6 [Verilog HDL] gate level modeling of basic knowledge
Leetcode question bank 78 Subset (recursive C implementation)
Practice of Flink streaming batch integration in Xiaomi
Installation of data cleaning ETL tool kettle
npm ERR! network
JS what is an event? Event three elements and operation elements
SAP CR transmission request sequence and dependency check
NLLLoss+log_ SoftMax=CE_ Loss
Flutter 的加载动画这么玩更有趣
Codeforces Round #784 (Div. 4)
ALV tree (ll LR RL RR) insert delete
Using sqlmap injection to obtain the account and password of the website administrator