• トノイテ、オ、、ソケヤ、マ、ウ、ホソァ、ヌ、ケ。」
  • コス、オ、、ソケヤ、マ、ウ、ホソァ、ヌ、ケ。」
  • クカサマクオ 、リケヤ、ッ。」

*フワシ。 [#ce01e070]

#contents


*クカサマクオ [#w08e61f8]

。。・ユ・ァ・・゙。シ、ホセョトヘ、隍遙「チヌソp、ヒツミ、キ、ニ。「(a,p)=1、ハ、鬢ミ&mimetex("a^{p-1} \equiv 1 \, \pmod{p}");、ャタョ、ホゥ、ト。」

。。、キ、ォ、キ、ハ、ャ、鬘「p-1、隍熙篝ョ、オ、ハk、ヌ&mimetex("a^k \equiv 1 \, \pmod{p}");、ヒ、ソ、ケ、隍ヲ、ハソa、筅「、、ォ、筅キ、、ハ、、。」

。。、ウ、ホ、隍ヲ、ヒa、kセ隍キ、ニス鬢皃ニヒ。p、ホタ、ウヲ、ヌ1、ヒ、ハ、。「ツィ、チ&mimetex("a^k \equiv 1 \, \pmod{p}");、ヒ、ソ、ケk、。「p、ヒ。、ネ、ケ、''a、ホーフソ。ハorder。ヒ''、ネクニ、ヨ。」、ウ、、シ。、ホ、隍ヲ、ヒス、ッ。」

&mimetex("ord_p (a) =k");


**チヌソp、ホクカサマクオ [#mc5ab3db]

[トオチ]p。ァチヌソ、ネ、ケ、。」~
、ウ、ホ、ネ、ュ。「&mimetex("ord_p (g)=p-1");、ネ、ハ、g、。「''p、ホクカサマクオ。ハクカサマコャ。ヲタクタョクオ。ヒ''、ネ、、、ヲ。」

。。、ト、゙、遙「g、p-1セ隍キ、ニス鬢皃ニ1、ヒ、ハ、、隍ヲ、ハクオ、ホ、ウ、ネ、ヌ、「、。」

ホ罍ァp=5

-&mimetex("ord_5 (2)=4");
-&mimetex("ord_5 (3)=4");
-&mimetex("ord_5 (4)=2");

。。クカサマクオ、マp-1、ネ、ハ、テヘa、ネ、、、ヲ、ウ、ネ、ハ、ホ、ヌ。「4。ハ。疳-1=5-1)、ネ、ハ、テヘ、マ2、ネ3、ヌ、「、。ハウ邵フ、ホテ讀ホテヘ、ャクカサマクオ、ネウミ、ィ、ニ、ェ、ア、ミ、隍、。ヒ。」、ト、゙、遙「&mimetex("Z_5^*");、ホクカサマクオ、マ2,3、ネ、、、ヲ、ウ、ネ、ヒ、ハ、。」


[キマ]p。ァチヌソ、ネ、ケ、。」~
。ヨa。ァクカサマクオ。ラ「ヘ。ヨ。「&mimetex("ord_p (g)=p-1");。ラ
。ヨa。ァクカサマクオ。ラ「ヘ。ヨ&mimetex("ord_p (g)=p-1");。ラ


**タオターソm、ホクカサマクオ [#heaa12ec]

。。ーネフ、ヒ。「ノャ、コ、キ、簔ヌソ、ヌ、ハ、、タオターソm。「m、ネチヌ、ハa、ヒツミ、キ、ニ。「シ。、ャタョ、ホゥ、ト。」

&mimetex("a^{\phi(m)} \equiv 1 \pmod{m}");

。。、ウ、、[[・ェ・、・鬘シ、ホトヘ]]、ネクニ、ヨ、ホ、ヌ、「、テ、ソ。」

。。タ隍ロ、ノ、ネニアヘヘ、ヒケヘ、ィ、ニ。「a、イソセ隍ォ、ケ、、ネヒ。m、ホタ、ウヲ、ヌ1、ヒ、ハ、。」

。。、ス、ウ、ヌ。「&mimetex("a^k \equiv 1 \pmod{m}");、ャタョ、ホゥ、ト、隍ヲ、ハコヌセョ、ホタオターソk、。「m、ヒエリ、ケ、''a、ホーフソ''、ネ、、、ヲ。」、ウ、、&mimetex("ord_m(a)");、ネノスオュ、ケ、。」

。。、ス、キ、ニ。「タオターソm、ヒツミ、キ、ニ、篋カサマクオ、ャトオチ、ヌ、ュ、。」

[トオチ]&mimetex("ord_m(g)=\phi(m)");、ヒ、ソ、ケg、。「m、ホ''クカサマクオ''、ネクニ、ヨ。」

ホ罍ァ4、ホクカサマクオ、マ。ゥ

。。、゙、コ。「&mimetex("\phi(4) = \sharp \{ 1,3 \} =2");、ヌ、「、。」

。。クカサマクオ、ホクハ荀マ1,2,3、ヌ、「、遙「、ス、、鬢ャ&mimetex("\phi(4) = 2");セ隍キ、ソ、ネ、ュ、ヒ1、ヒ、ハ、、筅ホ、ャ4、ホクカサマクオ、ヌ、「、。」

-1、ホセケ
--フタ、鬢ォ、ヒ1セ隍ホサナタ、ヌ1、ヒ、ハ、テ、ニ、、、、ォ、鮑カサマクオ、ヌ、マ、ハ、、。」
-2、ホセケ
--2SUP{1};=2
--2SUP{2};=4「0 (mod 4)、ヌーク、ヒ1、ヒーテラ、キ、ハ、、。」
-3、ホセケ
--3SUP{1};=3
--3SUP{2};=9「1 (mod 4)、ヌ1、ヒーテラ、ケ、。」

。。、讀ィ、ヒ。「4、ホクカサマクオ、マ3、ホ、゚、ヌ、「、。」。。。


*クカサマクオ、ネクオ、ホーフソ、ホエリキク [#b5c44218]

。。クカサマクオ、マ[[クオ、ホーフソ]]、ネフゥタワ、ハエリキク、サ、テ、ニ、、、。」

[トヘ]エチヌソp、ヒエリ、ケ、a、ホーフソq。ハ=ordSUB{p};(a)。ヒ、マ。「p-1、ホフソ、ヌ、「、。」~
ツィ、チ。「&mimetex("q|p-1");

[ケヘサ。]

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

[セレフタ]ヌリヘヒ。、ヘム、、、。」ーフソ&mimetex("q(=ord_p(a))");、ャp-1、ウ荀タレ、鬢ハ、、、ネイセト熙ケ、。」、ケ、、ネ。「&mimetex("p-1=k \times q +r \,(0 < r < q)");、ネス、ア、。」

。。、゙、ソ。「シ。、ホ、隍ヲ、ハキラササ、ャ、ヌ、ュ、。」

&mimetex("1");~
&mimetex("\equiv a^{p-1} \pmod{p}");。。。ハ「鐚[・ユ・ァ・・゙。シ、ホセョトヘ]]。ヒ~
&mimetex("\equiv a^{k \times q + r}");~
&mimetex("\equiv a^{k \times q} \cdot a^r");~
&mimetex("\equiv a^r");。。。ハ「雕オ、ホーフソ、ホトオチ、隍遙「&mimetex("a^q \equiv 1 \pmod{p}");。ヒ

。。、隍テ、ニ。「&mimetex("a^r \equiv 1 \pmod{p}");、ャタョ、ホゥ、ト。」

。。、キ、ォ、キ。「r。縡、ヌ、「、、ャ。「q、ホコヌセョタュ。ハーフソ、ホトオチ。ヒ、ヒネソ、ケ、、ホ、ヌフキス筍」

。。、讀ィ、ヒ。「ーフソ&mimetex("q(=ord_p(a))");、マp-1、ウ荀タレ、。」。。「「

*クカサマクオ、ホツクコ゚ [#f1e00d31]

。。ヒ。、ャチヌソ、ル、ュ、ホ、ネ、ュ、ヒ。「クカサマクオ、ャツクコ゚、ケ、、ウ、ネ、シィ、ケ。」

#divid(s,thorem)
[トヘ]n=pSUP{e};。「p、マエチヌソ。「e。1、ホ、ネ、ュ。「ヒ。n、ヒエリ、ケ、クカサマクオ、ャツクコ゚、ケ、。」
#divid(e,thorem)

#divid(s,proof)
[セレフタ]

[1]e=1、ホ、ネ、ュ。「[トヘ]。ヨp、ャチヌソ、ホ、ネ、ュ。「ヒ。p、ヒエリ、ケ、クカサマクオ、ャツクコ゚、ケ、。ラ、隍遙「ツーユ、ャタョ、ホゥ、ト。」

[2]e。1、ホ、ネ、ュ

ヒ。pSUP{e-1};、ヒエリ、ケ、クカサマクオ、ャツクコ゚、ケ、、ネイセト熙キ、ニ。「ヒ。pSUP{e};、ヒエリ、ケ、クカサマクオ、ャツクコ゚、ケ、、ウ、ネ、シィ、ケ。」

イセト熙ネ。ハタオターソm、ホ。ヒクカサマクオ、ホトオチ、隍遙「&mimetex("ord_{p^{e-1}}(a)=\phi(p^{e-1})");、ヒ、ソ、ケターソa、ャツクコ゚、ケ、。」~
、ウ、、マシ。、ホ、隍ヲ、ヒナクウォ、ヌ、ュ、。」

&mimetex("ord_{p^{e-1}}(a) = \phi(p^{e-1})");~
&mimetex("ord_{p^{e-1}}(a) = (p-1)p^{e-2}");。。。ハ「鐚[・ェ・、・鬘シエリソ]]、ホタュシチ。ヒ

、隍テ、ニ。「[トヘ]。ヨn、ャシォチウソ。「a、n、ネク゚、、、ヒチヌ、ハターソ、ネ、ケ、。」、ウ、ホ、ネ、ュ。「シ。、マニアテヘ、ヌ、「、。」~
[1]&mimetex("ord_n(a) = s");~
[2]ーハイシ、ホ2セキ、ャタョ、ホゥ、ト。」~
(a)s、マシォチウソ、ヌ。「&mimetex("a^s \equiv 1 \pmod{n}");~
(b)&mimetex("a^m \equiv 1 \pmod{n}");、ハ、鬢ミ。「m、マs、ホヌワソ、ヌ、「、。ラ、隍遙「シ。、ャタョ、ホゥ、ト。」

-&mimetex("n=p^{e-1}, s=(p-1)p^{e-2}");
-(a)s、マシォチウソ、ヌ。「&mimetex("a^s \equiv 1 \pmod{n}");
-(b)&mimetex("a^m \equiv 1 \pmod{n}");、ハ、鬢ミ。「m、マs、ホヌワソ、ヌ、「、。」。。「ォ(*)

、゙、ソ。「ヒ。pSUP{e};、ヒエリ、ケ、a、ホーフソ、m、ネ、ケ、、ネ。「シ。、ャタョ、ホゥ、ト。」

&mimetex("a^m \equiv 1 \pmod{p^e}");~
&mimetex("a^m \equiv 1 \pmod{p^{e-1}}");。。。ハ「???。ヒ。。「ォ(**)

、ト、゙、遙「(*),(**)、隍遙「ヒ。pSUP{e};、ヒエリ、ケ、a、ホーフソ、ヌ、「、m、マs、ホヌワソ。「ツィ、チm、マ&mimetex("(p-1)p^{e-2}");、ホヌワソ、ヌ、「、。」

ーハ。「[キマ]。ヨ&mimetex("ord_n(a)");、マヲユ(n)、ホフソ、ヌ、「、。ラ、隍遙「ヒ。pSUP{e};、ヒエリ、ケ、a、ホーフソ、マ。「&mimetex("\phi(p^e) = (p-1)p^{e-1}");、ホフソ、ヌ、「、。」

、隍テ、ニ。「ヒ。pSUP{e};、ヒエリ、ケ、a、ホーフソ、マ。「&mimetex("(p-1)p^{e-2}");、ホヌワソ。「、ォ、ト&mimetex("(p-1)p^{e-1}");、ホフソ、ヌ、「、。」~
、ト、゙、遙「ヒ。pSUP{e};、ヒエリ、ケ、a、ホーフソ、マ。「&mimetex("(p-1)p^{e-2} \, or \, (p-1)p^{e-1}");、ヌ、「、。」

(i)ヒ。pSUP{e};、ヒエリ、ケ、a、ホーフソ、ャ&mimetex("(p-1)p^{e-1}(=\phi(p^e))");、ホセケ遑「a、ャヒ。pSUP{e};、ヒエリ、ケ、クカサマクオ、ヌ、「、。」

(ii)ヒ。pSUP{e};、ヒエリ、ケ、a、ホーフソ、ャ&mimetex("(p-1)p^{e-2}");、ホセケ

[トヘ]。ヨn、シォチウソ、ネ、ケ、。」~
(1)&mimetex("ord_n(a)=s,(e。0)");、ホ、ネ、ュ。「&mimetex("ord_n(a^e) = \frac{s}{d}");、ヌ、「、。」、ソ、タ、キ。「d、マs、ネe、ホコヌツ邵フソ、ヌ、「、。」~
(2)&mimetex("ord_n(a)=s,ord_n(b)=t,(s,t)=1");、ホ、ネ、ュ。「&mimetex("ord_n(ab)=st");、ヌ、「、。ラ、ホ(1)、隍遙「シ。、ャタョ、ホゥ、ト。」

-e、ャ、ォ、ヨ、テ、ニ、、、、ホ、ヌ。「トヘツヲ、e'、ネ、キ、ソ。」
-&mimetex("n=p^e");
-&mimetex("e'=p^{e-2}");
-&mimetex("s=ord_n(a)=ord_{p^e}(a)=\phi(p^e)=(p-1)p^{e-1}");
-&mimetex("ord_{p^e}(a^{p^{e-2}}) = p-1");。。「ォ(***)
--。ハコクハユ。ヒ。&mimetex("ord_n(a^e') = ord_{p^e}(a^{p^{e-2}})");
--。ハアヲハユ。ヒ。&mimetex("\frac{s}{d} = \frac{s}{GCD(s,e')} = \frac{(p-1)p^{e-1}}{(p-1)p^{e-2}} = p-1");
---&mimetex("GCD(s,e')=GCD((p-1)p^{e-1}, p^{e-2}) = (p-1)p^{e-2}");

、ウ、ウ、ヌ。「&mimetex("ord_{p^e}(1+p)=p^{e-1}");、ャシィ、オ、、、ミ。「(p-1,pSUP{e-1};)=1、ハ、ホ、ヌ。「セ蠏ュトヘ、ホ(2)、ネ(***)、隍遙「シ。、ャタョ、ホゥ、ト。」

&mimetex("ord_{p^e}(a^{p^{e-2}} \cdot (1+p)) = (p-1) \cdot p^{e-1}");

、ト、゙、遙「&mimetex("(p-1) p^{e-1}=\phi(p^e)");、隍遙「pSUP{e};、ホクカサマクオ、マツクコ゚、キ。「&mimetex("a^{p^{e-2}}(1+p)");、ホクカサマクオ、ヌ、「、。」

ク螟マ。「&mimetex("ord_{p^e}(1+p)=p^{e-1}");、シィ、ケ。」

&mimetex("(1+p)^{p^{e-1}} \equiv 1 + p^{e} \pmod{p^{e+1}}");。。。ハ「鐚トヘ]。ヨp、ャエチヌソ。「e。1、ホ、ネ、ュ。「シ。、ャタョ、ホゥ、ト。」&mimetex("(1+p)^{p^e} \equiv 1 + p^{e+1} \pmod{p^{e+2}}");。ラ、隍遙ヒ~
&mimetex("(1+p)^{p^{e-1}} \equiv 1 \pmod{p^e}");

、隍テ、ニ。「[トヘ]。ヨn、ャシォチウソ。「a、n、ネク゚、、、ヒチヌ、ハターソ、ネ、ケ、。」、ウ、ホ、ネ、ュ。「シ。、マニアテヘ、ヌ、「、。」~
[1]&mimetex("ord_n(a) = s");~
[2]ーハイシ、ホ2セキ、ャタョ、ホゥ、ト。」~
(a)s、マシォチウソ、ヌ。「&mimetex("a^s \equiv 1 \pmod{n}");~
(b)&mimetex("a^m \equiv 1 \pmod{n}");、ハ、鬢ミ。「m、マs、ホヌワソ、ヌ、「、。ラ、ホ[2]、隍遙「シ。、ャタョ、ホゥ、ト。」

-&mimetex("a=1+p, n=p^e, m= p^{e-1}");
-&mimetex("s= ord_n(a)=ord_{p^e} (1+p)");
-&mimetex("m(=p^{e-1})");、マ&mimetex("s(= ord_n(a)=ord_{p^e} (1+p))");、ホヌワソ、ヌ、「、。」
--ツィ、チ。「&mimetex("ord_{p^e}(1+p)");、マpSUP{e-1};、ホフソ、ヌ、「、。」

、ス、ウ、ヌ。「シ。、ホ、隍ヲ、ヒ、ェ、ッ。」

&mimetex("ord_{p^e}(1+p)=p^m, (1 \le m \le e-1)");~
&mimetex("(1+p)^{p^m} \equiv 1 \pmod{p^e}");。。。ハ「雕オ、ホーフソ、ホトオチ。ヒ

、ウ、ウ、ヌm。綟-1、ヌ、「、、ネイセト熙ケ、、ネ。「シ。、ホ、隍ヲ、ヒナクウォ、ソハ、皃、ウ、ネ、ャ、ヌ、ュ、。」

&mimetex("(1+p)^{p^m} \equiv 1 \pmod{p^e}");~
&mimetex("(1+p)^{p^m} \equiv 1 \pmod{p^{m+2}}");。。。ハ「鑪。綟-1、隍遙「m+2。蘰。ヒ~
&mimetex("1+p^{m+1} \equiv 1 \pmod{p^{m+2}}");。。。ハ「鐚トヘ]。ヨp、ャエチヌソ。「e。1、ホ、ネ、ュ。「シ。、ャタョ、ホゥ、ト。」&mimetex("(1+p)^{p^e} \equiv 1 + p^{e+1} \pmod{p^{e+2}}");。ラ、隍遙ヒ~
&mimetex("p^{m+1} \equiv 0 \pmod{p^{m+2}}");

、ウ、、マフキス筅ケ、。」~
、隍テ、ニ。「m=e-1、ヌ、「、。」~
、キ、ソ、ャ、テ、ニ。「&mimetex("ord_{p^e}(1+p)=p^e=p^{e-1}");、ャタョ、ホゥ、ト。」。。「「
#divid(e,proof)

。。シ。、ヒ。「n、ャ2、ホ、ル、ュ、ホセケ遉ケヘ、ィ、。」

#divid(s,thorem)
[トヘ]n=2SUP{e};。「e。3。「a、ャエソ、ホ、ネ、ュ、ヒ。「シ。、ャタョ、ホゥ、ト。」~
&mimetex("ord_{2^e}(a) \le 2^{e-2}");
#divid(e,thorem)

#divid(s,proof)
[セレフタ]

[1]e=3、ホセケ遑「&mimetex("ord_{2^3}(a) \le 2^{3-2}");。「ツィ、チ&mimetex("ord_{8}(a) \le 2");、シィ、ケ。」

、ケ、ル、ニ、ホa、ヒ、ト、、、ニ。「クオ、ホーフソ、ホオ、ケ、、ネシ。、ホトフ、熙ヌ、「、。」

-&mimetex("ord_8(1)=1");
-&mimetex("ord_8(3)=2");
-&mimetex("ord_8(5)=2");
-&mimetex("ord_8(7)=2");

、、、コ、、2ーハイシ、ヌ、「、遙「。「ツーユ、ャタョ、ホゥ、ト。」

[2]e。3、ホセケ

&mimetex("ord_{2^{e-1}}(a) \le 2^{e-3}");、ネイセト熙ケ、。」~
、ウ、ホ、ネ、ュ。「シ。、ャタョ、ホゥ、ト。」

&mimetex("ord_{2^{e-1}}(a) \le 2^{e-3}");。。。ハ「雋セト遙ヒ~
&mimetex("a^{2^{e-3}} \equiv 1 \pmod{2^{e-1}}");~
&mimetex("a^{2^{e-3}} = 1 + b2^{e-1}, (\exist b \in \mathbb{Z})");。。「ォ(*)

、ウ、ホ、ネ、ュ。「&mimetex("a^{2^{e-2}}");、マシ。、ホ、隍ヲ、ヒナクウォ、ヌ、ュ、。」

&mimetex("a^{2^{e-2}}");~
&mimetex("= (a^{2^{e-3}})^2");~
&mimetex("= (1 + b2^{e-1})^2");。。。ハ「(*)。ヒ~
&mimetex("= 1 + b2^e + b^2 2^{2e-2}");~
&mimetex("\equiv 1 \pmod{e^2}");。。。ハ「鐺。3。ヒ

[トヘ]。ヨ。ヨ&mimetex("a^s \equiv 1 \pmod{n}");。ラ「ヘ。ヨ&mimetex("ord_n(a) | s");。ラ。ラ、隍遙「&mimetex("ord_{2^e} (a) \le 2^{e-2}");、ヌ、「、。」~
、キ、ソ、ャ、テ、ニ。「。「ツーユ、ャタョ、ホゥ、ト。」。。「「
#divid(e,proof)

#divid(s,thorem)
[トヘ]n、ャpSUP{e};,2pSUP{e};,。ハp、マエチヌソ。「e。1。ヒ,1,2,4、ホ、ネ、ュ、ホ、゚。「ヒ。n、ヒエリ、ケ、クカサマクオ、ャツクコ゚、ケ、。」
#divid(e,thorem)

#divid(s,proof)
[セレフタ]

[1]n=1、ホ、ネ、ュ

-&mimetex("ord_1(1)=1");

ーハ。「&mimetex("\phi(1)=1");、ヌ、「、遙「&mimetex("ord_1(a)=1");、ヒ、ソ、ケa=1、ャクカサマクオ、ヌ、「、。」

[2]n=2、ホ、ネ、ュ

-&mimetex("ord_2(1)=1");

ーハ。「&mimetex("\phi(2)=1");、ヌ、「、遙「&mimetex("ord_2(a)=1");、ヒ、ソ、ケa=1、ャクカサマクオ、ヌ、「、。」

[3]n=4、ホ、ネ、ュ

-&mimetex("ord_4(1)=1");
-&mimetex("ord_4(3)=2");

ーハ。「&mimetex("\phi(4)=2");、ヌ、「、遙「&mimetex("ord_4(a)=2");、ヒ、ソ、ケa=3、ャクカサマクオ、ヌ、「、。」

[4]n=pSUP{e};。ハp、マチヌソ。「e。1。ヒ、ホ、ネ、ュ

[トヘ]。ヨn=pSUP{e};。「p、マエチヌソ。「e。1、ホ、ネ、ュ。「ヒ。n、ヒエリ、ケ、クカサマクオ、ャツクコ゚、ケ、。ラ、ォ、鯲タ、鬢ォ、ヌ、「、。」

[5]n=2pSUP{e};。ハp、マエチヌソ。「e。1。ヒ、ホ、ネ、ュ

[4]、隍遙「ヒ。pSUP{e};、ヒエリ、ケ、クカサマクオ、ャツクコ゚、キ。「クカサマクオ、a、ネ、ケ、、ネ。「シ。、ャタョ、ホゥ、ト。」

&mimetex("\phi(p^e)");~
&mimetex("= ord_{p^e}(a)");。。。ハ「靈。pSUP{e};、ヒエリ、ケ、クカサマクオ、ャツクコ゚、キ。「クカサマクオ、a、ネ、ケ、。ヒ~
&mimetex("\le ord_{2p^e}(a)");。。。ハ「雕オ、ホーフソ、ホトオチ、隍遙ヒ~
&mimetex("\le \phi(2p^e)");。。。ハ「鐚トヘ]。ヨn、ャシォチウソ。「a、n、ネク゚、、、ヒチヌ、ハターソ、ネ、ケ、。」、ウ、ホ、ネ、ュ。「シ。、マニアテヘ、ヌ、「、。」~
[1]&mimetex("ord_n(a) = s");~
[2]ーハイシ、ホ2セキ、ャタョ、ホゥ、ト。」~
(a)s、マシォチウソ、ヌ。「&mimetex("a^s \equiv 1 \pmod{n}");~
(b)&mimetex("a^m \equiv 1 \pmod{n}");、ハ、鬢ミ。「m、マs、ホヌワソ、ヌ、「、。ラ。ヒ

、ウ、ウ、ヌ。「&mimetex("\phi(p^e) = \phi(2p^e)");、ハ、ホ、ヌ。「&mimetex("ord_{2p^e}(a) = \phi(2p^e)");、ネ、ハ、遙「a、マヒ。n=2pSUP{e};、ヒエリ、ケ、クカサマクオ、ヌ、「、。」

[6]、ス、ーハウー、ホ、ネ、ュ

[トヘ]。ヨmSUB{1};,mSUB{2};、2、隍ツ遉ュ、ハク゚、、、ヒチヌ、ハ、キシォチウソ、ネ、キ。「n=mSUB{1};mSUB{2};、ネ、ケ、。」~
、ウ、ホ、ネ、ュ。「n、ネク゚、、、ヒチヌ、ハターソa、ヒ、ト、、、ニ。「シ。、ャタョ、ホゥ、ト。」~
&mimetex("ord_n(a) \le \frac{\phi(n)}{2}");。ラ、隍遙「n=mSUB{1};mSUB{2};。ハmSUB{1};,mSUB{2};、マ3ーハセ螟ホク゚、、、ヒチヌ、ハシォチウソ。ヒ、ホ、ネ、ュ、マ。「セ、ヒ&mimetex("ord_n(a) \le \frac{\phi(n)}{2}");、ャタョ、ホゥ、ト。ラ、隍遙「&mimetex("ord_n(a) \not{=} \phi(n)");、ヒ、ハ、遙「クカサマクオ、マツクコ゚、キ、ハ、、。」。。「「
#divid(e,proof)


*クカサマクオ、ホクトソ [#o7788831]

。。&mimetex("Z_5^*");、ホクトソ、マ2クト、ヌ、「、、ウ、ネ、マウホヌァ、キ、ソ。」、ウ、ホ、隍ヲ、ヒ、ケ、ル、ニ、ホクカサマクオ、トエ、ル、ニクトソ、・ォ・ヲ・・ネ、ケ、、ホ、ヌ、マサエヨ、ャ、ォ、ォ、。」シツ、マ。「クカサマクオ、ヒ、マクトソ、ヒエリ、ケ、シ。、ホ、隍ヲ、ハトヘ、ャタョ、ホゥ、ト。」

[トヘ]p、エチヌソ、ネ、ケ、。」、ウ、ホ、ネ、ュ。「&mimetex("Z_p^*=\{ g^0,g^1, \cdots ,g^{p-2}  \}");、ホクカサマクオ。「ツィ、チp、ホクカサマクオ、マヲユ(p-1)クト、ヌ、「、。」、ソ、タ、キ。「ヲユ(。ヲ)、マ[[・ェ・、・鬘シエリソ]]、ヌ、「、。」

[エムサ。]トヘ、セレフタ、ケ、チー、ヒ。「ソテヘホ网ヌトヘ、ホツナナタュ、ウホヌァ、キ、ニ、゚、。」

。。p=19、ホ、ネ、ュ。「p、ホクカサマクオ。ハヲユ(p)=p-1セ隍ヌ、マ、ク、皃ニ1、ヒ、ハ、、筅ホ。ヒ、マ。「2,3,10,13,14,15、ホ6クト、ヌ、「、。」

。。ーハ。「ヲユ(p-1)=ヲユ(19-1)=ヲユ(18)=ヲユ(2。ヲ3SUP{2};)=18(1-1/2)(1-1/3)=6

。。、隍テ、ニ。「。ハp、ホクカサマクオ、ホクトソ。ヒ。皋ユ(p-1)。6、ャタョ、ホゥ、ト、ウ、ネ、ャエムサ。、ヌ、ュ、ソ。」


[セレフタ]&mimetex("ord_p (g^k) = \frac{p-1}{(k,p-1)}");

。。、゙、ソ。「。ヨgSUP{k};。ァクカサマクオ。ラ「ホ。ヨ(k,p-1)=1。ラ

。。、隍テ、ニ。「クカサマクオ、ホソ。皋ユ。ハp-1)、ヒ、ハ、。」。。「「

[ハフセレ]d|p-1、ネ、キ、ニ。「ーフソd、ヌ、「、ターソb、ャツクコ゚、キ、ソ、ネ、ケ、。」

。。、ケ、、ネ。「&mimetex("b^d \equiv 1 \pmod{p} \wedge b^k \not{\equiv} 1 \pmod{p} \wedge k < d");、ャタョ、ホゥ、ト。」

。。、隍テ、ニ。「mod p、ヌb、ホ、ル、ュセ隍コ、、ネ。「

&mimetex("1,b,b^2,\cdots, b^{d-1}");。。。ト(*)

、ネ、ハ、。」

。。、ウ、、鬢マ、ケ、ル、ニdセ隍ケ、、ネ。「1、ヒーテラ、ケ、。ハ「&mimetex("(b^j)^d \equiv (b^d)^j \equiv 1 \pmod{p}");。ヒ。」

。。、隍テ、ニ。「ハトシー&mimetex("x^d \equiv 1 \pmod{p}");、ホコャ、ヌ、「、遙「[[・鬣ー・鬣・ク・螟ホトヘ]]、隍遙「dシ。、ホケ酥アハトシー、ホイ、ホクトソ、マd、トカ、ィ、ハ、、、ホ、ヌ。「(*)、ャ、ケ、ル、ニ、ヌ、「、。」

。。シ。、ヒ。「(*)、ホテ讀ヌ。ヨーフソ、ャd、ヌ、「、ソ。ラ、ホクトソ、トエ、ル、。」、ウ、ウ、ヌ。「bSUP{j};、ホーフソ、e、ネ、ェ、ッ。」

。。、ケ、、ネ。「&mimetex("b^{je} \equiv (b^j)^e \equiv 1 \pmod{p}");、隍遙「&mimetex("ord_p (b) |je");。ハ「鐚トヘ]。ヨm。ァタオターソ。「(a,m)=1、ネ、ケ、。」、ウ、ホ、ネ、ュ。「&mimetex("a^d \equiv 1 \pmod{m}");、ハ、鬢ミ。「&mimetex("ord_m (a) |d");。ラ、隍遙ヒ

&mimetex("ord_p (b) |je");~
&mimetex("d|je");。ハ「霎レフタコヌス鬢ホイセト熙隍遙「&mimetex("ord_p (b) = d");。ヒ~
&mimetex("je \equiv 0 \pmod{d}");~
&mimetex("j_1 ge \equiv 0 \pmod{g d_1}");。ハ「(j,d)=g,j/g=jSUB{1};,d/g=dSUB{1};,(jSUB{1};,dSUB{1};)=1、ネ、ェ、ッ。ヒ~
&mimetex("j_1 e \equiv 0 \pmod{d_1}");。ハ「靜セハユ、d、ヌウ荀テ、ソ。ヒ~
&mimetex("e \equiv 0 \pmod{d_1}");。。。ト(**)。ハ「(jSUB{1};,dSUB{1};)=1、ホセカキ、ヌホセハユ、jSUB{1};、ヌウ荀テ、ソ。ヒ

。。ツセハ。「b、ホーフソ、マd、隍遙「

&mimetex("(b^j)^{d_1}");~
&mimetex("= b^{jd_1}");~
&mimetex("= b^{gj_1 d_1");。ハ「鑠=gjSUB{1};。ヒ~
&mimetex("= b^{j_1 d}");。ハ「鑒dSUB{1};=d。ヒ~
&mimetex("= (b^d)^{j_1}");~
&mimetex("\equiv 1 \pmod{p}");

。&mimetex("Ind_p (b^j) | d_1");~
&mimetex("e| d_1");。ハ「鐫SUP{j};、ホーフソ、e、ネ、ェ、、、ニ、、、ソ、ホ、ヌ。ヒ~
&mimetex("d_1 \equiv 0 \pmod{e}");。。。ト(***)

。。(**)(***)、隍遙「e=dSUB{1};、ヌ、「、。」

。。、隍テ、ニ。「

&mimetex("ord_p ( b^j )");~
&mimetex("=e");。ハ「雋セト遙ヒ~
&mimetex("=d_1");。ハ「&mimetex("e= d_1");。ヒ~
&mimetex("=\frac{d}{g}");~
&mimetex("=\frac{d}{(j,d)}");

。。bSUP{j};、ホーフソ、ャd、ネ、ハ、、ソ、皃ホセキ、マ。「j。綸、隍遙「(j,d)=1、ヌ、「、。」

&mimetex("b^0=1,b^1,b^2,\cdots,b^j,\cdots,b^{d-1}");

、ホ、ヲ、チ、ヌ。「、ウ、ホセキ、ヒ、ソ、ケ、筅ホ、マ&mimetex("\phi(d)");クト、ヌ、「、。」

。。j、マp-1、ホ、ノ、ホフソ&mimetex("d_1,d_2,\cdots,d_k");、ヒ、ト、、、ニ、簇アヘヘ、ヌ、「、。」

-dSUB{1};、マヲユ(dSUB{1};)クト
-。ト
-dSUB{k};、マヲユ(dSUB{k};)クト

。。ニテ、ヒ。「ーフソp-1、ネ、ハ、ソ。「ツィ、チp、ホクカサマクオ、マヲユ(p-1)クト、ヌ、「、。」。。「「

[ケヘサ。]&mimetex("Z_n^*");、ヌケヘ、ィ、、ネ。「、ス、、ヒエ゙、゙、、クカサマクオ、マヲユ(ヲユ(n))、ヒ、ハ、。」、゙、コ&mimetex("Z_n^*");、ホヘラチヌ、ホクトソ、マヲユ(n)、ヒ、ハ、遙「、ス、、ヒヲユ、キラササ、ケ、、ホ、ヌ。「チエツホ、ネ、キ、ニヲユ(ヲユ(n))クト、ヒ、ハ、。」。。。

。。ーハセ螟ホ、ウ、ネ、ォ、鬘「クカサマクオ、マチエツホ、ホソ、ォ、鮑ォ、ニ、筅ソ、ッ、オ、、「、、ウ、ネ、ャ、、ォ、。」&mimetex("Z_p^*");、マヘラチヌソ、ャp-1クト、ハ、ホ、ヌ。「、ス、ホテ讀ホクカサマクオ、マヲユ(p-1)クト、ヒ、ハ、。」ホ网ィ、ミ。「p=7、ヌケヘ、ィ、、ネ。「シ。、ホ、隍ヲ、ヒクカサマクオ、ホクトソ、キラササ、ヌ、ュ、。」

&mimetex("\phi(7-1)=\phi(6)=\phi(2 \cdot 3)=\phi(2)\phi(3)=1 \cdot 2=2");


~
~

。。、ネ、ウ、、ヌ。「&mimetex("\phi(d_1) + \phi(d_1) + \cdots + \phi(d_k) = p-1");、ャタョ、ホゥ、ト。」

。。p=19、ホ、ネ、ュ。「p-1=18、ホフソ、ーフソ、ヒサ、トクトソ、トエ、ル、。」

|#(ーフソ、ャ1、ホクトソ)=#{1}=1|ヲユ(1)=1|
|#(ーフソ、ャ2、ホクトソ)=#{18}=1|ヲユ(2)=1|
|#(ーフソ、ャ3、ホクトソ)=#{7,11}=1|ヲユ(3)=2|
|#(ーフソ、ャ6、ホクトソ)=#{8,12}=1|ヲユ(6)=2|
|#(ーフソ、ャ9、ホクトソ)=#{4,5,6,9,16,17}=1|ヲユ(9)=6|
|#(ーフソ、ャ18、ホクトソ)=#{2,3,10,13,14,15}=1|ヲユ(18)=6|

。。ノス、ホコク、ホホ、ホソ、ホマツ、マ18、ヌ、「、遙「アヲ、ホホ、ホマツ、ホマツ、マ18、ヒ、ハ、遙「ーテラ、キ、ニ、、、、ウ、ネウホヌァ、ヌ、ュ、。」


**クカサマクオ、ホウ荵 [#c78ccc94]

。。ヲユ(n)、マn、ヒ、隍テ、ニーロ、ハ、、ャ。「ハソカム、ケ、、ネ&mimetex("\frac{6n}{\pi^2}");。ハ「0.6。ヒ、ネ、、、ヲサシツ、ャ、「、[HW79]。」、隍テ、ニ。「ヲユ(ヲユ(n))、マハソカム、ケ、、ネフ0.36、ネ、、、ヲ、ウ、ネ、ヒ、ハ、。」、ト、゙、遙「チエツホ、ホ36%、ャクカサマクオ、ネ、キ、ニシ隍、、ネ、、、ヲ、ウ、ネ、ヌ、「、。」



*クカサマクオ、ホエリキク、ケ、トヘ [#qb9bac7d]

[トヘ]~
p。ァチヌソ。「g。ァ&mimetex("Z_p^*");、ホクカサマクオ、ネ、ケ、。」~
、ウ、ホ、ネ、ュ。「&mimetex("a_{i} =g^{i} \, (mod \, p) \,(i=0,\cdots,p-2)");、ネ、ェ、ッ、ネ。「シ。、ャタョ、ホゥ、ト。」~
&mimetex("\{ a_0,a_1,\cdots,a_{p-2} \}= \{1,2,\cdots,p-1 \}");

[セレフタ]セケ醋ャ、ア、キ、ニケヘ、ィ、。」

[1]「シ、シィ、ケ。」

&mimetex("a_i \in \{ 1,\cdots,p-1 \}");、ヌ、「、、ォ、鬘「&mimetex("\{ a_0,a_1,\cdots,a_{p-2} \} \subseteq \{1,2,\cdots,p-1 \}");、マフタ、鬢ォ、ヒタョ、ホゥ、ト。」

[2]「ス、シィ、ケ。」

&mimetex("\{ a_0,a_1,\cdots,a_{p-2} \} \supseteq \{1,2,\cdots,p-1 \}");、シィ、ケ、ソ、皃ヒ、マ。「&mimetex("|\{ a_0,a_1,\cdots,a_{p-2} \} |=p-1");、シィ、サ、ミ、隍、。」

。。、ウ、ウ、ヌ。「ウニaSUB{i};、ャ、ケ、ル、ニーロ、ハ、、ミ。「&mimetex("|\{ a_0,a_1,\cdots,a_{p-2} \} |=p-1");、ャタョ、ホゥ、ト。」、ス、ウ、ヌ。「。ヨi。稻。ラ「ヘ。ヨaSUB{i};。秣SUB{j};。ラ、シィ、サ、、ミ、隍、。」

。。ヌリヘヒ。、ヘム、、、。」イセ、ヒ、「、i。臻、ヒツミ、キ、ニ。「。ヨgSUP{i}; (mod p)=g SUP{j}; (mod p)。ラ、ャタョ、ホゥ、ト、ネイセト熙ケ、、ネ。「(g,p)=1、隍&mimetex("g^{i-j} \equiv 1 \, (mod \, p)");、ャニタ、鬢、。」

。。、ウ、ホコクハユ、ホサリソノ、マ0。緤-j。縣-1、ネ、ハ、。」、キ、ォ、キ。「、ウ、、マg、ホーフソ、ャp-1、ヌ、「、、ウ、ネ、ヒネソ、ケ、。」、隍テ、ニ。「フキス筅ャタク、ク、。」。。「「

ホ罍ァシ。、ホセキ、ホ、ネ、ュ、ヌケヘ、ィ、。」

-p=5
-&mimetex("Z_5 = \{ 0,1,2,3,4 \}");
-&mimetex("Z_5^* = \{ 1,2,3,4 \}");
-クカサマクオ&mimetex("g \in Z_5^*");
-g=2,3

[1]g=2、ホ、ネ、ュ

-aSUB{0};「疊SUP{0};「2SUP{0};「1 (mod 5)
-aSUB{1};「疊SUP{1};「2SUP{1};「2 (mod 5)
-aSUB{2};「疊SUP{2};「2SUP{2};「4 (mod 5)
-aSUB{3};「疊SUP{3};「2SUP{3};「8「3 (mod 5)

。。、隍テ、ニ。「{aSUB{0};,aSUB{1};,aSUB{2};,aSUB{3};}={1,2,4,3}={1,2,3,4}、ャタョ、ホゥ、テ、ニ、、、、ウ、ネ、ャ、、ォ、。」

[2]g=3、ホ、ネ、ュ

-aSUB{0};「疊SUP{0};「3SUP{0};「1 (mod 5)
-aSUB{1};「疊SUP{1};「3SUP{1};「3 (mod 5)
-aSUB{2};「疊SUP{2};「3SUP{2};「4 (mod 5)
-aSUB{3};「疊SUP{3};「3SUP{3};「27「2 (mod 5)

。。、隍テ、ニ。「{aSUB{0};,aSUB{1};,aSUB{2};,aSUB{3};}={1,3,4,2}={1,2,3,4}、ャタョ、ホゥ、テ、ニ、、、、ウ、ネ、ャ、、ォ、。」

。。、、、コ、、ヒ、キ、ニ、筍「g、ホテヘ、ャ、、、コ、、ヒ、キ、ニ、籠ヘ、ャノャ、コタョホゥ、ケ、、ウ、ネ、ャウホ、ォ、皃鬢、ソ。」


*クカサマクオ、ホタクタョ・「・・エ・・コ・ [#tbc8a6c2]

。。ーナケ讀ホタ、ウヲ、ヌ、マクカサマクオ、ャウ靂、ケ、。」、ス、ホ、ソ、皈ウ・・ヤ・蝪シ・ソ、ヌクホィナェ、ヒクカサマクオ、タクタョ、ケ、ノャヘラ、ャタク、ク、。」ホ网ィ、ミ。「[[ElGamalーナケ訃]、ハ、ノ、ヒ、ェ、、、ニ、マ。「ツ遉ュ、ハ[[チヌソ]]p、ヒツミ、キ、ニ。「&mimetex("Z_p^*");、ホクカサマクオg、タクタョ、ケ、ノャヘラ、ャ、「、。」

。。チヌヒム、ハ・「・ラ・。シ・チ、マチエソテオコ、ヌ、「、。」、゙、コ。「&mimetex(" g \in Z_p^*");、・鬣・タ・爨ヒチェ、モ。「シ。、ヒ、ス、、ャクカサマクオ、ォ、ノ、ヲ、ォ、ネスト熙ケ、、ミ、隍、。」クカサマクオ、ホトオチ、ォ、鬘「&mimetex("g \not{\equiv} 1, g^2 \not{\equiv} 1,\cdots, g^{p-2} \not{\equiv} 1 \, (mod \, p)");、ャタョ、ホゥ、ニ、ミ。「g、マクカサマクオ、ヌ、「、。」、キ、ォ、キ。「、ウ、ホハヒ。、ヌ、マpSUP{ヲハ};、ホキラササホフ、ャ、ォ、ォ、テ、ニ、キ、゙、ヲ。ハヲハ。ァ・モ・テ・ネソ。ヒ。」サリソサエヨ、ホキラササホフ、ヌ、マ・チ・蝪シ・・・ー・゙・キ・、ヒ、ネ、テ、ニクホィナェ、ヌ、マ、ハ、、。」

。。、ス、ホ、ソ、癸「ツソケ狆ーサエヨ、ヌクカサマクオ、ネスト熙ケ、、隍ヲ、ハクホィ、ホ、隍、ハヒ。、ケヘ、ィ、ハ、ア、、ミ、ハ、鬢ハ、、。」ネスト・「・・エ・・コ・爨ャクホィナェ、ハ、鬢ミ。「・鬣・タ・爨ヒチェツ、ケ、、ホ、篋ホィナェ、ハ、ホ、ヌ。「タクタョ、ネ、、、ヲチエツホ、ヌクォ、ニ、篋ホィナェ、ヒ、ハ、。」

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


**クカサマクオ、ホネスト・「・・エ・・コ・ [#fbac66ed]

[ハ萃鷯~
p-1、ャ&mimetex("p-1= q_0^{e_0} q_1^{e_1} \cdots q_t^{e_t}");、ネチヌーソハャイ、オ、、ソ、ネ、ケ、。」、ウ、ホ、ネ、ュ。「シ。、ャタョ、ホゥ、ト。」~
。ヨg、ャmod p、ホクカサマクオ、ヌ、「、。ラ「ホ。ヨ&mimetex("0 \le \forall i \le t; g^{\frac{p-1}{q_i}} \not{\equiv} 1 \, (mod \, p)");。ハ。ト(*)。ヒ。ラ

[セレフタ]フー、ホク、ュ、ハャ、ア、ニケヘ、ィ、。」

[1]「ヘ、シィ、ケ。」

。。g、ャクカサマクオ、ヌ、「、、ミ。「フタ、鬢ォ、ヒタョ、ホゥ、ト。」、ハ、シ、ハ、鬢ミ。「g、ャクカサマクオ、ハ、鬘「mod p、ホタ、ウヲ、ヌp-1セ隍キ、ハ、、、ネ「1、ヒ、ハ、鬢ハ、、、ォ、鬢ヌ、「、。」

[2]「ォ、シィ、ケ。」

。。ツミカ、サネ、テ、ニシィ、ケ。」、ト、゙、遙「シィ、キ、ソ、、シ酘・、マ。ヨg、ャmod p、ホクカサマクオ、ヌ、ハ、、。ラ「ヘ。ヨ&mimetex("0 \le \exist i \le t; g^{\frac{p-1}{q_i}} \equiv 1 \, (mod \, p)");。ラ。ハ。ト(**)。ヒ、ヌ、「、。」

。。g、ャクカサマクオ、ヌ、ハ、、、ハ、鬢ミ。「[トヘ]。ヨ「マa;ordSUB{p};|p-1。ラ、隍遙「。ヨordSUB{p};(g)|p-1。ラ、ヒ、ソ、ケ。」、隍テ、ニ。「、「、m。2、ヒツミ、キ、ニ。「p-1=ordSUB{p};(g)。゚m、ャタョ、ホゥ、ト。」

。。イセト熙ネチネ、゚ケ遉、サ、、ネ。「シ。、ャタョ、ホゥ、ト。」

&mimetex("q_0^{e_0} q_1^{e_1} \cdots q_t^{e_t} = p-1 = ord_p (g) \times m");

。。、隍テ、ニ。「qSUB{i};|m、ャタョ、ホゥ、ト。」

。。、ウ、ホ、ネ、ュ。「&mimetex("p-1 = ord_p (g) \times q_i \times h");

&mimetex("g \frac{p-1}{q_i}");~
&mimetex("\equiv g^{ord_p (g) \times h}");~
&mimetex("\equiv (g^{ord_p (g)})^h");~
&mimetex("\equiv 1 \, (mod \, p)");。。。ハ「&mimetex("(g^{ord_p (g)})^h \equiv 1");。ヒ

。。、ウ、、マ(**)、ヒ、ソ、ケ。」。。「「

ホ罍ァp=11、ネ、ケ、。」p-1=10、ホチヌーソ、マ2、ネ5、ヌ、「、。」

[1]。ハセ蠏ュ、ホトヘ、ヘヘム、キ、ニ。ヒ2、ャタクタョクオ、ォトエ、ル、

-2SUP{(11-1)/5};「4。1 (mod 11)
-2SUP{(11-1)/2};「10。1 (mod 11)

。。、ノ、チ、鬢ホキイフ、1、ヒーテラ、キ、ハ、、、ホ、ヌ。「2、マタクタョクオ、ヌ、「、。」

[2]3、ャタクタョクオ、ォトエ、ル、

-3SUP{(11-1)/5};「9。1 (mod 11)
-3SUP{(11-1)/2};「1 (mod 11)

。。1、ヒーテラ、ケ、、筅ホ、ャ、「、テ、ソ、ホ、ヌ。「3、マタクタョクオ、ヌ、マ、ハ、、。」。。。

。。、ウ、ホトヘ、サネ、ヲ、ネ。「(*)、t+1イ・チ・ァ・テ・ッ、ケ、、タ、ア、ヌ。「クカサマクオ、ォ、ノ、ヲ、ォ、ネスト熙ヌ、ュ、、ウ、ネ、ヒ、ハ、。」

。。、ネ、ウ、、ャ。「、ウ、ホトヘ、マクカサマクオ、ホネスト・「・・エ・・コ・爨ヒヘヘム、ヌ、ュ、ス、ヲ、タ、ャ。「シツコン、ヒ、マサネ、ヲ、ウ、ネ、マ、ヌ、ュ、ハ、、。」、ハ、シ、ハ、鬢ミ。「ElGamalーナケ讀ホ、ネ、ュ、マp=1,024・モ・テ・ネ、ハ、ホ、ヌ。「p、チヌーソハャイ、ケ、、ウ、ネ、マフオヘ、ヌ、「、。」、ウ、ホトヘ、サネ、ヲ、ソ、皃ヒ、マ。「p-1、ホチヌーソハャイ、テホ、鬢ハ、ア、、ミ、ハ、鬢ハ、、、ソ、癸「トセタワサネ、ヲ、ウ、ネ、マノヤイトヌス、ヌ、「、。」

。。、ス、ウ、ヌ。「シツチ、ヒ、ェ、、、ニ、マシ。、ホ、隍ヲ、ヒケヤ、ヲ。」

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

1。ァq、・鬣・タ・爨ヒチェ、モ。「[[チヌソネスト・「・・エ・・コ・濔]、ヌネスト熙ケ、。」ノ眛フ、ヒMiller-Rabin・「・・エ・・コ・爨サネ、ィ、ミ、隍、。」

2。ァシ。、ヒp=2q+1、キラササ、キ。「、ウ、ホp、ャチヌソ、ォ、ノ、ヲ、ォ、チヌソネスト・「・・エ・・コ・爨ヌネスト熙ケ、。」

3。ァ、筅キp,q、ノ、チ、鬢簔ヌソ、ハ、鬢ミ。「p-1、ホチヌーソ、マ2、ネq、ネ、ケ、ヌ、ヒテホ、テ、ニ、、、、ホ、ヌ。「セ蠏ュ、ホクカサマクオ、ォ、ノ、ヲ、ォ、ネスト熙ケ、・「・・エ・・コ・爨ヘヘム、ヌ、ュ、。」ゾ、ホクカサマクオタクタョ・「・・エ・・コ・爨マg、ホチェツ、ネクカサマクオネスト・「・・エ・・コ・爨ホチネケ遉、サ、ーユフ」、ネ、キ、ニ、、、。」

。。、チ、ハ、゚、ヒ。「、ソ、テ、ソ2、ト、ホチヌーソ、ハ、ホ、ヌ。「&mimetex("g^2 \equiv 1 \, (mod \, p)");、ネ&mimetex("g^q \equiv 1 \, (mod \, p)");、ホ、ソ、テ、ソ2イ、ホ・チ・ァ・テ・ッ、ホ、゚、ヌクカサマクオ、ホネスト熙ャ、ヌ、ュ、。」、筅キホセハ、ホケ酥アシー、ャヒ、ソ、オ、、ハ、、セケ遉マ。「g、マmod p、ホクカサマクオ、ネ、ハ、、、ア、ヌ、「、。」


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

-・シ・゚・ホ。シ・ネ
-。リソマタニフ遑ル
-。リクスツ蟆ナケ讀ホエチテソヘ。ル
-。リーナケ賚マタニフ遑ル
-。リーナケ豬サスムツ鄰エ。ル
-。リソマタニフ遑ル
-。リーナケ賚マタニフ遑。[ツ2ネヌ]。ル
-[HW79]"An introduction to the theory of numbers"