离散对数 - jcvb

离散对数

jcvb posted @ 2013年12月08日 10:06 , 1629 阅读

[tex]a^x \equiv b (\text{mod} p)[/tex]求最小的非负整数x。默认[tex]a \neq 0,p\geq 2[/tex]。

·bzoj3239模为质数(裸的BSGS)
若[tex]p|a[/tex]。[tex]b \equiv 0[/tex]时,[tex]x=1[/tex];否则x无解。
否则a,p互质,由费马小定理,只需考虑[tex]x=0,1,\dots,p-2[/tex]。
取一个m,令[tex]x=mi-j[/tex],[tex]i=1,2,\dots,m[/tex],[tex]j=1,2,\dots,m[/tex]。此时[tex]x=0,1,\dots,m^2-1[/tex],所以只要取[tex]m^2\geq p-1[/tex]即可。
则[tex]a^{mi-j} \equiv b(\text{mod}p)[/tex]
等价于[tex]a^{mi} \equiv b\cdot a^j(\text{mod}p)[/tex]
等号两边分别遍历i和j,用hash表检查是否出现重复值,并保留最小解即可。

·bzoj2995模可能为合数
分解模[tex]p=\prod_{i=1}^k {p_i}^{d_i}[/tex],等价转换为k个形如[tex]a^x \equiv b(\text{mod}p^d)[/tex]的方程。若其中任意一个无解,则原方程无解。
①[tex]p \nmid a[/tex],则可以使用上述BSGS解出最小非负整数解[tex]x_0[/tex]。
再求[tex]a^x \equiv 1(\text{mod}p^d)[/tex]的最小正整数解K(即a对模p^d的阶),可以用BSGS,也可以枚举[tex]\varphi(p^d)=p^d-p^{d-1}[/tex]的所有约数进行检查。
则所有形如[tex]x\equiv x_0(\text{mod}K)[/tex]的非负整数x均是此方程的解。
(当[tex]a\equiv 1(\text{mod}p^d)[/tex]时此方法仍然有效,其中求得的K=1)
②[tex]p|a[/tex],且[tex]b\equiv 0 (\text{mod}p^d)[/tex]。
由于a中含有p的因子,那么在x充分大的时候一定能有[tex]a^x\equiv 0\equiv b(\text{mod}p^d[/tex]。
令[tex]a=p^qa'[/tex],[tex]q\geq 1,p\nmid a'[/tex],则[tex]x \geq x_0=\left \lceil d/q \right \rceil[/tex]均为此方程的解。
③[tex]p|a[/tex],且[tex]b \not \equiv 0(\text{mod}p^d)[/tex]。
由上讨论,可知此时x不会超过[tex]d/q[/tex],而这是一个很小的范围(在32以内)。所以若这种情况出现,只需对原方程暴力检验32以内的x后即可跳出。

假如不出现情况③,把①中得到的所有结果按中国剩余定理合并,并从中取满足②下界的最小x即为答案。

upd:后来学会了更加简单的消因子做法。。。稍微写一下吧

首先对x<=logp暴力。

现在假设x>logp,a^x=b (mod p)。

(边界:p=1,那么x就是任意非负整数)

设d=gcd(a,p),若d=1,则a存在逆元,可以BSGS。

若d!=1,需要有d|b,于是写成d*a'*a^{x-1}=d*b' (mod d*p'),

即a'*a^{x-1}=b' (mod p'),由于gcd(a',p')=1,a'是存在逆元的,那么a^{x-1}=b'*a'^{-1} (mod p'),继续求出x-1就好。

每次p至少减半,所以x至多减logp次,因此要对logp以内暴力。

Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee