NanoApe's Blog

既是咸鱼又是辣鸡

【数论】原根、指标、同余方程

NanoApe posted @ 2016年1月04日 22:13 in 蒟蒻不撕烤智熵何来 , 409 阅读

 

原根

在(a,m)=1时,定义a对模m的指数$\delta m(a)$为使$a^d \equiv 1 \pmod{m}$成立的最小的正整数d

若$\delta m(a)=\varphi(m)$,则称a是模m的原根

模$m$有原根的充要条件是$m = 2 , 4 , p^n , 2p^n$,其中$p$是奇素数,$n$是任意正整数。

 

原根定理

素数p的原根个数为$\varphi(p-1)$

 

指标

当确定模p和原根g时,定义a的指标为$I(a)$为使$g^d \equiv a \pmod p$成立的最小的正整数d

 

指标法则

①$$I(ab) \equiv I(a)+I(b) \pmod {p-1}$$

②$$I(a^k) \equiv kI(a) \pmod {p-1}$$

 

求原根

从小到大枚举数$g$判断其是不是原根

对于一个待检查的$g$,检查下面式子是否成立

$$g^{(p-1)/a} \equiv 1 \pmod p$$

若成立则g不为原根(其中a为p-1的质因子)

 

求所有原根

若已求得一个模p意义下的原根g,则所有原根为

$$g^k \quad (gcd(k,p-1)=1)$$

 

二次剩余

与一个平方数模$p$同余的非零数为模$p$的二次剩余,与任意平方数模$p$都不同余的非零数为模$p$的非二次剩余

对于奇素数p,各有$\frac {p-1}{2}$个二次剩余和非二次剩余

 

勒让德符号

$$\left(\frac{a}{p}\right) = \begin{cases} +1 \\ -1 \end{cases}$$

 

二次互反率

设$p,q$为不同的奇素数,则

$$\left(\frac{-1}{p}\right)=\begin{cases} +1 \quad 如果p \equiv 1 \pmod 4 \\ -1 \quad 如果p \equiv 3 \pmod 4\end{cases}$$

$$\left(\frac{2}{p}\right)=\begin{cases} +1 \quad 如果p \equiv 1或7 \pmod 8 \\ -1 \quad 如果p \equiv 3或5 \pmod 8\end{cases}$$

$$\left(\frac{q}{p}\right)=\begin{cases} +\left(\frac{p}{q}\right) \quad 如果p \equiv 1 \pmod 4或q \equiv 1 \pmod 4\\ -\left(\frac{p}{q}\right)  \quad 如果p \equiv q \equiv 3 \pmod 4\end{cases}$$

 

广义二次互反律

设$p,q$为正奇数,则

$$\left(\frac{-1}{b}\right)=\begin{cases} +1 \quad 如果b \equiv 1 \pmod 4 \\ -1 \quad 如果b \equiv 3 \pmod 4\end{cases}$$

$$\left(\frac{2}{b}\right)=\begin{cases} +1 \quad 如果b \equiv 1或7 \pmod 8 \\ -1 \quad 如果b \equiv 3或5 \pmod 8\end{cases}$$

$$\left(\frac{a}{b}\right)=\begin{cases} +\left(\frac{b}{a}\right) \quad 如果a \equiv 1 \pmod 4或b \equiv 1 \pmod 4\\ -\left(\frac{b}{a}\right)  \quad 如果a \equiv b \equiv 3 \pmod 4\end{cases}$$

 

二次剩余求解

求$x^2 \equiv a \pmod p$最小非负整数解,其中p为素数

当p为2时,$x=a \mod p$

当p为奇素数时

由欧拉准则可知,$a^{(p-1)/2} \equiv \left( \frac{a}{p} \right) \pmod p$

当$a^{(p-1)/2} \equiv -1 \pmod p$时无解;

当$a^{(p-1)/2} \equiv 1 \pmod p$且$p \equiv 3 \pmod 4$时,$x=a^{(n+1)/4}$;

当$a^{(p-1)/2} \equiv 1 \pmod p$且$p \equiv 1 \pmod 4$时:

设$$b^{(p-1)/2} \equiv -1 \pmod p ~,~ i=(n-1)/2 ~,~ k=0$$

所以$$a^ib^k \equiv 1 \pmod p$$

若$i \mod 2=0$,则$i,k$同时取半,此时$a^ib^k \equiv \pm1 \pmod p$

若$a^ib^k \equiv -1 \pmod p$,则$k=k+(n-1)/2$

不断递归下去,直到$i \mod 2=1$

最后$x=a^{(i+1)/2}b^{k/2}$

 

离散对数(BSGS算法)

解$a^x \equiv b \pmod p$的最小整数解,其中p为素数

解法:BSGS算法

设s是满足$s*s>p$的最小整数

先预处理出$x^i(i \in [0,s-1])$并用Hash表储存

然后枚举$x^{is}(i \in [0,s-1])$,通过乘法逆元求出满足$c*x^{is}\equiv n(mod\;p)$的c,再判断c是否位于Hash表内,从而找到解

map<int,int>mp;

inline void BSGS(int a, int b, int p)
{
	mp.clear();
	int s=(int)sqrt(p); while (1LL*s*s<=p) s++;
	int cnt=1; rep(i, 0, s-1) 
		{if (!mp.count(cnt)) mp[cnt]=i; cnt=1LL*cnt*a%p;}
	int mul=cnt, tmp; cnt=1; rep(i, 0, s-1)
	{
		tmp=1LL*b*Pow(cnt,p-2,p)%p;
		if (mp.count(tmp)) {printf("%lld\n", 1LL*i*s+mp[tmp]); return;}
		cnt=1LL*cnt*mul%p;
		if (cnt==0) break;
	}
	puts("Orz, I cannot find x!");
}

 

离散对数(ExBSGS算法)

解$a^x \equiv b \pmod m$的最小整数解

首先在$[0,log(m)]$的范围内暴力枚举x

不妨令$d=gcd(a,m)$,若d=1则直接套用BSGS,若$b \mod d \not= 0$则无解

其余情况我们则将原式两边同除$d$

$$a^x \equiv b \pmod m ~\Rightarrow~ \frac ad*a^{x-1} \equiv \frac bd \pmod {\frac md}$$

继续重复,直到$d=gcd(a,\frac m{d_1d_2...})=1$

此时原式

$$\frac {a^k}{d_1d_2...}*a^{x-k} \equiv \frac {b}{d_1d_2...} \pmod {\frac {m}{d_1d_2...}}$$

$$a^{x-k} \equiv \frac {b}{d_1d_2...}*(\frac {a^k}{d_1d_2...})^{-1} \pmod {\frac {m}{d_1d_2...}}$$

接下来就求逆元完套BSGS

 

N次剩余求任意解

求$x^k \equiv b \pmod m$任意解,其中$gcd(b,m)=gcd(k,\varphi(m))=1$

设数$u$满足

$$ku \equiv 1 \pmod {\varphi(m)}$$

则解为

$$x=b^u \pmod m$$

证明:

$$\begin{align} x^k &= (b^u)^k \\ &= b^{uk} \\ &= b^{1+\varphi(m)v} \\ &= b \cdot (b^{\varphi(m)})^v \\ & \equiv b \pmod m \end{align}$$

 

N次剩余求所有解

求$x^k \equiv b \pmod p$所有解

设$g$为原根,令$g^y=x ~,~g^t=b$,则有$$g^{yk} \equiv g^t \pmod p ~\Rightarrow~ yk \equiv t \pmod {p-1}$$

求原根g完,t用离散对数求,y用Exgcd求,x用快速幂求

 

询问某数是否为两平方数之和

①素数$p$能表示成两平方数之和

条件:

$$p是两平方数之和 \quad \Leftrightarrow \quad p \equiv 1 \pmod 4$$

求具体方案:费马降阶法

②正整数$m$能表示成两平方数之和

将$m$分解成

$$m=p_1p_2...p_rM^2$$

其中$p_1,p_2,...,p_r$是互不相同的素因子

条件:$$p_i=2~或~p_i \equiv 1 \pmod 4 \quad (i \in [1,r])$$

②正整数$m$能表示成$m=a^2+b^2$且$gcd(a,b)=1$

条件:

$$m \mod 2=1 ~且~ p \equiv 1 \pmod 4 ~ (p|m)$$

$$m \mod 2=0 ~且~ m/2 \mod 2=1  ~且~ p \equiv 1 \pmod 4 ~ (p|m/2)$$

③c能表示成$c^2=a^2+b^2$且$gcd(a,b)=1$

条件:

$$p \equiv 1 \pmod 4 ~ (p|c)$$

 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter