关于素数测试的问题

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

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

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

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