Miller Rabin素性测试check函数while循环中x=mod(x,x,n)作用是什么
关于x = mod(x, x, n)语句的作用解释
首先明确:此处的三参数mod(a, b, n)是模乘实现,作用是计算(a * b) % n,因此mod(x, x, n)等价于计算 x的平方对n取模,是Miller-Rabin素性测试核心逻辑的必要步骤,原因如下:
- Miller-Rabin测试的前置推导中,我们会先将待判断数
n对应的n-1拆分为d * 2^s的形式(d为奇数)。对于素数来说,从a^d mod n开始最多反复平方s-1次,必然会得到n-1,否则n就是合数。 - 进入while循环前,代码已经判断过初始值
x = a^d mod n的状态:如果x等于1或n-1,已经直接返回true通过测试,进入循环说明当前x不满足这两个条件。 - 循环中每次对x平方取模,对应的就是指数从当前的d翻倍到2d,和下方
d <<= 1的操作对应。每次平方后做两次判断:- 如果平方后得到1:说明上一轮的x是模n下1的非平凡平方根(既不是1也不是n-1),只有合数才会存在非平凡平方根,因此直接返回false判定n为合数
- 如果平方后得到n-1:符合素数的性质,返回true通过当前基a的测试
- 循环终止条件
d == n-1对应的就是已经平方了s-1次,始终没有得到n-1,说明n不满足素数的性质,最终返回false。
另外补充:使用模乘函数而非直接计算x*x % n,是为了避免大整数乘法溢出(代码中ll一般指64位长整型,两个64位整数相乘会超出64位存储范围,模乘实现可以在计算过程中就做取模处理,避免溢出问题)。
内容的提问来源于stack exchange,提问作者Aubdur Rob Anik
相关产品推荐
相关产品推荐

