关于素数测试的问题

trisinker · 发表于 2010-1-20 23:35:16

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

在The Agrawal -Kayal -Saxena Test的素数测试中

Input: Integer n > 1
if (n has the form ab with b > 1) then output COMPOSITE;
r := 2;
while (r < n) {
if (gcd(n,r) is not 1) then output COMPOSITE;
if (r is prime greater than 2) then {
   let q be the largest factor of r-1;
   if (q > 4sqrt(r)log n) and (n^[(r-1)/q] is not 1 (mod r)) then
      break;
   }
r := r + 1;
}
for a := 1 to 2sqrt(r)log n {
if ( (x-a)^n is not (x^n-a) (mod x^r-1,n) ) then output COMPOSITE;
}

output PRIME;

这句：
if ( (x-a)^n is not (x^n-a) (mod x^r-1,n) ) then output COMPOSITE;
应该如何理解？

无心人 · 发表于 2010-1-21 09:54:29

难道是分别用两个数对取模？
还是对应取模?

wayne · 发表于 2010-1-21 10:21:18

本帖最后由 wayne 于 2010-1-21 10:23 编辑

2# 无心人

http://en.wikipedia.org/wiki/AKS_primality_test

账号		自动登录	找回密码
密码			欢迎注册

[求助] 关于素数测试的问题

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。