階 原根 離散對數
階
定義
\(a\mod p\) 的階是 \(a^e\equiv1\pmod p\) 的最小指數 \(e\)
符號語言: \(\delta_p(a)\) 代表 \(a\) 在 \(\mod p\) 的意義下的最小指數 \(e\) 使\(a^e\equiv1\pmod p\)
根據這個表格，我們可以舉出一些例子
\[\delta_5(1) = 1~~~\delta_7(4) = 3~~~\delta_{11}(9) = 5 \]原根
定義
\[a^{q}\not\equiv 1\pmod m~~~~~~~~~q,a\in[1,\varphi(m))\cup Z \]滿足上述則 \(a\) 是 \(\mod m\) 意義下的原根
最小原根 \(g\)
我們列舉，如果 \(gcd(now,n)\ne1\) 那一定不是原根
找出一個可能是原根的數，我們從 \([1-\varphi(n))\) 列舉每個 \(k\) 判斷 \(now^k\equiv1\pmod m\) 是否成立
如果全都不同余 \(1\) ，那么就找到了 \(g\) ，可以容易的找出其他原根：
while(++g){
int now=1,bj=0;
if(gcd(g,n)!=1) continue;
for(int j=1;j<phi[n];j++){
now=now*g%n;
if(now==1){
bj=1;
break;
}
}
if(bj==1) continue;
else if(bj==0){
break;
}
}
找出其他原根
我們認為 \(g\) 是最小的原根
尋找方法：
\[在gcd(k,\varphi(m))=1條件下,(g^{k})也是模m意義下的原根 \]我們考慮當 \(gcd(k,\varphi(m))=g\) 的時候 \({g^{k}}^{\frac {\varphi(m)} {k}}\) 會同余 \(1\)
代碼
int now=g;
ans[++cnt]=g;
for(int j=2;j<phi[n];j++){
now=now*g%n;
if(gcd(j,phi[n])!=1) continue;
ans[++cnt]=now;
}
有無原根
這些數有原根
\(結論：2,4,p^k,2×p^k，其中 p 為奇素數，k 為正整數，\)
證明詳見
原根
原根數量
我們在前面可以知道，當求出一個g(最小原根)，
\[在gcd(k,\varphi(m))=1條件下,(g^{k})也是模m意義下的原根~~~k\in[1,\varphi(m)) \]有多少個 \(k\) 滿足:\(k\in[1,\varphi(m))~~~gcd(k,\varphi(m))=1\)
其實就是 \(\varphi(\varphi(m))\)
總代碼：
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int phi[N],prim[N],v[N],vis[N],tot=0,ans[N],cnt=0;
int t,n,d;
void pre(){
phi[1]=1;
for(int i=2;i<=N-1;i++){
if(!v[i]){
prim[++tot]=i;
phi[i]=i-1;
}
for(int j=1;j<=tot&&prim[j]*i<=N-10;j++){
v[i*prim[j]]=1;
if(i%prim[j]==0){
phi[i*prim[j]]=phi[i]*prim[j];
break;
}else{
phi[i*prim[j]]=phi[i]*phi[prim[j]];
}
}
}
vis[2]=1;
vis[4]=1;
for(int i=2;i<=tot;i++){
for(long long j=1;j<=N;j=j*prim[i]){
if(j>N-10){
break;
}
vis[j]=1;
if(2*j<=N-1) vis[2*j]=1;
}
}
}//預處理phi和prime
int gcd(int x,int y){
if(y==0) return x;
return gcd(y,x%y);
}
void input(){
scanf("%d",&t);
for(int i=1;i<=t;i++){
cnt=0;
memset(ans,0,sizeof(ans));
scanf("%d%d",&n,&d);
if(!vis[n]){
printf("0\n\n");
continue;
}
int g=0;
while(++g){
int now=1,bj=0;
if(gcd(g,n)!=1) continue;
for(int j=1;j<phi[n];j++){
now=now*g%n;
if(now==1){
bj=1;
break;
}
}
if(bj==1) continue;
else if(bj==0){
break;
}
}
int now=g;
ans[++cnt]=g;
for(int j=2;j<phi[n];j++){
now=now*g%n;
if(gcd(j,phi[n])!=1) continue;
ans[++cnt]=now;
}
sort(ans+1,ans+1+cnt);
printf("%d\n",phi[phi[n]]);
for(int j=1;j<=phi[phi[n]]/d;j++){
printf("%d ",ans[j*d]);
}
printf("\n");
}
}
int main(){
// freopen("1.txt","w",stdout);
pre();
input();
return 0;
}
離散對數
就是對數的定義，只不過在模意義下
定義
對于正整數 \(p\) , \(p\) 的原根 \(g\) ，整數 \(b\)，使得 \(g^x\equiv b \pmod {p}\) 則稱 \(x\) 為 \(b\) 的離散對數，記作
\(\log_g(b)\)
性質
1.當 \(p\) 為質數時，\(?i ∈ [0, p ? 1]\) 在 \([0, p ? 1]\) 范圍內都有唯一對應的離散對數，
2.當 \(p\) 為奇質數的冪時，\(p\) 的倍數不存在離散對數，通常需要特殊處理，\(2p^ k\) 也類似，
利用離散對數可以將模 \(p\) 意義下的 \(xy\) 轉化為 $ g^{\log_g
(x)+\log_g
(y)}$
BSGS
題目描述：
已知 \(a,b,p\)，求模 \(p\) 意義下 \(x=\log_a(b)\) ，保證 \(p\) 為質數 ，
根據性質1，在 \(x\in[1,m]\implies b\in[1,m]\)
我們列舉 \(x\) ，可以得到答案，但時間復雜度不能接受
我們考慮更優秀的列舉：
\(設x=A\times\sqrt m-B(A,B\in[1,{\sqrt m}])\)
可以發現現在依舊 \(x\in[1,m]\)
轉換一下
\[a^{A\times\sqrt m-B}\equiv b\pmod m\implies a^{A\times\sqrt m}\equiv b\times a^B\pmod m \]發現現在只有兩個未知數A,B我們可以先列舉一次B預處理
用map記錄所有 \(b \times a^B~ mod~m\)
再列舉A算出 \(a^{A*\sqrt m}~mod~m\) 在map找找有沒有對應的
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/554370.html
標籤：其他
下一篇：返回列表