合成数のAKS witnessに関する実験的研究

• Item type: SIG Technical Reports(1)
• 公開日: 2004-03-19
• タイトル: 合成数のAKS witnessに関する実験的研究
• タイトル / 言語: en
• タイトル: Experimental research on AKS witness of the number of composition
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 明治大学大学院理工学研究科基礎理工学専攻
• 著者所属: 明治大学理工学部情報科学科
• 著者所属(英): en
• 著者所属(英): Computer Science Course, Major in Science, Graduate School of Science and Technology, Meiji University.
• 著者所属(英): en
• 著者所属(英): DepartMent of Computer Science, Meiji University
• 著者名: 瀬川, 紘; 玉木, 久夫
• 著者名(英): Kou, Segawa; Hisao, Tamaki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 正整数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以下であることを見出した
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2004, 号 34(2003-AL-094), p. 13-18, 発行日 2004-03-19
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会