• トノイテ、オ、、ソケヤ、マ、ウ、ホソァ、ヌ、ケ。」
  • コス、オ、、ソケヤ、マ、ウ、ホソァ、ヌ、ケ。」
  • Miller-Rabin・ニ・ケ・ネ 、リケヤ、ッ。」

*フワシ。 [#d81c480d]

#contents


*Miller、ホトヘ [#c4734516]

。。Miller、ホトヘ、ネクニ、ミ、、シ。、ホトヘ、ャツクコ゚、ケ、。」

#divid(s,thorem)
[トヘ]p、チヌソ、ネ、キ。「r、マp-1={2^s}。゚r、ヒ、ソ、ケエソ、ネ、ケ、。ハエソ、ャスミ、、゙、ヌ2、ヌウ荀テ、ニ、、、。ヒ。」、ウ、ホ、ネ、ュ。「1。藺。蚪-1、ハ、ヌ、ーユ、ホターソa、ヒツミ、キ、ニ。「シ。、ャタョ、ホゥ、ト。」。ヨ&mimetex("a^r \equiv 1 \pmod{p}");。ラ、「、、、、マ。ヨ&mimetex("a^{{2^j} \times r} \equiv 1 \pmod{p}");。ラ、ヒ、ソ、ケ、隍ヲ、ハ&mimetex("j \in \{0 , \cdots, s-1\}");、ャツクコ゚、ケ、。」「ォ(*)
#divid(e,thorem)

。。、ウ、ウ、ヌ、マMiller、ホトヘ、ホセレフタ、マ、サ、コ、ヒ。「イソ、ーユフ」、キ、ニ、、、、ホ、ォ。「、ス、キ、ニ、ハ、シタョ、ホゥ、ト、ホ、ォ、ネ、、、ヲナタ、ネトセエムナェ、ヒスメ、ル、。」

。。p、ャチヌソ、ホ、ネ、ュ。「。ヨxSUP{2};「1 (mod p)。ラ「ヘ。ヨx「-1 or 1。ラ、ャタョ、ホゥ、ト。」p、ャケ鄲ョソ、ホ、ネ、ュ、マ、ウ、、ャタョ、ホゥ、ト、ネ、マクツ、鬢ハ、、。」、隍テ、ニ。「チヌソ、ヒ。、ネ、ケ、タ、ウヲ、ヌ2セ隍キ、ニ1、タ、テ、ソ、鬘「クオ、ホソ、マ1 or -1、ヌ、「、。」、ト、゙、遙「aSUP{r};、2セ隍コ、ト、キ、ニ、、、ュ。「1、ヒス鬢皃ニ、ハ、テ、ソ、ネ、ュ。「、ス、ホトセチー、ホソ、マ-1、ヌ、ハ、ア、、ミ、ハ、鬢ハ、、、ネ、、、ヲ、ウ、ネ、ヌ、「、。」

#img(http://security2600.sakura.ne.jp/main2/image3/miller1.jpg)
#img(,clear)

#divid(s,proof)
[ホャセレ]s=2、ホ、ネ、ュ、セレフタ、ケ、。」ツィ、チ。「&mimetex("p-1=2^{2} \times r");、ヌケヘ、ィ、。」、ソ、タ、キ。「r、マエソ、ネイセト熙ケ、。」

。。、ウ、ホ、ネ、ュ。「・ユ・ァ・・゙。シ、ホセョトヘ、隍遙「1。藺。蚪-1、ハ、ヌ、ーユ、ホa、ヒツミ、キ、ニ。「p、ヒ。、ネ、キ、ニシ。、ャタョ、ホゥ、ト。」

&mimetex("1 \equiv a^{p-1} \pmod{p}");~
&mimetex("0 \equiv a^{p-1} -1 \pmod{p}");~
&mimetex("0 \equiv a^{2^2 r} -1 \pmod{p}");。。。ハ「鑵-1=2SUP{2};。゚r。ヒ~
&mimetex("0 \equiv (a^{2r})^2 -1 \pmod{p}");。。。ハ「&mimetex("a^{2^2 r}=a^{4r}=a^{2r}a^{2r}=(a^{2r})^2");。ヒ~
&mimetex("0 \equiv (a^{2r} +1)(a^{2r} -1) \pmod{p}");~
&mimetex("0 \equiv (a^{2r} +1)(a^r +1)(a^r -1) \pmod{p}");~
。&mimetex("a^r \equiv 1, a^4 \equiv -1, a^{2r} \equiv -1 \pmod{p}");。。「「
#divid(e,proof)



*Miller-Rabin・ニ・ケ・ネ [#ze14c19b]

。。Millar、ホトヘ、ヘヘム、キ、ソチヌソ・ニ・ケ・ネ、ヌ、「、Miller-Rabin・ニ・ケ・ネ。ハMR・ニ・ケ・ネ。ヒ、セメイ、ケ、。」、ウ、ホMiller-Rabin・ニ・ケ・ネ、ホニスミホマ、ネ・「・・エ・・コ・潼R、マシ。、ホ、隍ヲ、ヒ、ハ、。」

-ニホマ
--n。ハn。3、ホエソ。ヒ
-スミホマ
--"prime" or "composite"

#code(lisp){{
s,r、マn-1=2^{s}。゚r、ヒ、ソ、ケ、隍ヲ、ヒ・サ・テ・ネ、オ、、。ハ、ソ、タ、キ。「r、マエソ。ヒ
i=0
i「ォi+1
a。ァ{1,2,。ト,n-1}、ォ、鬣鬣・タ・爨ヒチェツ
y[0]「ォa^r mod n
if(y[0]==1 || y[0] == n-1)
    output "prime"
else
    for(j=1;j。蚶-1;j=j+1){
        y[j]「ォy[j-1]^2 mod n
        if(y[j]==n-1)
            output "prime"
    }
output "composite"
}}

。。MR、ホ・「・・エ・・コ・爨ホテ豼ネ、ヒ、ト、、、ニイタ筅ケ、。」

-6ケヤフワ、ホifハク、ホセキシー、ホチーネセ、マMiller、ホトヘ、ホ。ヨa^r「1。ラ、ヒツミア、キ。「ク衒セ、マj=0
、ホ、ネ、ュ、ホ。ヨ&mimetex("a^{{2^j} \times r} \equiv 1");。ラ、ヒツミア、ケ、。」y[0]==n-1、マmod n、ヌy[0]=-1、ヌ、「、、ウ
、ネ、ヒテーユ。」
-11ケヤフワ、ホifハク、ホセキシー、マj。0、ホ、ネ、ュ、ホ&mimetex("a^{{2^j} \times r} \equiv 1");、ヒツミア、ケ、。」


*Miller-Rabin・ニ・ケ・ネ、ホフ萃ナタ [#n415cce9]

。。、ウ、ホMiller-Rabin・ニ・ケ・ネ、ホフ萃熙マシ。、ホ2ナタ、ヌ、「、。」

-ニホマn、ャチヌソ、ハ、ホ、ヒ。「"composite"、ネスミホマ、オ、、、ウ、ネ「ェ[1]
-ニホマn、ャケ鄲ョソ、ハ、ホ、ヒ。「"prime"、ネスミホマ、オ、、、ウ、ネ「ェ[2]

[1]n、ャチヌソ、ホセケ

。。Miller、ホトヘ、隍遙「MR、マ"composite"、スミホマ、キ、ハ、、。」、ハ、シ、ハ、鬢ミ。「、、、ュ、ハ、1、ヒ、ハ、、ォ。「ナモテ讀ヌ-1、ャスミ、ニ、ッ、、ォ、ホ、ノ、チ、鬢ォ、ヌ、「、。」、隍テ、ニ。「ノャ、コ。ヨoutput "prime"。ラ、ホフソホ皃ヒ、メ、テ、ォ、ォ、。」

[2]n、ャカソ、ホセケ

。。Miller-Rabin・ニ・ケ・ネ、ヌ。「"prime"、スミホマ、ケ、ウホホィ、マ(1/4)^t、ヒ、ハ、。」、ソ、タ、キ。「t、マキォ、ハヨ、キイソ、ネ、ケ、。」

。。ーハセ螟ヌMiller-Rabin・ニ・ケ・ネ、ホサナヘヘ、ヒ、ト、、、ニ、ホイタ筅マスェ、ィ、ソ。」


*MR-witness、ネMR-liar [#b16476d3]

。。Miller-Rabin・ニ・ケ・ネ、ヌ、マ。「。ヨn、ャケ鄲ョソ。ラ、ォ、ト。ヨMR(n)="reject"。ラ、ャタョ、ホゥ、ト、ネ、ュ、ホウホホィ、ャ1/2ーハセ螟ヌ、「、、ウ、ネ、エツヤ、キ、ソ、、。」、ウ、ウ、ヌシ酘・、フタウホ、ヒ、ケ、、ソ、皃ヒ。「シ。、ホ2、ト、ホクタヘユ、トオチ、ケ、。」

#divid(s,thorem)
-。ヨ&mimetex("a^r \not{\equiv} 1 \pmod{n}");。ラ、ォ、ト。ヨヌ、ーユ、ホj「コ{0,。ト,k-1}、ヒ、ェ、、、ニ。「&mimetex("a^{{2^s} \times r} \not{\equiv} -1 \pmod{n}");。ラ、ャタョ、ホゥ、ト、ネ、ュ。「a、''n、ヒツミ、ケ、MR-witness''、ネクニ、ヨ。」
-。ヨn。ァケ鄲ョソ。ラ、ォ、ト。ヨa。ァn、ホMR-witness、ヌ、ハ、、。ラ、ャタョ、ホゥ、ト、ネ、ュ。「a、''n、ヒツミ、ケ、MR-liar''、ネクニ、ヨ。」
#divid(e,thorem)

。。Fermat-wintess/liar、ホ、ネ、ュ、ホオトマタ、ネニアヘヘ、ヒ。「。ヨn、ヒツミ、ケ、MR-witness。ラ、ネ。ヨn、ヒツミ、ケ、MR-liar。ラ、箴。、ホエリキクシー、ャタョ、ホゥ、ト。」

#divid(s,thorem)
。ヨn、ヒツミ、ケ、MR-witness。ラ。ワ。ヨn、ヒツミ、ケ、MR-liar。ラ。疣-1
#divid(e,thorem)

#divid(s,notice)
ホ1。ァーユフ」、ネサネ、、ハ、ヒエキ、、、ウ、ネ、フワナェ、ネ、キ、ニ。「Miller-Rabin・ニ・ケ・ネ、ヘム、、、、ウ、ネ、ヒ、隍テ、ニ。「n=105、ャチヌソ、ォ、ノ、ヲ、ォ、ネスト熙キ、ニ、゚、。ハn=105=3。ヲ5。ヲ7、ャタョ、ホゥ、ト、ホ、ヌヒワナ、マチヌソ、ヌ、マ、ハ、、、ホ、タ、ャ。「、ス、、マオ、、ヒ、サ、コ・「・・エ・・コ・倏ェ、ヒ、ノ、ヲニー、ッ、ォトエ、ル、。ヒ。」

。。&mimetex("n-1=104={2^{3}} \times 13");、ャタョ、ホゥ、ト、ォ、鬘「、゙、コs=3,r=13、ネ・サ・テ・ネ、オ、、。」シ。、ヒ。「・鬣・タ・爨ヒチェ、、タターソテヘ、ャa=8、ヌ、「、テ、ソ、ネ、ケ、。」、ケ、、ネ。「y[0]=8SUP{13};「8 (mod 105)、ヒ、ハ、。」、ウ、ホy[0]、マmod 105、ホタ、ウヲ、ヌ1 or 104(=n-1)、ヌ、マ、ハ、、、ホ、ヌ。「elseーハイシ、ホforハク、ャシツケヤ、オ、、。」

-y[1]「ォy[0]^2「8SUP{2};「64 (mod 105)
-y[2]「ォy[1]^2「64SUP{2};「1 (mod 105)
-y[1]「ォy[0]SUP{2};「8SUP{2};「64 (mod 105)
-y[2]「ォy[1]SUP{2};「64SUP{2};「1 (mod 105)

。。ク螟マ。「、コ、テ、ネy[j]、マ1 (mod 105)、ヒ、ハ、。」、ス、ホ、ソ、癸ヨoutput "prime"。ラ、ャシツケヤ、オ、、コ、ヒ。「コヌスェナェ、ヒ。ヨoutput "composite"。ラ、ャシツケヤ、オ、、。」、隍テ、ニ。「n=105、マチヌソ、ヌ、マ、ハ、、。」。。。
#divid(e,notice)

#divid(s,notice)
ホ2。ァシ。、ヒ・ォ。シ・゙・、・ア・ソ、ャニホマ、オ、、ニ、筍「Miller-Rabin・ニ・ケ・ネ、ャ、ヲ、゙、ッニーコ、ケ、、ウ、ネ、ウホヌァ、ケ、。」、ウ、ウ、ヌ、マホ网ネ、キ、ニコヌセョ、ホ・ォ。シ・゙・、・ア・ソ、ヌ、「、n=561=3。゚11。゚17、ケヘ、ィ、。」タ隍ロ、ノ、ホ・ユ・ァ・・゙。シ・ニ・ケ・ネ、ヌ、マ、ウ、ホ、ネ、ュ、ヒフ萃熙ャ、「、テ、ソ。」Miller-Rabin・ニ・ケ・ネ、ヌ、マ、ウ、ホフ萃熙ャイキ隍オ、、ニ、、、、ウ、ネ、ウホヌァ、キ、ニ、ェ、ォ、ハ、ア、、ミ、ハ、鬢ハ、、。」

。。n-1=560=2SUP{4};。゚35、ャタョ、ホゥ、ト、ホ、ヌ。「s=4,r=35、ネ・サ・テ・ネ、オ、、。」

-a=2
-aSUP{35};=2SUP{35}; (mod 561)「263
-aSUP{70};=166
-aSUP{140};=67。。「ォaSUP{280};=1、ネ、ハ、トセチー、タ、ャ。「mod n、ホタ、ウヲ、ヌ、マ-1、ヌ、マ、ハ、、
-aSUP{280};=1
-aSUP{560};=1

。。a=2、ホ、ネ、ュ。「aSUP{r};、ホ2セ隍コ、ト、キ、ニ、、、ッ、ネ。「aSUP{n-1};、゙、ヌ、ヒヒ。n、ホタ、ウヲ、ヌ-1、マーナル、簀ミセ、キ、ハ、、。」、ト、゙、遙「a=2、マMR-witness、ヒ、ハ、。ハn=561、ヒ、マMR-witness、ャセッ、ハ、ッ、ネ、筅メ、ネ、トツクコ゚、ケ、、ウ、ネ、ャウホヌァ、ヌ、ュ、ソ。ヒ。」

。。ニアヘヘ、ヒ。「a=3,。ト,560、゙、ヌトエ、ル、ニ、、、ッ、ネ。「ホ网ィ、ミa=5、ホ、ネ、ュ、マ。ヨn、ヒツミ、ケ、MR-witness。ラ、ヒ、ハ、、キ。「a=50、ホ、ネ、ュ、マ。ヨn、ヒツミ、ケ、MR-liar。ラ、ヒ、ハ、。」、隍テ、ニ。「n=561、ホ、ネ、ュ、ヒMR-witness、ネMR-liar、ャ、「、、ウ、ネ、ャ、、ォ、テ、ソ。」シツコン、ヒ、マ。「。ハMR-witness、ホソ。ヒ。茖ハMR-liar、ホソ。ヒ、ヌ、「、、ウ、ネ、ャ、、ォ、テ、ニ、、、。」、隍テ、ニ。「。ヨMR(561)="reject"。ラ、ャタョ、ホゥ、トウホホィ、マ1/2ーハセ螟ヒ、ハ、。」ーハセ螟ヒ、隍遙「・ォ。シ・゙・、・ア・ソ、ホーシ、ヌ、「、n=561、ヌ、「、テ、ニ、筍「Miller-Rabin・ニ・ケ・ネ、マチヌソ・ニ・ケ・ネ、ネ、キ、ニ、ヲ、゙、ッニッ、ッ、ウ、ネ、ャウホヌァ、ヌ、ュ、ソ。」
#divid(e,notice)

。。コヌク螟ヒオ、、ヒ、ハ、、ホ、マ。「、ノ、ホ、隍ヲ、ハターソn、チェ、、タ、ネ、キ、ニ、筍「。ヨn、ャケ鄲ョソ。ラ、ォ、ト。ヨMR(n)="reject"。ラ、ャタョ、ホゥ、トウホホィ、ャ1/2ーハセ螟ヌ、「、、ォ、ノ、ヲ、ォ、ネ、、、ヲナタ、ヌ、「、。」、ウ、ホオソフ荀ヒエリ、キ、ニ、マケホトナェ、ハーユフ」、ヌイキ隍オ、、ニ、、、。」、ス、、トヘ、ネ、キ、ニ、゙、ネ、皃、ネシ。、ホ、隍ヲ、ヒ、ハ、。」

#divid(s,thorem)
[トヘ]Miller-Rabin・ニ・ケ・ネ、マ。「Primes「コcoRP、セレクタ、ケ、。」ツィ、チ。「Pr[MR(ケ鄲ョソ)=accept]。1/2、ャタョ、ホゥ、ト。ハ=1/2、ヒ、マ、ハ、鬢ハ、、。ヒ。」
#divid(e,thorem)

#divid(s,thorem)
[トヘ]。ヨn、ャケ鄲ョソ。ラ、ォ、ト。ヨMR(n)="reject"。ラ、ャタョ、ホゥ、トウホホィ、ャ1/2ーハセ螟ヌ、「、。」クタ、、エケ、ィ、、ネ。「。ヨn、ャケ鄲ョソ。ラ、ォ、ト。ヨMR(n)="accept"。ラ、ャタョ、ホゥ、トウホホィ、マ1/2、隍セョ、オ、、。」
#divid(e,thorem)

#divid(s,proof)
[セレフタ]n、ケ鄲ョソ、ネ、ケ、。」。ヨn、ヒツミ、ケ、MR-liar。ラ、ヌ、「、、隍ヲ、ハa、ホクトソ、ャ。「チエツホ、ホネセハャーハイシ、ヌ、「、、ウ、ネ、シィ、ケ、ウ、ネ、ャ、ヌ、ュ、、ミ、隍、。」、ウ、ウ、ヌ。「チエツホ、ネ、マ&mimetex("\mathbb{Z}_n^*");、ハ、ホ、ヌ。「、ス、ホクトソ、マヲユ(n)、ヌ、「、。」

。。、゙、コ。「n、ャ・ォ。シ・゙・、・ア・ソ、ォネン、ォ、ヒ、隍テ、ニセケ醋ャ、ア、キ、ニケヘ、ィ、。」

[1]n、ャ・ォ。シ・゙・、・ア・ソ、ヌ、ハ、、、ネ、ュ

。。n、ャ・ォ。シ・゙・、・ア・ソ、ヌ、ハ、ア、、ミ・ユ・ァ・・゙。シ・ニ・ケ・ネ、ヌ、「、テ、ニ、篶萃熙ハ、ォ、テ、ソ。」Miller-Rabin・ニ・ケ・ネ、マ・ユ・ァ・・゙。シ・ニ・ケ・ネ、ホイホノネヌ、ハ、ホ、ヌ。「・「・・エ・・コ・倏ェ、ヒフ萃熙ハ、ッ。「シ。、ホエリキク。ハスクケ遉ホハエ゙エリキク。ヒ、ャタョ、ホゥ、ト。」

。ハ。ヨn、ヒツミ、ケ、MR-liar。ラ、ヌ、「、、隍ヲ、ハa、ホスク、゙、遙ヒ~
「シ。ハ。ヨn、ヒツミ、ケ、Fermat-liar。ラ、ヌ、「、、隍ヲ、ハa、ホスク、゙、遙ヒ~
。&mimetex("\mathbb{Z}_n^*");

。。、隍テ、ニ。「。ヨn、ヒツミ、ケ、MR-liar。ラ、ヌ、「、、隍ヲ、ハa、ホスク、゙、熙ホヘラチヌ、ホクトソ、マ1/2。゚ヲユ(n)ーハイシ、ヌ、「、。」

[2]n、ャ・ォ。シ・゙・、・ア・ソ、ヌ、「、、ネ、ュ

。。フ萃熙マ、ウ、チ、鬢ホセケ遉ヌ、「、。」。ヨn、ヒツミ、ケ、MR-liar。ラ。ハ&mimetex("a^{{2^s} \times r} \equiv -1 \pmod{n}");。ヒ、ヌ、「、、隍ヲ、ハa、ホスク、゙、熙ホ、゙、゙、ヌ、マケヘ、ィ、ヒ、ッ、、、ホ、ヌ。「、ウ、、ハウ遉ケ、、隍ヲ、ハスクケ遉ソキ、ソ、ヒケヘ、ィ。「、ス、ホスクケ遉ヌ、「、テ、ニ、&mimetex("\mathbb{Z}_n^*");、ホソソノハャキイ、ヌ、「、、ウ、ネ、シィ、ケ、ウ、ネ、ャ、ヌ、ュ、、ミ、隍、。」&mimetex("a^{{2^s} \times r} \equiv -1 \pmod{n}");、ヒ、ソ、ケ、隍ヲ、ハa、ホスク、゙、熙A、ネ、ケ、。」

。。、゙、ソ。「t、&mimetex("a^{{2^s} \times r} \equiv 1 \pmod{n}");、ヒ、ソ、ケ、隍ヲ、ハa、ャツクコ゚、ケ、、ネ、ュ、ヒ、ェ、ア、。「s、ホコヌツ酖ヘ、ネ、ケ、。」、ウ、ホt、サネ、テ、ニ。「ソキ、キ、、スクケ遉。「&mimetex("a^{{2^t} \times r} \equiv \pm 1 \pmod{n}");、ヒ、ソ、ケ、隍ヲ、ハa、ホスク、゙、熙ネトオチ、ヌ、ュ、。」、ウ、ホスクケ遉B、ネ、ケ、。」A「シB、ヌ、「、、ウ、ネ、ヒテーユ。」フワナェ、マB。&mimetex("\mathbb{Z}_n^*");、シィ、ケ、ウ、ネ、ヌ、「、。」ソソノハャキイ、ヌ、「、、ウ、ネ、シィ、ケ、ヒ、マ。「ノハャキイ、ヌ、「、、ウ、ネ、ネソソ、ホノハャキイ、ヌ、「、、ウ、ネ、ホ2、ト、シィ、サ、ミ、隍、。」、ウ、ホ2、ト、ス遉トノ、テ、ニセレフタ、キ、ニ、、、ッ。」

(i)B、ャ&mimetex("\mathbb{Z}_n^*");、ホノハャキイ、ヌ、「、、ウ、ネ、シィ、ケ

。。ノハャキイ、ヌ、「、、ウ、ネ、シィ、ケ、ソ、皃ヒ、マオユクオ、ホツクコ゚、ネア鮟サ、ャハト、ク、ニ、、、、ウ、ネ、、、、ィ、、ミ、隍、。」

-B、マオユクオ、ャツクコ゚、ケ、。」、ハ、シ、ハ、鬢ミ。「&mimetex("b^{{2^t} \times r} \equiv \pm 1 \pmod{n}");、ヒ、ソ、ケテヘ、ヌ、「、b、マ。「2セ隍ケ、、ミノャ、コ1、ヒーテラ、ケ、。」、ト、゙、遙「オユクオ、マノャ、コツクコ゚、ケ、、ォ、鬢ヌ、「、。ハシォハャシォソネ。ヒ。」
-c,d「コB、ハ、鬢ミ。「cd「コB、ャタョ、ホゥ、ト。」、ハ、シ、ハ、鬢ミ。「c,d「コB、隍遙「c、マ&mimetex("c^{{2^t} \time r} \equiv \pm 1 \pmod{n}");、ヒ、ソ、ケテヘ。「d、マ&mimetex("d^{{2^t} \times r} \equiv \pm 1 \pmod{n}");、ヒ、ソ、ケテヘ、ヌ、「、。」、隍テ、ニ。「&mimetex("cd^{{2^t} \times r} \equiv \pm 1 \pmod{n}");、ャタョ、ホゥ、ト、ホ、ヌ。「cd「コB、ャタョ、ホゥ、ト。」ークタ、ヌクタ、ィ、ミ。「。゙1、、ウン、ア、、ミ。「キカノ。゙1、ヒ、ハ、、ォ、鬢ヌ、「、。」

。。、隍テ、ニ。「B。&mimetex("\mathbb{Z}_n^*");、ャタョ、ホゥ、ト。」

(i)B、ャ&mimetex("\mathbb{Z}_n^*");、ホソソノハャキイ、ヌ、「、、ウ、ネ、シィ、ケ

。。、ウ、、シィ、サ、ミ。「&mimetex("\mathbb{Z}_n^*");、ォ、顳、ス、、、ソスクケ遉ャカスクケ遉ヌ、「、、ミ、隍、。」、ス、ウ、ヌヌリヘヒ。、ヘム、、、。」、ス、ウ、ヌ。「&mimetex("\mathbb{Z}_n^*");、ォ、顳、ス、、、ソスクケ遉ャカスクケ遉ヌ、ハ、、、ネイセト熙ケ、。」

。。・ォ。シ・゙・、・ア・ソ、マ3、トーハセ螟ホチヌーサメ、サ、ト、ホ、ヌ。「セッ、ハ、ッ、ネ、穗=nSUB{1};。゚nSUB{2};、ネオュスメ、オ、、。」、ソ、タ、キ。「nSUB{1};,nSUB{2};、ネ、箒ソ、ォ、トGCD(nSUB{1};,nSUB{2};)=1、ヌ、「、。」

。。、゙、ソ。「{{2SUP{t};}。゚r}セ隍ケ、、ネmod n、ホタ、ウヲ、ヌ-1、ヒーテラ、ケ、、隍ヲ、ハテヘ、ャA、ホヘラチヌ、ヒツクコ゚、ケ、。ハ、ウ、、マA、ホトオチ、ォ、鯲タ、鬢ォ。ヒ。」、ウ、ホテヘ、e、ネ、ケ、。」、ト、゙、遙「e^{{2^t}。゚r}「-1 (mod n)、ャタョ、ホゥ、ト。」

。。、ウ、ウ、ヌ。「a:=e (mod n_1)、ネトオチ、ケ、。」、ケ、、ネ。「テ貉ソヘ、ホセヘセトヘ、隍遙「シ。、ホマ「ホゥケ酥アシー、ヒ、ソ、ケ、隍ヲ、ハa「コZ、ャツクコ゚、ケ、。」

-a「疇 (mod nSUB{1};)
-a「1 (mod nSUB{2};)
-、ソ、タ、キ。「GCD(nSUB{1};,nSUB{2};)=1

。。、゙、コ。「&mimetex("a^{{2^t} \times r} \equiv e^{{2^t} \times r} \pmod{n_1} \equiv -1 \pmod{n_1}");。ハ、ウ、ホキイフ、ュ。、ネ、ケ、。ヒ、ャタョ、ホゥ、ト。」、゙、ソ。「。ヨ&mimetex("a^{{2^t} \times r} \equiv 1 \pmod{n_1}");。ラ。ハ、ウ、ホキイフ、ュ「、ネ、ケ、。ヒ、簑ョ、ホゥ、ト。」

。。、隍テ、ニ。「&mimetex("a^{{2^t} \times r} \equiv 1");、ネケヘ、ィ、、ネュ「、ヒネソ、キ。「&mimetex("a^{{2^t} \times r} \equiv -1");、ネケヘ、ィ、、ネュ。、ヒネソ、ケ、、ホ、ヌ。「&mimetex("a^{{2^t} \times r} \not{\equiv} \pm 1 \pmod{n}");、ヒ、ハ、。ハmod、ャn、ヒ、ハ、テ、ニ、、、、ウ、ネ、ヒテーユ。ヒ。」、隍テ、ニ。「&mimetex("a( \in \mathbb{Z}_n^*)");、マB、ヒツー、キ、ハ、、。」

。。、ス、筅ス、磚「シB、ホ、隍ヲ、ヒタ゚ト熙キ、ソ、マ、コ、ハ、ホ、ヒ。「a、マA、ヒエ゙、゙、。「B、ヒエ゙、゙、、ハ、、、ネ、、、ヲ、ウ、ネ、マ、「、熙ィ、ハ、、。」、隍テ、ニ。「フキス筅ャタク、ク、ソ。」。。「「
#divid(e,proof)

。。、ウ、、ヌMiller-Rabin・ニ・ケ・ネ、ャチヌソ・ニ・ケ・ネ、ネ、キ、ニヘュク、ヌ、「、、ウ、ネ、ャシィ、オ、、ソ。」


*Miller-Rabin・ニ・ケ・ネ、ホチヌソネスト熙ホウホホィノセイチ [#i8bfd08e]

。。ク螟マ。「。ヨn、ャケ鄲ョソ。ラ、ォ、ト。ヨMR(n)="accept"。ラ、ャタョ、ホゥ、トウホホィ、ャ、ノ、ホ、ッ、鬢、、ホテヘーハイシ、ヌ、「、、ォ、ノ、ヲ、ォ、ノセイチ、ヌ、ュ、、ミエ、キ、、。」、ウ、、ャ、、ォ、、ミ。「、ノ、ホ、ッ、鬢、ツソテハ、ヒ、ケ、、ミススハャ、ォ、ノ、ヲ、ォ、タオウホ、ヒ、、ォ、。」

。。セレフタ、マセハ、ッ、ャ。「ウホホィ、ネ、キ、ニシ。、ホ、隍ヲ、ハキイフ、ャテホ、鬢、ニ、、、。」

#divid(s,thorem)
[トヘ]。ヨn、ャケ鄲ョソ。ラ、ォ、ト。ヨMR(n)="accept"。ラ、ャタョ、ホゥ、トウホホィ、マ1/4ーハイシ、ヌ、「、。」
#divid(e,thorem)

。。MR(n)、kイニネホゥ、ヒキォ、ハヨ、キ、ソチエツホ、MR_k(n)、ネ、ケ、。」MRSUB{k};(n)、マニ篷、ヌkイMR(n)、・オ・ヨ・。シ・チ・、ネ、キ、ニクニ、モスミ、ケ。」MR(n)、ャ、ケ、ル、ニ"accept"、ハ、鬢ミMRSUB{k};(n)、"accept"。「MR(n)、ャ、メ、ネ、ト、ヌ、"reject"、ハ、鬢ミMRSUB{k};(n)、マ"reject"、ネ、ケ、。」、ト、゙、遙「1イ、ヌ、"reject"、ャスミホマ、オ、、ソ、鬘「MRSUB{k};(n)、"accept"、ネ、、、ヲ、ウ、ネ、ヒ、ハ、。」

。。、隍テ、ニ。「シ。、ホトヘ、ャニタ、鬢、。」

#divid(s,thorem)
[トヘ]。ヨn、ャケ鄲ョソ。ラ、ォ、ト。ヨMRSUB{k};(n)="accept"。ラ、ャタョ、ホゥ、トウホホィ、マ(1/4)SUP{k};ーハイシ、ヌ、「、。」
#divid(e,thorem)

#divid(s,proof)
[セレフタ]MRSUB{k};(n)、マニ篷、ヌ・キ。シ・ア・・キ・罕。「、キ、ォ、稾クト、ス、、セ、、ャニネホゥ、ヒMR(n)、・オ・ヨ・。シ・チ・、ネ、キ、ニクニ、モスミ、ケ、ホ、ヌ。「チエツホ、ホウホホゥ、マ(1/4)SUP{k};ーハイシ、ネ、ハ、。」。。「「
#divid(e,proof)

#divid(s,notice)
ホ1。ァk=10。ハ10イキォ、ハヨ、ケ。ヒ、ヌ、「、、ミ。「n、ャケ鄲ョソ、ハ、ホ、ヒaccept、オ、、ニ、キ、゙、ヲウホホィ、マ1/2SUP{20};。ハ「1/10SUP{6};。ヒ、ヒ、ハ、。」。。。
#divid(e,notice)

#divid(s,notice)
ホ2。ァ1,000・モ・テ・ネ、隍ツ遉ュ、、チヌソ、テオ、ケ、ネ、ュ、マ。「クコケ、ャ(1/2)SUP{80};、隍セョ、オ、ハウホホィ、ネ、ハ、、隍ヲ、ヒk=3、チェ、ル、ミススハャ、ヌ、「、。」。。。
#divid(e,notice)

#divid(s,thorem)
[トヘ]n。3、ャエソ、ホケ鄲ョソ、ヌ、「、、ネ、ュ。「スクケ轆1,。ト,n-1}、ホテ讀ヒ、マn、ネチヌ、ヌ、「、、隍ヲ、ハ。「n、ホMR-liar、ホソ、ャケ筍ケ(n-1)/4クト、キ、ォツクコ゚、キ、ハ、、。」
#divid(e,thorem)

。。、ウ、ホトヘ、マ。ヨn、ャPrimes、ヒエ゙、゙、、ハ、、。ラ「ヘ。ヨPr[MR(n)=accept]。1/4。ラ、ーユフ」、ケ、。」

#divid(s,proof)
[セレフタ]n。ハ。3。ヒ、エソ、ホケ鄲ョソ、ネ、ケ、。」

。。、ウ、ホ、ネ、ュ。「。ヨGCD(a,n)=1、ォ、ト&mimetex("a^r \equiv 1 \pmod{n}");。ト(*)。ラ、゙、ソ、マ。ヨ&mimetex("r \in \{0,1, \cdots ,k-1\}");、ヒツミ、キ、ニ。「&mimetex("a^{2^s r} \equiv -1 \pmod{n}");。ト(**)。ラ、ャタョホゥ、ケ、a「コ{1,。ト,n-1}、ホチソ、ノセイチ、キ、ソ、、。」、ス、ホ、隍ヲ、ハa、ャツクコ゚、キ、ハ、ア、、ミノセイチ、マスェホサ、ケ、。」

。。、゙、コ。「、ス、ホ、隍ヲ、ハMR-liar、ヌ、「、a、ャツクコ゚、ケ、、ネイセト熙ケ、。」、ウ、ホ、ネ、ュ。「(**)、ャタョホゥ、キ、ハ、、MR-liar、ヌ、「、a、篦クコ゚、ケ、。」a、ャ(*)、ヒ、ソ、サ、ミ。「-a、マ(**)、ヒ、ソ、ケ。」

。。、ウ、ウ、ヌ。「GCD(a,n)=1、ォ、ト(**)、ヒ、ソ、ケa、ャツクコ゚、ケ、s、ホコヌツ酖ヘ、t、ネ、ケ、。」、ス、キ、ニ。「m、m:=2SUP{t};r。「n、ホチヌーチ飜ャイ、&mimetex("\prod_{p|n} p^{e(p)}");、ネトオチ、ケ、。」、オ、鬢ヒ。「シ。、ホ4、ト、ホ&mimetex("\mathbb{Z}_n^*");、ホノハャキイ、トオチ、ケ、。」

-&mimetex("J=\{ a+n \mathbb{Z}: GCD(a,n)=1, a^{n-1} \equiv 1 \pmod{n} \}");
-&mimetex("K=\{ a+n \mathbb{Z}: GCD(a,n)=1, a^{m} \equiv \pm 1 \pmod{p^{e(p)}(\forall p|n) \}");
-&mimetex("L=\{ a+n \mathbb{Z}: GCD(a,n)=1, a^{m} \equiv \pm 1 \pmod{n} \}");
-&mimetex("M=\{ a+n \mathbb{Z}: GCD(a,n)=1, a^{m} \equiv 1 \pmod{n} \}");

。。、ウ、ホ、ネ、ュ。「&mimetex("M \subset L \subset K \subset J \subset \mathbb{Z}_n^*");、ャタョ、ホゥ、ト。」、隍テ、ニ。「n、ホMR-witness、ャツクコ゚、キ、ハ、、。「n、ヒチヌ、ハ「マ、ホa、ヒツミ、キ、ニセヘセホ濛+nZ、マL、ヒツー、ケ、。」

。。ク螟マ。「L、ホサリソ&mimetex("\mathbb{Z}_n^*");、ャセッ、ハ、ッ、ネ、4、ヌ、「、、ウ、ネ、シィ、サ、ミ、、ミ、隍、。」

。。K、ホヌ、ーユ、ホクオ、ホハソハ、ャM、ヒエ゙、゙、、、ホ、ヌ。「M、ホK、ヌ、ホサリソ、マ2、ホ、ル、ュセ隍ヌ、「、。」L、ホK、ヒ、ェ、ア、サリソ、マ。「2、ホ・ル・ュ、ヌ、「、。」、ウ、、ホ网ィ、ミ2SUP{j};、ネ、ケ、。」j。2、ホ、ネ、ュ、マL、ホサリソ&mimetex("\mathbb{Z}_n^*");、ャセッ、ハ、ッ、ネ、4、ヌ、「、。」ク螟マ。「j=0,1、ホ、ネ、ュ、ヒL、ホサリソ&mimetex("\mathbb{Z}_n^*");、ャセッ、ハ、ッ、ネ、4、ヌ、「、、ウ、ネ、ォ、ノ、ヲ、ォ、ウホヌァ、ケ、。」

[1]j=1、ホ、ネ、ュ、ケヘ、ィ、

。。n、マ2、ト、ホチヌーソ、サ、ト。」、隍テ、ニ。「n、マ・ォ。シ・゙・、・ア・ソ、ヌ、マ、ハ、、。ハ「隘ォ。シ・゙・、・ア・ソ、ホチヌーソ、マ3クト、「、。ヒ。」、隍テ、ニ。「J、マ&mimetex("\mathbb{Z}_n^*");、ホソソノハャキイ、ヌ、「、遙「J、ホ&mimetex("\mathbb{Z}_n^*");、ヌ、ホサリソ、マセッ、ハ、ッ、ネ、2、ヌ、「、。」L、ホK、ヌ、ホサリソ、穃、ホトオチ、ヒ、隍2、ヌ、「、、ホ、ヌ。「L、ホ&mimetex("\mathbb{Z}_n^*");、ヌ、ホサリソ、マセッ、ハ、ッ、ネ、4、ヌ、「、。」

[2]j=0、ホ、ネ、ュ、ケヘ、ィ、

。。n、マチヌソ・ル・ュ、ヌ、「、。」、ウ、ホセケ遑「J、ャ、チ、遉ヲ、ノp-1、ウ、ホクオ、サ、ト。「ツィ、チス茣キイ&mimetex("\mathbb{Z}_{p^e}^*");、ホーフソp-1、ホノハャキイ、ホクオ、ヌ、「、、ウ、ネ、セレフタ、ケ、、ウ、ネ、ャ、ヌ、ュ、。」、隍テ、ニ。「J、ホ&mimetex("\mathbb{Z}_n^*");、ヌ、ホサリソ、マn=9、ス、、、ニセッ、ハ、ッ、ネ、4、ヌ、「、。」n=9、ヒツミ、キ、ニ、マフソツ熙ャトセタワシィ、オ、、。」。。「「
#divid(e,proof)

*サイケヘハクク・ [#ed1f0be4]

-・シ・゚・ホ。シ・ネ
-ケヨオチ・ホ。シ・ネ
-。リクスツ蟆ナケ讀ホエチテソヘ。ル
-。リーナケ賚マタニフ遑ル
-。リアヘムツ蠢ウリニフ遑ル
-。リIntroduction to Algorithms。ル