标签 - 数学

? 数学 ?    2017-03-19 20:44:16    261    0    0

Pa,a,P互质 求x使得 axk(modP)

解法

q=P,x=eq+f(f<q)

afkaqe(modn)

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

? 数学 ?    2017-03-19 20:39:39    471    0    0

来填一下这个坑吧

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

MR算法 素数判定

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

如果n是质数,一定有an11(modn)

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

如果 an11(modn) , n一定为合数

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

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

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

(原文有错,留坑待填)