@techreport{oai:ipsj.ixsq.nii.ac.jp:00031859,
 author = {瀬川, 紘 and 玉木, 久夫 and Kou, Segawa and Hisao, Tamaki},
 issue = {34(2003-AL-094)},
 month = {Mar},
 note = {正整数nに対して合同式(x+a)^n !≡ x^n + a  mod(n  x^r - 1)を満たしかつgcd(a  n) = 1であるような正整数rと整数aの対はnが合成数のときかつそのときに限り存在する。このような対(r a)を合成数nのAKSwitnessと呼ぶことにする。Agrawal  KayalとSaxenaの決定的多項式時間素数性判定アルゴリズムは、(1) 与えられたnに対してrがある性質を満たすとき、もしnが素数の冪乗でない合成数ならば1 ≦ a ≦ O √r log nの範囲のaで(r a)がnのAKS witnessであるものが存在する、(2)その性質を満たすr = O(log^5 n)が必ず存在する、ことに基づいている。我々は小さい値のAKS witnessの存在について実験を行った。結果の一部として、10^11以下のすべての合成数nおよび10^16以下のすべてのCarmichael数nに対して(r 1)がnのAKS witnessであるようなrの最小値は0.49log n以下、ある1 ≦ a ≦ rに対して(r  a)がnのAKS witnessであるようなrの最小値は0.37log n以下であることを見出した, For any integer n ≧ 2, congruence (x+a)^n !≡ x^n +a mod(n, x^r -1) is satisfied by some positive r and a with gcd(n,a) = 1 if and only if n is a composite number. We call such a pair (r,a) an AKS witness of the composite n. The deterministic polynomial time primality algorithm of Agrawal, Kayal and Saxena is based on the facts: (1)if r satisfies some condition with respect to given n, and if n is a composite but is not a power of a prime, then (r,a) is an AKS witness of n for some 1 ≦ a ≦ O(√r log n);(2)for every n this condition is satisfied by some r = O(log^5 n). We have conducted experiments on the existences of AKS witnesses with small values. In particular, we have found that, for every composite n ≦ 10^11 and for every Carmichael number n ≦ 10^16, n has an AKS witness (r,1) with r ≦ 0.49log n and an AKS witness (r,a) for some 1 ≦ a ≦ r with r ≦ 0.37log n.},
 title = {合成数のAKS witnessに関する実験的研究},
 year = {2004}
}