WEKO3
アイテム
合成数のAKS witnessに関する実験的研究
https://ipsj.ixsq.nii.ac.jp/records/31859
https://ipsj.ixsq.nii.ac.jp/records/3185947548235-aedc-46d4-bb8a-8b0036165fb7
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
Copyright (c) 2004 by the Information Processing Society of Japan
|
|
オープンアクセス |
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
× Kou, Segawa
|
|||||||
論文抄録 | ||||||||
内容記述タイプ | 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 | |||||||
収録物識別子 | 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 | |||||||
出版者 | 情報処理学会 |