wuvin

$P \le a$,$a,P$互质 求$x$使得 $a^x \equiv k \pmod P$

解法

令$q=\sqrt{P},x=e *q+ f (f<q)$

$a^f \equiv k * {a^{-qe}} \pmod n$

$f$的取值只有$q$个，$e$的取值也只有$q$个，所以暴力枚举两侧，hash判同即可

来填一下这个坑吧

这两个随机算法还是很好懂的

MR算法 素数判定

首先想必大家都知道费马小定理

如果n是质数，一定有$a^{n-1} \equiv 1 \pmod n$

那么逆否命题正确性与原命题相同，也就是

如果 $a^{n-1} \equiv 1 \pmod n$ , $n$一定为合数

注意：这里没有说这个为1是n是质数，但不为1一定是合数

所以如果要判断n是否是质数只需要选取多个a，再利用快速幂来判定n
如果多个a都说n是不是合数了，那么n基本上就是一个质数了
该测试单次正确的概率是75%所以多测试几次即可。

接下来就是巧妙的rho因数分解了（复杂度O(n^1/4 logn)）

(原文有错，留坑待填)