什么是强伪质数?
发布网友
发布时间:2022-04-23 14:15
我来回答
共1个回答
热心网友
时间:2023-07-13 16:33
强伪质数又叫强伪素数,是数论中的一个概念。
设n是一个大于4的奇整数,s和t是使得(n-1)=2^s*t的正整数,其中t为奇数,设B(n)是如下定义的整数集合:
a属于集合B(n)当且仅当2≤a≤n-2且
1: a^tmodn=1
2: 存在整数i,0<=i<s满足a^((2^i)*t) mod n=n-1
当n为素数时, 任意a在2和n-1中,均有a属于集合B(n)
当n为合数时,若a属于集合B(n),则称n为一个以a为底(基)的强伪素数,称a为n素性的强伪证据。
n为素数,说明它对所有底均为强伪素数
参考资料:素数测试算法(基于Miller-Rabin的MC算法)