拟素数,欧拉拟素数还有强拟素数,他们之间有什么关系.希望各位懂这方面内容的大侠能讲解讲解.

Question

拟素数,欧拉拟素数还有强拟素数,他们之间有什么关系.希望各位懂这方面内容的大侠能讲解讲解.

Answer 1

拟素数就是这样的奇合数n
b^(n-1)=1 (mod n) （b是某一正整数） 这叫n基于b的拟素数
其实对于素数p
只要b不是p的倍数,b^(p-1)=1 (mod p)是一定成立的（这你应该知道吧n_n）
当然n是奇合数不是真的素数,所以就叫拟素数拉
欧拉拟素数好像是对于b,(b/n)（勒让德符号,如果你这个不知道的话我就没法说了,姑且我就当你是知道的）
有(b/n)=b^[(n-1)/2] mod n 好像是这样的,有点忘了
强拟素数要求更严格b^(n-1)-1=(b^[(n-1)/2]+1)(b^[(n-1)/4]+1).(b^[(n-1)/(2^k)]+1)(b^[(n-1)/(2^k)]-1)
右边分解出来的那么多项其中必须要有一个mod n为0
这些我只记得一个大概,具体你还是看一下数论方面的书吧
不过有一点我还是肯定的
是强拟素数就一定是欧拉拟素数,欧拉拟素数一定是拟素数