修 士 学 位 論 文
題 名
Miller‑Rabin素 数 判 定 法 に お け る誤 り確 率 の 上 限
指 導 教 授 鈴 木 登 志雄 准 教 授
平 成23年1月 7日 i提 出
首都大学東京大学院
理 工 学 研 究 科 数 理 情 報 科 学 専 攻 学修番号09878307
氏 名 後 藤 大 和
論 文 題 名:MillerRabin素 数 判 定 法 に お け る誤 り確 率 の 上 限
素 数 は 無 数 に 存 在 し、今 日、暗 号 論 な ど様 々 な ところで 利 用 され てい る。与 え られ た 自然 数 が 素 数 で あ るか 判 定 す る方 法 の 一 つ として『Miller・Rabin素 数 判 定 法 』とい う素 数 判 定 法 が あ る。
MillerRabin素 数 判 定 法 は確 率 的 素 数 判 定 法 と呼 ばれ 、判 定 す る 自然 数 が 素 数 で あれ ば必 ず 「素 数 の 可 能 性 あ り」と出力 す るが 、合 成 数 で あってもある一 定 の 確 率 で 「素 数 の 可 能 性 あ り」と 出 力 してしまう。しか し、現 在 発 表 され て い る唯 一 の 決 定 多 項 式 時 間 で 計 算 で き る 『AKS素 数 判 定 法 』 は 計 算 量 が 高 す ぎ る た め 、 少 な い 計 算 量 で 済 むMillerRabi鍛 素 数 判 定 法 等 の確 率 的 素 数 判 定 法 が よ く利 用 され て い る。
本 論 文 で は 、一 般 的 に 実 用 で きるレベ ル で は ない もの の 、簡 単 な前 処 理 を行 うことで 、あ る特 定 の 場 合 を 除 きMillerRabin素 数 判 定 法 に お け る誤 判 定 の確 率 を下 げ る方 法 を紹 介 す る。
目次
§1
§2
§3
§4
§5
§6
§7
§8
序 と 記 法 の 説 明
MillerRabin素 数 判 定 法 とは 基 本 事 項 の 復 習
Miller‑Rabin素 数 判 定 法 の アル ゴ リズ ム と正 当 性 Miller‑Rabin素 数 判 定 法 の 計 算 量
MillerRabまn素 数 判 定 法 の 誤 り確 率 の 証 明 MillerRabin素 数 判 定 法 の 誤 り確 率 の 低 減 今 後 の 課 題
134910101926
指導教授 鈴木登志雄 准教授
平 成23年1,月7日 提 出
首都大学東京大学院 理工学研 究科 数理情報科学専攻 09878307後 藤大和
09878307後 〕藤 大 和
が1序 と 認 滋 の 詑 男 序
素 数 と は 、1と そ れ 自身 しか 正 の約 数 を持 た な い2以 上 の 自然 数 の こ とで あ る。 素 数 は 無 限 に存 在 し、 暗 号 論 等 で 重 要 な 役 割 を 持 っ て い る。
素 数 を判 定 す る方 法 は 様 々 な 例 が 挙 げ られ る が 、2002年 に 決 定 多 項 式 時 間 で 計 算 で き る 方 法 と して 『AKS素 数 判 定 法 』 が 発 表 され た 。 しか し、 時 間 計 算 量 を表 す 多 項 式 の 次 数 が 高 す ぎ る た め 実 用 的 範 囲 で 利 用 出 来 る も の で は な く、 実 際 に は 『MillerRabin素 数 判 定 法 』 や 『Solovay・Strassen素 数 判 定 法 』 とい っ た 確 率 的 素 数 判 定 法 が 利 用 され て い る の が 現 状
で あ る。 ち な み に 確 率 的 素 数 判 定 法 と は 、 判 定 した い 自然 数 を 「合 成 数 」 か 「素 数 の 可 能 性 が あ る 」 の どち らか に判 定 す る 判 定 法 で あ る。 「合 成 数 」 と判 定 した 場 合 は 確 実 に合 成 数 で あ る が 、 「素 数 の 可 能 性 が あ る 」 と判 定 した 場 合 は ま だ どち ら と もい え な い 状 態 で あ る。
そ の た め 実 際 に利 用 す る と き は 、 こ の 確 率 的 素 数 判 定 法 を繰 り返 し行 う こ と に よ っ て 精 度 を 高 め る の が 一 般 的 で あ る。
今 回 は そ の確 率 的 素 数 判 定 法 の うち 、[3】、 【4]で導 入 され た 『MillerRabin素 数 判 定 法 』 に つ い て 論 じ る。
本論文では
1:MillerRabin素 数 判 定 法 の アル ゴ リズ ム とそ の 正 当 性 。
1
2:η が 合 成 数 で あ る とき"素 数 の 可 能 性 あ り"と 出力 す る確 率 が 一 以 下 で あ る証 明 。4
3さ ら に 、実 用 的 な レベ ル で は な い も の の簡 単 な 前 処 理 を行 う こ とで 、 ηが 合 成 数 で あ る
と綜 数 の可能 脚 ・ と出力する確率が・ある特定の場合 を除 き砲 下(正確に
は ユZL以 下)に な る こ との 証 明.
1024 を 述 べ る 。
な お 、 誤 り確 率 とは 、 「ηが 合 成 数 で あ る に も関 わ らず"素 数 の 可 能 性 あ り"と 出 力 す る 確 率 」 とす る。
記 法 の 説 明
部 分 集 合 の 記 号 「⊂」 は 集 合 竣,βが 躍=Bの と き も含 め て 」 ⊂Bと す る。
脚 を 法 とす る剰 余 類 を α",な ど と表 記 し、 特 に ηを 法 とす る剰 余 類 を αな ど と表 記 す る。
ηの 規 約 剰 余 類(剰 余 類 群 の 元 の 中 か ら、 乗 法 逆 元 を もつ も の)の 集 合 を(Z/ηZ)× とお く。
つ ま り(Z/ηZ)㌧{α1(α,η)瓢1}と す る。
η を 法 とす る剰 余 類 の 元gの 元 位 数 を}g},と 表 記 す る。
0を 次 の よ うに 定 義 す る。
!=0(9)⇔ あ る0以 上 の 整 数 ん に対 し!=0(910gl9)
詳 し く は[1]De蝕ition2.2.5ま た は[5]注 意1.3.2を 参 照 し て い た だ き た い 。
09878307後 藤 大 和
52遡 θr・磁 ゐ血 素翻 鰭 くをな
MillerRabin素 数 判 定 法 と はSt欝ongprobableprimetest(強 擬 素 数 テ ス ト)と も 呼 ば れ 、 そ の 名 の 通 り あ る 整 数 が 素 数 か ど う か 判 定 す る ア ル ゴ リ ズ ム で あ る 。 素 数 か ど う か 判 定 し た い 奇 数 を η と す る と
η が 素 数 な ら ば 、 必 ず"素 数 の 可 能 性 あ り"と 出 力 し
η が 合 成 数 な ら ば 、!以 下 の 確 率 で ・素 数 の 可 能 性 あ り ・ と 勘 、 つ ま り 4
触 上 の 確 率 で ・合 成 数 ・ で あ る と 判 定 さ れ る.
4
(な お 逆 に 、 入 力 に 対 し"合 成 数"と 出 力 され た と き は 、 そ の 入 力 は 必 ず 合 成 数 で あ る。) この ア ル ゴ リズ ム を利 用 す る と き 、基 本 的 に は 何 回 か繰 り返 し行 うこ と が 多 い 。 例 え ば 、ん
回 行 っ 腸 合 、 そ の 信 用 度 は{H1)・}以 上 の も の と な る 。 た だ そ れ ゆ え 、 蜷 レ・く ら 大 き 4
く と っ て も"素 数 で あ る"と 言 い き る こ と は 出 来 な い 。
【MillerRabin素 数 判 定 法 の ア ル ゴ リ ズ ム 】
123・4
5.
η一1議23・ ア,(7は 奇 数)と な る5,rを 求 め る 。 1≦ α ≦ η一1な る 自 然 数 α を ラ ン ダ ム に と る 。 Z》:=αアrnodη
bニ1ま た は ろ=η 一1の と き 、"素 数 の 可 能 性 あ り"と 出 力 し て 終 了 。 〃 そ う で な い と き 、 以 下 を3‑1回 繰 り返 す 。
i.ゐ に う2modη を 代 入 。
ii.も し わ 瓢 η一1な ら ば 、"素 数 の 可 能 性 あ り"と 出 力 し て 終 了 。//
"素 数 で な い"と 出 力 し て 終 了
。 〃
(以 下"素 数 の 可 能 性 あ り"を 、̀̀Ybs?"と 表 記 す る 。)
53塞 本 算 贋 の 復 習
本 節 で は 、 以 下 の 議 論 に 必 要 な 代 数 学 の 初 歩 等 を復 習 す る 。 本 節 の 執 筆 に は 田 を参 考 に し た。
Fermatの 小 定 理
素 数pに 対 し、 整 数 αを 任 意 に と る 。 この と き
αρ≡ α(mod1ワ)が 成 立 す る。
証 明:
数 学 的 帰 納 法 を使 っ て 証 明 す る。
α竃0,1の と き 、 明 ら か に 成 立 す る。
α竃2の と き 2P認(1+1)ρ
一 Σ 。c、
'瓢O
P(ρ 一1)+
̲+ .ρ千1=1+P+2
よ っ て2ρ 竃2(mod .ρ)を 得 る 。
α ≧3の と き 、 〆 § α(modρ)と 仮 定 す る と 、 同 様 に
(α+1)」o≡{2rP+1ρ(mod、 ρ)
≡ 〆+1
≡≡α+1(rnod 、ρ)
(な お 、 α が 負 の と き も 同 様)
よ っ て 、 数 学 的 帰 納 法 よ り 証 明 さ れ た 。 口
09878307後 藤i大 和
補 題0素 数 ρ に 対 し、1≦ α<ρ α2mod .ρ=1と す る と o雛1ま た は α=ρ 一1と な る 。
証 明:
題 意 よ り
(α2‑1)modp瓢0
⇔(α+1)(α 一1)modρ 瓢0
こ れ よ りpは(α+1)(α 一1)の 約 数 と な り 、 ρ1(α+1),ρ1(α 一1)の ど ち ら か 、 ま た は 両 方 を 満 た す 。 よ っ て 、pと α の 範 囲 か ら α=1ま た は α=ρ 一1を 得 ら れ る 。 □
補 題1.1G,H:有 限 群,H⊂Gの とき 、Hの 位 数 はGの 位 数 の 約 数 で あ る。
特 に 、g6Gの 位 数 は 、gの 生 成 す る巡 回 部 分 群 の 位 数 に 一 致 す る の で 、 群Gの 位 数 の約 数 で あ る。(証 明 略)
補 題1.2.1合 同 式 砿 … 戻modη)は 、@η)=1の と き 、 解 は 唯 一 と な る 。
証 明:
(α,η)=1よ り 、 αo+働=1を み た す あ る 整 数 α,β が 存 在 す る の で 解 の 存 在 は 明 ら か 。
(α,η)=1の 時 、(Z/ηZ)={朔,f2,.̲.,鴎}と す る 。
ακゴ……αrノ(modη)⇔ α(κ∫一 κノ)ミ0(modη)よ り 、 κ〜一 κノ ≡0(modη)
よ っ て 亙=1『1と な り 、 ακ 鋸 わ(modη)の 解 は 唯 一 と な る 。 口
補 題1.2素 数 ρ に 対 し 、♂ 叢1(mod .ρ)の解 の 個 数 は 、法pで 合 同 な も の を 同 一 視 し て 高 々 吻 個 で あ る 。
証 明:
帰 納 法 を 利 用 し て 証 明 す る 。
溺 雛1の と き 、 補 題1。2ユ よ り解 は 唯 一 と な る 。
以 下 吻 ≧2の と き を 考 え る 。一 般 に 、多 項 式 プ(κ)=κ'〃‑1を(κ 一 の で 割 っ た 商 をg(κ)、
余 り をRと す る と!(κ)=(κ 一 のg(κ)+Rと か け る。α が κ"L1…0(modp)の 解 で あ る と きR≡0(mod、 ρ)と な り ∫(κ)≡0(modρ)か ら(κ 一 の9(κ)≡0(modρ)が 得 ら れ る 。 よ っ て 、1ワ が 素 数 で あ る こ と か ら κ 一〇 ヨ0(mod .ρ)ま た はg(κ)…0(mod.ρ)と な り 、
κ一 α 叢0(願od ,ρ)の と き 、 補 題1.2.1よ り解 は 唯 一 。g(κ)羅0(mod.ρ)の と き 、g(κ)は 吻 一1次 式 で あ る こ と か ら 、 帰 納 法 の 仮 定 に よ り解 の 個 数 は 高 々 〃卜1個 で あ る こ と が 分 か る 。
こ れ よ り補 題L2は 成 立 す る 。 目
補 題1(Z/pZ)xは 、 位 数 ρ の 巡 回 群 で あ る 。 証 明:
ま ず(Z/pZ)xが 巡 回 群 で あ る こ と を 示 す 。
(Z/pZ)xで 位 数 最 大 の 元 をgと し 、gの 位 数 を 吻 と お き 、 〃2=ρ 一1を 示 せ ば 良 い 。
背 理 法 で(Z/ρZ)xが 巡 回 群 で あ る こ と を 示 す 。g,彫 を 前 述 の よ う に 置 き 、 〃2<ρ 一1と 仮 定 す る と 、 こ れ は κ"一 』0(modP)の 解 で あ る 。こ の と き 、1,9,92,.̲,9耐 は す べ て
κ溺 一bO(mod .ρ)の 解 と な り 、ρ を 法 と し て 合 同 で な い 。 よ っ て こ れ ら1,g,g2,.̲,g1洞 が 解 と な り 、 補 題1.2よ り他 に 解 は 存 在 し な い 。
09878307後 藤i大 和
ま た 、1(Z/pZ)×1㍉ ρ一1よ り、 仮 定 か らg'で な い 元 乃 が 存 在 す る 。 こ こ で1乃1≒ η と す る 。(η>1)乃 は κ海 一bO(modρ)の 解 で な い の で η は 吻 の 約 数 で な い 。
(1)@,η)=1の と き 、g乃 の 位 数 が 溺 よ り 大 き く な る こ と を 示 す 。(g乃 ソ …1(mod,ρ)と す る と 、Igト 〃2よ り1≡(g乃)'"〜 ≡ 乃伽 と な り 川 伽 こ れ よ り 川'を 得 る 。(同 様 に
瑚 の
よ っ て ∫は η と 脚 の 公 倍 数 と な り 、 伽,η)=1よ り、'は 脚 の 倍 数 と な り」 〉 〃2が
得 られ 、 〃2が 最 大 位 数 で あ る こ と と矛 盾 。
こ れ よ り 〃7=ρ 一1と な り 、 こ の よ う な 乃 は 存 在 せ ず 、(Z/1ワZ)xはgを 生 成 元 と す る 巡 回 群 と な る 。
紳"瓶
(2)(〃2,η)=4>1の と き 、 溺,η の 最 小 公 倍 数 を1と す る と 、1=撃 が 分 か る 。(号,号)コ1
より・4一 鵜 ・・膿 素騰 辮 した とき・各因辮 は 器 のせいぜレ・どち
ら か 一 方 の 因 数 で あ る 。 こ こ で 、@o,ηo)瓢1,脚oηo=1と な る よ う 醒o,ηoを 設 定 す る 。
(「疏 藷 どち らかの因魏 らそち らに4戸 かけ・ どちらので もなければ好き
な 方 に か け る 」 と い う操 作 を'=1か ら ∫=た ま で 行 う こ と で 吻o,ηoを 作 成 で き る 。)
こ の 時 、(1)よ りg〃 謬吻 〃oの位 数 は1=moπoと な る 。 η は 脚 の 約 数 で な い の で 、1>〃2
こ れ は 吻 が 最 大 位 数 で あ る こ と と矛 盾 す る 。
よ っ て 〃2=p‑1と な り 、(Z/pZ)xはgを 生 成 元 とす る 巡 回 群 で あ る 。
これ よ り補 題1は 成 立 す る。 目
補 題4.1(中 国 式 剰 余 定 理 、 孫 子 の 定 理)
鵬 ηを 互 い に 素 な 整 数 とす る と き 、 連 立 合 同 式
{
κ …昭(mod吻
は 、 ㈱ を 法 と し た 唯 一 の 解 を 持 っ 。 κ …竃15(modη)
証 明:
ま ず は 解 の 存 在 に つ い て 示 す 。 α=1,b諏0の 時@,の 灘1よ り、 補 題1.2.1か ら 鷹 ミ ー1(modη)は 解 を も っ 。 こ の 解 を ん と し 、 κ。=1+磁 と す る と 、
κ。 …≡1(mod〃2),κo≡1‑1≡0(modη)と な る 。 α=0,ゐ=1の 時 も 同 様iに κ1≡0(mod〃2),κ1≡1(modη)な る κ1が 生 成 で き る 。
よ っ て 、 一 般 の α,ゐに 対 し 、 κ=α κo+わ κ1が 解 と な る 。 つ ま り解 は 存 在 す る 。
次 に 解 の 一 意 性 を 示 す 。 κ,x'を 連 立 合 同 式 の 解 とす る(κ ≧ κ'と す る)。 κ一 κ響は 、 〃7,ηど ち ら を 法 に し て も0と 合 同 に な る 。 つ ま り 刎(κ 一 κ,),川(κ 一 κ')と な る 。 こ こ で 溺 と η は 互 い に 素 よ り 、 駕 川 κ 一 κ響⇔ κ一 κ㌧0(mod御 η)
こ れ よ り連 立 方 程 式 の 解 は 、〃卿 を 法 と し た 唯 一 の 解 を 持 つ 。 目
09878307後 藤 大 和
54澁 望㊧θゑあ素薮 綻 法の正 』当荏
本 節 で は 、MillerRabin素 数 判 定 法 が"素 数 で な い"と 判 定 し た と き は 必 ず 「η は 合 成 数 」 で あ る こ と(す な わ ち 、 η が 素 数 の と き̀脆s?"と 判 定 す る こ と)を 証 明 す る 。
5,ア を 上 記 の よ う に 設 定 す る 。対 偶 を 示 す た め 、η を 素 数 と し 、任 意 の 整 数1≦ α ≦ η一1が α7≡1(modη)…(α)
0≦ ヨ4≦3‑1鉱02%ミ η一1(1nodκ)…(β)の ど ち ら か を 満 た す こ と を 示 せ ば 良 い 。
Fermatの 小 定 理(α 屈 ≡1(modη))を 使 っ て 証 明 す る 。 α〃一1遷 αゴ』1(modの よ り 、 補
盤
題0か ら 、こ の 平 方 根 は α2=α 「1「 …1(modη)ま た は η一1(modη)と な る 。(こ こ で 、η一1 型
の と き は(β)が 成 立 。)α2ヨ1(modη)の と き は 、 ま た 更 に そ の 平 方 根 に っ い て 考 え る と 、 そ の 値 は 同 様 に 、1(撮odη)ま た は η一1(modη)と な る 。 こ の 操 作 を 何 度 も 繰 り返 し 、 一 度
も η 一1(modη)の 値 を と ら な い ま ま6濡0と な っ た と き α207離 〆 華η 一1(modη)と な り 、
(α)が 成 立 す る 。
よ っ て 、MillerRabin素 数 判 定 法 の 正 当 性 が 示 さ れ た 。 □
が5遡 θ望痂 ゑ血薫i糊 灘 の評籟
MillerRabin素 数 判 定 法 を1回 繰 り返 し 実 行 す る と き の 計 算 量 は 、四 則 演 算 の 回 数 に 換 算 し て0(140gη)で あ り、 ビ ッ ト演 算 の 回 数 に 換 算 す る と 、0(1・(10gη)3)で あ る 。
ま た 、 ん ビ ッ トの 整 数 同 士 の 四 則 演 算 を0(紛 回(す な わ ち 、0(ル(109ん γ)回 た だ し1は
定 数)で 実 装 す る 方 法 が 知 られ て い る 。 こ の 「高 度 な 実 装 」 を 用 い る と 、MillerRabin素
数 判 定 法 の1回 反 復 の 計 算 量 は 、 ビ ッ ト演 算 で1・0((logη)2)と な る 。
が6遡 θノぜ勉ゐ血 素i糊 融 の誤 ク礎率
さて 、 さ き に 「ηが 合 成 数 の と き 、
本 節 で は そ の 証 明 を 紹 介 す る。
脆 ・γ と勘 す る確率は劉1 下」 と述べた・
定 理A.
奇 数 η が 合 成 数 の と き 、MillerRabin素 数 判 定 法 が 『Ybs?と 返 す よ う な 乱 数 α の 個 数 は 、 1
0<α<η の う ち 、 高 々 一 で あ る 。4
こ れ を証 明 す る に あ た っ て
① ηが 平 方 因 子 を持 ち 、Ybs?と 出 力 した とき
② ηが 平 方 因 子 を 持 た ず 、Ybs?と 出 力 した と き の 二 つ に 場 合 分 け をす る。
09878307後 藤 大 和
まず 、① の 場 合 の 証 明 の 準 備 と して 、 以 下 で い くつ か の 補 題 を証 明 す る。
補 題2(Z/ .ρ2Z)× は 巡 回 群 で あ り 、 位 数 はp(ρ 一1)で あ る 。 証 明:
(Z/.ρZ)× の 生 成 元9を え ら ぶ 。g(modρ)は9ρ 一玉強1(mod.ρ)(フ ェ ル マ ー の 小 定 理)を 満
た し 、0<∫<ρ 一1の と きg̀≠1(mod1の
こ こ で(9ρ 一1)ρ=@ρ+1)ρ=β ρ2+1≡1(mod ,ρ2)(α,β は あ る 整 数)よ り 〆 を 法 と す る と9ρ ψ'1)…1(mod〆)と な る 。 そ し て 、51ρ 一1,3<ρ 一1な る3に 対 し 、
9㌧1(mod〆)と す る と95ヨ1(modρ)と な り 、lgし=」 ρ一1に 反 す る 。
ま た 、gρ5羅1(modρ)の と き 、1三gρ5=(〆)㌧g3(modρ)と な りigし ㍉g‑1に 反 す
る 。
よ っ てg(mod .〆)の 位 数 は1ρ 一1,ρ(p‑1)の ど ち ら か で あ る 。(ρ(ρ 一1)の 時 はgが 生 成 元 と な り、 位 数 は ρ(1ワー1)と な る 。)
9(mod.ρ2)の 位 数 が 」9‑1の と き 、(P+1)9が 生 成 元 と な る こ と を 示 す 。 {(p+1)g}ρ 一1憲(ρ+1)坦gρ 一1…簗(」ρ+1)ρ i
匪1+(ρ 一1)ρ+〔 ζ 一1〕 〆+ ・… 蕊1一 ρ(m・d〆)
こ こ で 、1‑ .ρ≡1(mod〆)⇔.ρ ≡0(mod.ρ2)は 成 立 し な い た め(ρ+1)gの 位 数 はp‑1 で は な い 。
よ っ て{(1ワ+1)g}ρ 密g華1(modρ2)よ り(1ワ+1)gの 位 数 は ρ(ρ 一1)と な り 、(1ρ+1)g は 生 成 元 で あ る 。こ れ よ り(Z/ .ρ2Z)xは 巡 回 群 と な り、位 数 はp(ρ 一1)と な る 。 日
補 題3位 数 〃2>2の 巡 回 群Gに お い て κ々雛1の 解 の 個 数4は4=(ん,〃2)個 で あ る 。 証 明:
Gの 生 成 元 をgと す る とG《1(=g◎),g,g2,g3,̲.,g"2‑i}と な る 。 こ の と き 、gノ が 譜 蕊1の 解 ⇔(gノ)た=1⇔gノ ん 鵠1
⇔ 碗 ん⇔ 姿1夢 ここで轍 脚 ÷ 告は互い1こ素より・欝 謄 ノ
・≦ブく磯 囲考 の倍数 となるような プ1姻 より・ κ㌧1の 解の騰 は姻 であ
る 。 口
こ れ よ り① の 場 合 の 証 明 を お こ な う。
①nが 平 方 因 子 を 持 つ と し て そ れ を .ρとす る。Miller・Rabin素 数 判 定 法 の 性 質 よ り αη一1釜1(modη)
ρ2擁 よ り、 法 を ρ2に し て も αη一1…羅1(mod、 ρ2)
(Z/ρ2Z)xは 補 題2よ り位 数 ρ(ρ 一1)の 巡 回 群 な の で 、 補 題3よ り α は 〆 を 法 とす る 剰 余 類 と し て 、 解 の 個 数 は4=(アz‑1,1フ(ρ 一1))個 で あ る 。 こ こ で .ρ1ηよ り、pは η一1の 約 数 で な い の で 、pは4の 約 数 で な い 。 よ っ て4は 高 々 ρ 一1で あ り 、 こ れ よ り条 件 を み た す α の 個 数 が 、 ρ2で わ れ な い α全 体 の 中 に 占 め る 割 合 は 、 法 をp2と し た 剰 余 類 で 考 え る と 、 高 々
鍋 漏 ≦去(な ぜならP≧3)
これ を ηを 法 と した 剰 余 類 で 考 え る に は
09878307後 藤 大 和
(1》‑1)× 一了
(ρ2‑1)× 些
張 は 成 り立 っ 。
とす れ ば い い の で 、同 様 に1と な り、① の 場 合 に 定 理Aの 主 4
口
次 に 、 ② を 証 明 す る前 に 以 下 の い くつ か の 事 柄 を証 明 す る。
中 国 剰 余 定 理 よ り次 の こ と が い え る 。 補 題4〃z,η を 互 い に 素 な 整 数 と す る 。
!:Z/脚 ηZ→(Z/襯Z)×(Z/ηZ)を!(κ 脚)=(κ"ρ κ。)と す る と 、 プ は 上 へ の 1:1写 像 で あ る 。 ま た こ れ よ り プ を 既 約 剰 余 類 群 上 に 制 限 し て 、 次 の よ う な 上 へ の 1:1写 像 が 得 られ る 。
∫:(Z/〃 御Z)x→(Z/加Z)× ×(Z/ηZ)x
系5素 数 ρ ≧3に 対 し 、(Z/.ρZ)xに お け る κ女鷹1の 解 の 個 数 は 補 題3よ り(ん,.ρ4)
で あ り 、(Z/ .ρ2Z)× に お け る κ々 コ1の 解 の 個 数 は(ん,.ρ(ρ一1))個 で あ る 。
(補 題2よ り1(Z/.ρ2Z)x}=p(ρ 一1)で あ る た め 。)
補 題6〃2,η:互 い に 素 な 整 数 とす る 。
孟 ⊂(Z/〃zZ)×,β ⊂(Z/ηZ)× を 集 合 と し 、1刻 篇5,1捌 訂 と す る 。
こ の と き 、(Z/〃zηZ)xの 元 κ で 、 κ(mod〃2)ε 殴 か っ κ(modη)6B
と な る よ う な も の の 数 は 、 舘 個 で あ る 。
証 明:
こ れ を 満 た す も の は 、 プ:(Z/〃 〜ηZ)× →(Z/〃2Z)x×(Z/ηZ)xで 考 え られ る の で 、
補 題4よ り 舘 個 で あ る 。 口
こ れ よ り② の 場 合 の 証 明 を お こ な う。
② η が 平 方 因 子 を 持 た な い と き
こ の と き 、1ワゴGは 自 然 数)を 素 数 と て 、 η は η=PLρ2̲,ρ 〆 ρ、≠ .ρノ〉 と素 因 数 分 解 で き る
と す る 。
ま ず 、 η=1っg(ρ ≠g)と か け る と き 、
/フー1瓢25〆
g‑1瓢25'"(∫ サ,'"は 奇 数)と す る 。
こ こ で 、1ワ,gは 対 称 的 な の で 、5書≦5"と し て も 一 般 性 を 失 わ な い た め そ う仮 定 し 、(i)(ii) の 二 つ に 場 合 分 け し て 考 え る 。
(i)5Ψ<3"の と き
底 α に 対 し 、 η がMillerRabin素 数 判 定 法 でYbs?と 返 し た と き
(1)ゴ …≡1(modη)ま た は
(2)0≦ ヨ7<5:〆 ご≡‑1(modη)
と な っ て い る 。 こ の と き 、 各 々 の ゐ ∈Z/ρgZを!で(Z/ρZ)×(Z/gZ)に 写 す と 、
次 が 成 立 す る 。
(1)ゴ …1(modρ)か っ ゴ …d(modg)ま た は
(2)0≦3γ 〈3:α2「'…‑1(modP)カ 〉つ αγ∫竃 一1(mod9)
09878307後 藤 大 和
(1)が 成 立 す る と き
ゴ 蕪1(mod1の を 満 た す α,の 個 数 は 系5よ り(ちp‑1)個 。
ゴ 議1(modg)を 満 た す α,の 個 数 は 系5よ り(ちg‑1)個 。
こ の 両 方 を 満 た す αρgの 個 数 は 補 題6よ り(ちp‑1)(ちg‑1)個 。
こ こ で 、1ワ ー1議25ズg‑1=25∫"か らtが 奇 数 よ り (ち」ρ一1)=(ち 〆)
(ち9‑1)=(ち ∫")で あ り
(ちの ≦ ∫Ψ(ち'")≦'"か ら 、 最 初 の 条 件 を 満 た す α四 の 個 数 は 高 々 〆'"個 と い う こ
と が 分 か る 。
(2)が 成 立 す る と き
0≦ ア<5で あ る よ う な ア を1つ 固 定 し た と き に 〆 ∫簗 一1(mod .ρ)か っ
α凶 …‑1(modg)と な る αρ,の 個 数 を 評 価 す る 。そ の た め 、以 下 の 補 題 を 利 用 す る。
補 題7(Z/pZ)× に お い て κ飽 …‑1(mod .ρ)の'の 解 の 個 数 は
ア≧5'の と き0で あ り 、 ア<5'の と き2ア(ち の 個 で あ る 。(証 明 は 後 ほ ど)
補 題6と 補 題7よ り 、 〆 』‑1(搬od .ρ)か つ αγ∫塞4(modg)で あ る よ う な
%の 個 数 は2℃,〆)2℃,'")で あ り、2℃,∫,)2℃,'")≦47〃 響 よ り 、4F〃"を 上 界 に も つ 。
さ て 、(1)を 満 た す 底 が 高 々 〃"個
(2)を 満 た す 底 が 高 々4学 ∫"個 と い う こ と が 分 か っ た 。
η 一1㍉ ρg>(ρ 一1)(g‑1)蕊2∫'÷5"〆'"か ら 、 可 能 な 底 α(0≦ α<η)の う ち 、 Miller・Rabin素 数 判 定 法 が 「艶s?と 返 す も の は
"WW鵠1;キ ー+碑 の ニ2‑(4∫‑11+
4‑1)
≦2‑1(243'一 十 一) 33
≦2弓(24‑十 一) 33
=一111十 一=一 一 1264
と な る 。
(ii)5』5サ'の と き
σ,の ≦ 〆 σ,'")≦1"の う ち 、 少 な く と も ど ち ら か の 不 等 号 を 「<」 に 置 き か え る こ と が で き る 。 な ぜ な ら
も し(ち ∫')漏ガ(ち ∫,サ)=〆'⇔ 州'か つ','け
⇔ 〆{@‑1)か っ 〆サ1(η一1)と な り
さ ら に η一1㍉ ρg‑1…g‑1(mod")(な ぜ な ら ρ=h23∫')で あ る か ら 刈(g‑1)を 得 る 。 こ れ よ り 〆1∫"と な り 、 同 様 に ∫"げ か ら ガ訂"
よ っ て ρ=gと な る が 、 こ れ は η が 平 方 因 子 を 持 た な い こ と に 矛 盾 す る 。 こ れ よ り
09878307後 藤 大 和
(ち 〆)<〆 ま た は(ち 〆 婁)<〆 Ψ を 得 る 。
(ち の く ズ と す る と 、'Ψ は 奇 数 よ り
〆 ≧3よ 〆
っ て(ち 〆)≦ 一 (ち 〆)3
よ っ て 、(i)の ケ ー ス で σ,〆)σ,'")≦ 〃 サ と 評 価 し た と こ ろ を
〆 〆「(ちの(ち〆響)≦
一 一 と 評 価 置 き か え ら れ る。3
よ っ て
1,,,45‑111
‑2‑5‑5(1+)≦ 一 ≦‑
34‑164
こ れ よ り 、 η=1ワgの と き に お い て は 証 明 さ れ た 。
(iii)3つ 以 上 の 異 な る 素 数 の 積 の と き η=ρ1p2̲監 久(ん ≧3)と す る 。
p、 擁=2η 、σ1は 奇 数)と 表 す と し 、3、の う ち 最 小 の も の を51と し て お く と η ヲgの と
き と ま っ た く 同 じ よ う に
野 ・一(1÷1)≦2庵(il三1+
21築1)
‑2丸2L2+1
2ん̲12ん4
≦2‑・.2L2+1 2た̲12た̲1
1‑21‑々+12(1‑2‑々)21‑々(2ん 一1)
2た̲12た̲12ん̲1
鷺21‑・ ≦1
4
と な り 、② に お い て も 示 さ れ た 。 目
以 上 に よ り、定 理Aが 証 明 され た 。
な お 、 こ こ で 先 ほ ど飛 ば し た 補 題7の 証 明 を 行 う。
補 題7の 証 明:
(Z/ρZ)× は 巡 回 群 で あ り 、 そ の 原 始 根 をgと す る 。gは(Z/1ワZ)xの 生 成 元 で あ り 互
g2筆1(mod1ワ)で あ る 。 こ の 既 約 剰 余 群 の 元 をgノ(0≦ ノ ≦ ρ 一1)で 表 す と 、 補 題0と フ 巴
エ ル マ ー の 小 定 理 よ り92攣 一1(mod、 ρ)で あ る か ら 、 箆
(gノ)凶 …‑1(modρ)⇔(gノ)豹 ≡g2(modρ)
⇔9吻 ≡9ブ 馬(modρ)
⇔2「 ガ ≡2∫Ll・ ∫管(mod2∫"亨)(な ぜ な ら2∫'〆=ρ 一1) こ こ で 、7≧8サ の と き 最 後 の 合 同 式 は
25翠『1('L2「}5「+1グ)ミ0(mod25「")と な る が 、1'は 奇 数 よ り アー5'+1=0と な り 、 ア=5L1を 得 る 。 そ こ で 、 ま ず7≧5「 の と き 、 合 同 式 は 解 を も た な い こ と が 分 か る 。
次 に7<5'の と き4雛(ち の と お く と 、 最 後 の 合 同 式 の 両 辺 と 法 を2ア4で 割 っ て
(エ)ブ竃2‑(二44)(m・d囑))を 得る・
,ガ,'量'
これ は(
4)と2惣7)が 互 い1こ素 で あ る こ とか ら・鞭1・2・1に よ り25‑「(万)を 法 と して 唯 一 の 解 を 持 つ ,〆,
。 そ し て 、2凹(一)を 法 とす る1つ の 剰 余 類 の 中 に は 、25∫ 禦を 法 と す る 剰 余4
類 が2「4セ ッ トあ る の で 、問 題 の 合 同 式 は 、25〆 を 法 と し て 、27踏27(ち 〆)個 の 解 を も っ 。
[コ
09878307後 藤 大 和
が7遡 θr魚 ゐ血 轍 翻 鰭 の 譲ぎク確 率 の 耀
1
さて、 定 理Aよ りMillerRabin素 数 判 定 法 の 誤 り確 率 は 一 以 下 だ と証 明 した 。 本 節 で は 、4
簡 単 な 前 処 理 を 行 うこ と で 、 あ る特 定 の 場 合 を 除 き そ の誤 り確 率 を低 減 で き る こ と を示 す 。
① ηが 平 方 因 子 を もつ 場 合
こ の と き誤 り確 率 は 一1 と評 価 され て い る が 、 も し1ワ≠3の と き 、 ρ は 奇 数 よ り P+1
11 ≦一 に お さえ られ る。
ρ+16
つ ま り、Miller・Rabin素 数 判 定 法 を 試 行 す る前 に 、3で 試 し割 りを し、 ηが9の 倍 数 で あ 1
る か ど うか
の確 か め をす る こ と で 、 こ の誤 り確 率 を 「一 以 下 」 とい う と こ ろ ま で 引 き 下 げ 6
る こ とが で き る。
(②(i)η が 相 異 な る二 素 数 の 積 か つ3蜜く5"の 場 合 に つ い て は 後 述)
②(n)η が 相 異 な る 二 素 数 の積 か つ5』 ゴ の 場 合 1
この と き は も と よ り 「
一 以 下 」 と評 価 が され て い る。
6
③(出)η が 異 な る3つ 以 上 の 積 の場 合
ん ≧4の と き 、21‑・ ≦1と お さ え られ る.
8
ん 蕊3の と き 、 ηrρ ビ .ρ2・.ρ3と し(,ρ1,.ρ2,p3は 素 数)
ρ 「1=25"i」 ρ2‑』2ε2'2ρ3‑b233'3と す る 。
ま た 、 定 理Aの 証 明 の 通 り 、5,の う ち 最 小 の も の を5正 と お く 。
31≧2の と き ・ 誤 擁 率 は ・ 定 理Aの 証 明 の 駿 の 不 等 式 よ り6以1 下 と な る・ これ よ り
以 下 で は31=1の と き に つ い て 考 え る 。
51=1,52,33≧2の と き
23̲123̲12一ト5・‑5・(1 +・)≦2一 レ4(1+
7)23̲1
<2‑・ ユ<1
166
で 抑 え ら れ る 。
52=1,33≧2の と き 、51コ1よ り
2331̲1)
瓢2‑2一 ∫3(1+1)2‑5「52‑53(1+
23̲1
‑2一 レ ・・ ≦2‑1‑・‑1<!
86
で 抑 え ら れ る 。 1
ま た ・5・ ≧2・5・ 瀦1の と き 桐 様 に 百 で お さ え ら れ る ・
よ っ て 問 題 は52=53雛1の と き に つ い て で あ る 。3玉 誕1よ り31=52=33羅1と な り 、
.ρ「1誕2'1,1っ2‑1窯2ら,,ρ3‑1=2∫3で あ る 。 こ れ は 本 章 の 頭 で 述 べ た 「特 定 の 場 合 」
で あ り 、 誤 り 確 率 を 低 減 す る た め の 障 壁 と な っ て い る 。
09878307後 藤 大 和
(i)η が 相 異 な る 二 素 数 の 積 か つ3'<8"の 場 合
証 明 で は 、(ち の ≦ 〆,(ち 〆「)≦〆「 と評 価 し た が 、(ち の く 〆 ま た は α,〆')<∫"の と き
〃9撃(1)(2)の場 合 共 に
、 〆∫"と 評 価 し た と こ ろ を す べ ℃ に お き か え ら れ る の で 、 こ の3
と き の 誤 り確 率 は
‑× 一 諜 一111 以 下 と い う こ と が 分 か る 。4312
よ っ て 以 下 で は σ,の=〆,(',∫")='"の 場 合 に つ い て 考 え る 。
ま た 、(ち の=〆,(ち ヂ)雛 ガ㌧〆≠ が の と き
{鐵一 り
η 諜 ρ9
・竃(23〆+1)(2ε 〆,+1) 瓢25'+3'穿'ソ日+25監',+25冒じ'智+1
⇔ η 一1雛2∫+5〃"+251,+25'"(=251)が 得 ら れ る 。
こ こ で 、(ち の=〆 よ り"1(2∫ 瑠+3"∫""+25"∫ 量+2ダ「'")と な る た め 〆12∫"'"⇔ 〆1〆,
同 様 に 、(ち'")=1"よ り 〆牧251ぜ 〃"+2∫ 軍1'+25"'")と な る た め'"げ が 得 ら れ る 。
よ っ て"=〆'と な る が こ れ は 〆≠ が と 矛 盾 す る た め 、 こ の 条 件 を 満 た す η は 存 在 し な
い 。
以 下 で は(ち の 吋,,(ち 〆')=∫",∫ 』'"の と き に つ い て 考 え る 。
さ ら に5,≧5の と き 、 こ の 誤 り確 率 は
2‑(24ε 一 十一 一)≦2擁1(2+杢) 3333
171 1024
で お さ え られ る の で 、1≦5'≦4の と き に っ い て 考 え る 。
(α)3』1の 場 合
8">2の と き 、 こ の 誤 り 確 率 は
,1,45‑14‑1)
==2『 レ∫理'(1+2 3‑5(1+) 4‑14‑1
瓢̲<̲11 2∫8
で お さ え ら れ る の で 、 以 下 で は5"=2の 場 合 に つ い て 考 え る 。
5』1,3亨 』2,(ち の 瓢 〆,(ち 〆撃)='㌧ ガ=が の と き
η=(25',+1)(2∫ ∫胃+1)
==(2〆+1)(4〆 ・+1)
=8ガ2+6ガ+1
η̲1=8〆2+6〆
==2(4〆2+3ガ)
こ こ で 、4∫ 亨2+3〆 は 奇 数 な の で 、8=1で あ る こ と が 分 か る 。
よ っ て こ の と き
09878307後 藤 大 和
腸 と なり ・{剛 一
っ ま り 、 こ の と き η は 、 η=(2"+1)(4'婁+1)の 形 を し て い る の で η に 対 し 」 Ψの2次 方 程
式8〆+一 一・一 解をも一 その一{灘}1こ 代入する
こ と で 、 η の 約 数 を 求 め る こ と が で き 、 こ の 条 件 の と き に 誤 る こ と は な く な る 。
よ っ て こ の と き 、MillerRabin素 数 判 定 法 を 試 行 す る ま え に 、 ∫曾の2次 方 程 式 8ガ2+6ガ+(レ η)=0
を 解 く こ と で 、 誤 っ た 答 え を 出 す こ と を ふ せ ぐ こ と が で き る 。
(β)8』2の 場 合
5">3の と き 、 こ の 誤 り確 率 は
凶 ・(45‑11+
4‑1)一 齊 『(1+碧) ほ 33 く
2ゴ晋や1一32
で お さ え ら れ る の で 、以 下 で は3"=3の 場 合 に つ い て 考 え る 。
こ の と き
η=(4ガ+1)(8ガ+1)
=32ガ2+12〆+1
と な る の で 、(α)と 同 様 な 議 論 で 、"の2次 方 程 式 32ガ ズ亨+12ズ→一(レ η)=0
を 解 く こ と で 、 誤 っ た 答 え を ふ せ ぐ こ と が で き る 。
(γ)3』3の 場 合
3">4の と き 、 こ の 誤 り確 率 は
酬(45‑11+)ヂ(1+雄 一1)
4‑14‑1
コ 1111 〈̲
2♂ 率2‑128
で お さ え られ る の で 、5"=4の 場 合 に つ い て 考 え る と η=(8ガ+1)(16〆+1)
ニ128ズ2+24ガ+1
と な る の で 、(α 〉と 同 様 な 議 論 で 、 ガ の2次 方 程 式 128〆2+24ズ+(1一 η)=0
を 解 く こ と で 、 誤 っ た 答 え を ふ せ ぐ こ と が で き る 。
(δ)8』4の 場 合
3">5の と き 、 こ の 誤 り確 率 は
2‑(4̀‑11+)‑2‑(1+4簡)
444‑1 諏 4343 く̲̲̲
23鳩 一512
で お さ え ら れ る の で 、3"凱5の 場 合 に つ い て 考 え る と η 瓢(16〆+1)(32〆+1)
=512〆2・+48〆+1
と な る の で 、(α)と 同 様 な 議 論 で 、 〆の2次 方 程 式 512ガ2+48∫ 婁+〈1一η)=0
を 解 く こ と で 、 誤 っ た 答 え を ふ せ ぐ こ と が で き る 。
こ れ よ り②(i)の 場 合 、 前 処 理 と し て4つ の2次 方 程 式 を 解 く こ と で 、 誤 り確 率 を 171
「 以 下
」 ま で 下 げ る こ と が で き る 。1024
09878307後 藤 大 和
こ れ よ り 、
・9で 試 し割 り を す る
・2次 方 程 式8"2+6〆+(1一 η)誠0の2解 が 整 数 で あ る か ど う か の 判 定
・2次 方 程 式32〆2+12∫'+(1一 η)=0の2解 が 整 数 で あ る か ど う か の 判 定
・2次 方 程 式128〆2+24ガ+(1一 η)瓢0の2解 が 整 数 で あ る か ど う か の 判 定
・2次 方 程 式512〆2+48ガ+(レ η)=0の2解 が 整 数 で あ る か ど う か の 判 定
と い っ た 前 処 理 を 行 う こ と で 、 「 η が 異 な る3つ の 素 数 の 積 で 、 η=(21釜+1)(2∫2÷1)(2∫3÷1)('1,'2,'3は 異 な る 奇 数)」 と い う 特 定 の 場 合 を 除 き 、誤 り確 率
171
を 「 以 下
」 に お さ え る こ と が 出 来 る 。 な お 、2次 方 程 式 の 計 算 量 は2次 方 程 式 の 解 の1024
公 式 を 計 算 す る 計 算 量 と 同 一 視 で き る 。 つ ま り そ れ は 、 明 ら か に 累 乗 数 の 判 定 の 計 算 量 よ り 小 さ く な る た め 、そ の 計 算 量 は[1]のLemma2.3.6よ り0((logη)210910gη)程 度 で あ り 、
ビ ッ ト演 算 の 計 算 量 と し て も0((logη)3)で 抑 え られ る 。 ま た 、"Newtoniteration"を 利 用
す れ ば 、 ビ ッ ト演 算 は0((10gη)2)で 抑 え ら れ る 。 そ れ に つ い て は[11を 参 照 し て い た だ き
た い 。
ま た(α)、(β)、(γ)、(δ)の 二 次 方 程 式 の 自 然 数 解 の 候 補 は そ れ ぞ れ 一3+廟
,‑3+痂,‑3+廟,‑3+〜 偏 な の で 、 〉1扁 を求 め る計
3264168
算 と簡 単 な 計 算 だ け で4つ の判 定 は で き る 。 よ っ て4つ の 判 定 を合 わ せ て もMiller・Rabin 素 数 判 定 法1回 分 の 計 算 量 を超 え な い 。
が8今 凌 の誤題
今 後 の 課 題 は 、 「η が 異 な る3つ の 素 数 の 積 で 、 η 《2ら+1)(2らd)(2∫3+1)(∫p'2,∫3は
異 な る 奇 数)」 と い う 特 定 の 場 合 の 誤 り確 率 の 低 減 で あ る 。(そ の よ う な 場 合 は 確 か に 存 在 す る 。 例 と し て 、 η=231の と き η=3×7×11《2・h1)(2・3+1)(2・5d)が 挙 げ ら れ る 。)
も し こ の 特 定 の 場 合 の 誤 り確 率 を 低 減 で き れ ば 、 前 述 の 前 処 理 を 行 う こ と で 、 誤 り 確 率 を 171 以 下 に 下 げ る こ と が で き る
。1024
も し そ れ が 可 能 で あ れ ば 、MillerRabin素 数 判 定 法 と前 処 理 の 計 算 量 は 共 に0((logη)2)
で 抑 え る こ と が で き る た め 、 前 処 理 な し で 従 来 通 りMiller‑Rabin素 数 判 定 法 を す る 反 復 回 数 を1回 と す る と 、Miller‑Rabin素 数 判 定 法 を1回 繰 り返 す 時 間 計 算 量 と 、 今 回 の 前 処 理 を 行 っ た 後 に1‑1回 繰 り 返 す 時 間 計 算 量 は 同 等 で あ る 。 そ こ で 誤 り 確 率 を 比 べ る と 、
(1)1>(171)1‑1と な る の は1≧6で あ る た め 、 も しMillerRabin素 数 判 定 法 を6回 以10244
上 行 う の で あ れ ば 、 前 述 の 前 処 理 を 行 っ た 後 にMillerRabin素 数 判 定 法 を 行 っ た 方 が 効 率 的 だ と い う こ と が わ か る 。
09878307後 藤 大 和
謝辞
本 論 文 の 作 成 に あ た り、 終 始 適 切 な 助 言 、 指 導 を し て く だ さ っ た 鈴 木 登 志 雄 先 生 に 感 謝 い た しま す 。 同 研 究 室 の 中村 亮 太 氏 を は じめ と した メ ンバ ー に も 、 精 神 的 に と て も 支 え ら れ ま した 。 ま た 、 学 部 時 代 に お 世 話 に な りま した 黒 田 茂 先 生 に もお 世 話 に な りま した こ と を この 場 を借 りて お 礼 申 し上 げ ま す 。
参考文献
田MartinDietzfblbinger:
Primaliもytesもinginpolynomia1もime,fromfandomizedalgoriもhmstò̀PRIMESisi勲
P",Springe鴎Berlin,2004
[21深 川 久:
2001年 度 大 阪 市 立 大 学 イ ン タ ー ネ ッ ト講 座 「物 性 物 理 学 に お け る 最 近 の 話 題 」 レ ポ ー ト
「Miller・Rabinに よ る 素 数 の 確 率 的 判 定 法 」
http://www.a‑phys.eng.osaka℃u.acjp/suri・g/millerrabin.pdf
[3】GaryL.Miller:
Riemann'shypothesisandtestsfbrpri斑ality,」 ∂砿 η∂10!α 〜鵯 ρ薦 θf∂ 刀 ゴ
称3診 θ122甜b刀oθ513(1976),no.3,PP.300‑317.
[41Michae10.Rabin:
Probabilisticalgorithmfbrtestingprimality,♂ ∂砿 η∂10!ハ 加 加 わθ1・7ゐ θoη ・12
(1980),no.1,PP.128‑138.
[5}中村 憲(中 村 佳 正 ・竪 海 正 俊 編 集)
「開 か れ た 数 学 数 論 ア ル ゴ リズ ム 」,朝 倉 書 店,2009
