猿问

米勒拉宾素性检验问题。。。有一句话不明白??算法大神在吗。。。。。

渣渣菜鸟一枚,大神有空顺便给个建议。。。。

关于米勒拉宾素性检验证明里的一句话引出的疑问------

①、如果p是素数,x是小于p的正整数,且x^2 = 1 mod p,则x要么为1,要么为p-1。

我发现即使p不是素数,好像也能这么说啊,比如p=9,那么取 x(0<x<9) ,令x**2=1(mod 9), x只能为1或者8,所以这句话和p是不是质数没有必然关系,不是质数也可以这么讲啊。。。

②、还有结论, 如果对于任意一个小于p的正整数x,发现1(模p)的非平凡平方根存在,则说明p是合数。

但是后面又有补充。。。。

③、若p是一个大于2的素数,那么如果一个数与1或者-1模n同余(即 x = 1 (mod p) 或者 x = -1 (mod p)),那么它就叫做1模n的一个非平凡的平方根。

而事实上,没有1模p的非平凡的平方根存在。   (注:平凡根指1或-1(mod p) , 否则为非平凡根。)

结束-----这是在逗我吗。。。(主要因为是菜鸟.....

问题:针对以上①②③,望大神解答一下,不胜感激!!


asdhjhg
浏览 2998回答 1
1回答
随时随地看视频慕课网APP
我要回答