、ウ、ホ・レ。シ・ク、、マ、ニ、ハ・ヨ・テ・ッ・゙。シ・ッ、ヒトノイテ、ウ、ホ・レ。シ・ク、エ゙、爨マ、ニ、ハ・ヨ・テ・ッ・゙。シ・ッ 、ウ、ホ・レ。シ・ク、livedoor ・ッ・・テ・ラ、ヒトノイテ、ウ、ホ・レ。シ・ク、エ゙、瀝ivedoor ・ッ・・テ・ラ

フワシ。

クカサマクオ

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

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

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

ord_p~(a)~=k

チヌソp、ホクカサマクオ

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

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

ホ罍ァp=5

  • ord_5~(2)=4
  • ord_5~(3)=4
  • ord_5~(4)=2

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

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

タオターソm、ホクカサマクオ

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

a^{\phi(m)}~\equiv~1~\pmod{m}

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

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

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

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

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

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

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

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

  • 1、ホセケ
    • フタ、鬢ォ、ヒ1セ隍ホサナタ、ヌ1、ヒ、ハ、テ、ニ、、、、ォ、鮑カサマクオ、ヌ、マ、ハ、、。」
  • 2、ホセケ
    • 21=2
    • 22=4「0 (mod 4)、ヌーク、ヒ1、ヒーテラ、キ、ハ、、。」
  • 3、ホセケ
    • 31=3
    • 32=9「1 (mod 4)、ヌ1、ヒーテラ、ケ、。」

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

クカサマクオ、ネクオ、ホーフソ、ホエリキク

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

[トヘ]エチヌソp、ヒエリ、ケ、a、ホーフソq。ハ=ordp(a)。ヒ、マ。「p-1、ホフソ、ヌ、「、。」
ツィ、チ。「q|p-1

[ケヘサ。]

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

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

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

。。、隍テ、ニ。「a^r~\equiv~1~\pmod{p}、ャタョ、ホゥ、ト。」

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

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

クカサマクオ、ホツクコ゚

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

[トヘ]n=pe。「p、マエチヌソ。「e。1、ホ、ネ、ュ。「ヒ。n、ヒエリ、ケ、クカサマクオ、ャツクコ゚、ケ、。」

[セレフタ]

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

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

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

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

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

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

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

、゙、ソ。「ヒ。pe、ヒエリ、ケ、a、ホーフソ、m、ネ、ケ、、ネ。「シ。、ャタョ、ホゥ、ト。」

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

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

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

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

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

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

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

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

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

ord_{p^e}(a^{p^{e-2}}~\cdot~(1+p))~=~(p-1)~\cdot~p^{e-1}

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

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

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

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

  • a=1+p,~n=p^e,~m=~p^{e-1}
  • s=~ord_n(a)=ord_{p^e}~(1+p)
  • m(=p^{e-1})、マs(=~ord_n(a)=ord_{p^e}~(1+p))、ホヌワソ、ヌ、「、。」
    • ツィ、チ。「ord_{p^e}(1+p)、マpe-1、ホフソ、ヌ、「、。」

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

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

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

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

、ウ、、マフキス筅ケ、。」
、隍テ、ニ。「m=e-1、ヌ、「、。」
、キ、ソ、ャ、テ、ニ。「ord_{p^e}(1+p)=p^e=p^{e-1}、ャタョ、ホゥ、ト。」。。「「

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

[トヘ]n=2e。「e。3。「a、ャエソ、ホ、ネ、ュ、ヒ。「シ。、ャタョ、ホゥ、ト。」
ord_{2^e}(a)~\le~2^{e-2}

[セレフタ]

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

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

  • ord_8(1)=1
  • ord_8(3)=2
  • ord_8(5)=2
  • ord_8(7)=2

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

[2]e。3、ホセケ

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

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

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

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

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

[トヘ]n、ャpe,2pe,。ハp、マエチヌソ。「e。1。ヒ,1,2,4、ホ、ネ、ュ、ホ、゚。「ヒ。n、ヒエリ、ケ、クカサマクオ、ャツクコ゚、ケ、。」

[セレフタ]

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

  • ord_1(1)=1

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

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

  • ord_2(1)=1

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

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

  • ord_4(1)=1
  • ord_4(3)=2

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

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

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

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

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

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

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

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

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

クカサマクオ、ホクトソ

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

[トヘ]p、エチヌソ、ネ、ケ、。」、ウ、ホ、ネ、ュ。「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。ヲ32)=18(1-1/2)(1-1/3)=6

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

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

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

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

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

。。、ケ、、ネ。「b^d~\equiv~1~\pmod{p}~\wedge~b^k~\not{\equiv}~1~\pmod{p}~\wedge~k~<~d、ャタョ、ホゥ、ト。」

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

1,b,b^2,\cdots,~b^{d-1}。。。ト(*)

、ネ、ハ、。」

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

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

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

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

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

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

(b^j)^{d_1}
=~b^{jd_1}
=~b^{gj_1~d_1。ハ「鑠=gj1。ヒ
=~b^{j_1~d}。ハ「鑒d1=d。ヒ
=~(b^d)^{j_1}
\equiv~1~\pmod{p}

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

。。(**)(***)、隍遙「e=d1、ヌ、「、。」

。。、隍テ、ニ。「

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

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

b^0=1,b^1,b^2,\cdots,b^j,\cdots,b^{d-1}

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

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

  • d1、マヲユ(d1)クト
  • 。ト
  • dk、マヲユ(dk)クト

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

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

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

\phi(7-1)=\phi(6)=\phi(2~\cdot~3)=\phi(2)\phi(3)=1~\cdot~2=2



。。、ネ、ウ、、ヌ。「\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、ヒ、ハ、遙「ーテラ、キ、ニ、、、、ウ、ネウホヌァ、ヌ、ュ、。」

クカサマクオ、ホウ荵

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

クカサマクオ、ホエリキク、ケ、トヘ

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

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

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

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

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

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

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

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

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

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

  • p=5
  • Z_5~=~\{~0,1,2,3,4~\}
  • Z_5^*~=~\{~1,2,3,4~\}
  • クカサマクオg~\in~Z_5^*
  • g=2,3

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

  • a0「疊0「20「1 (mod 5)
  • a1「疊1「21「2 (mod 5)
  • a2「疊2「22「4 (mod 5)
  • a3「疊3「23「8「3 (mod 5)

。。、隍テ、ニ。「{a0,a1,a2,a3}={1,2,4,3}={1,2,3,4}、ャタョ、ホゥ、テ、ニ、、、、ウ、ネ、ャ、、ォ、。」

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

  • a0「疊0「30「1 (mod 5)
  • a1「疊1「31「3 (mod 5)
  • a2「疊2「32「4 (mod 5)
  • a3「疊3「33「27「2 (mod 5)

。。、隍テ、ニ。「{a0,a1,a2,a3}={1,3,4,2}={1,2,3,4}、ャタョ、ホゥ、テ、ニ、、、、ウ、ネ、ャ、、ォ、。」

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

クカサマクオ、ホタクタョ・「・・エ・・コ・

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

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

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

クカサマクオ、ホネスト・「・・エ・・コ・

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

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

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

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

。。、隍テ、ニ。「qi|m、ャタョ、ホゥ、ト。」

。。、ウ、ホ、ネ、ュ。「p-1~=~ord_p~(g)~\times~q_i~\times~h

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

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

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

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

  • 2(11-1)/5「4。1 (mod 11)
  • 2(11-1)/2「10。1 (mod 11)

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

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

  • 3(11-1)/5「9。1 (mod 11)
  • 3(11-1)/2「1 (mod 11)

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

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

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

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

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

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

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

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

サイケヘハクク・

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