ΥڡϤƤʥ֥åޡɲΥڡޤϤƤʥ֥åޡ Υڡlivedoor åפɲΥڡޤlivedoor å

ܼ

Ϥ

ؤˤư̿ȰˤäƤ͡ʰ̣ġǤϤޤǽǡʸˤΰ̿ˤĤƸڤ롣ΰ̿ȤϰۤʤΤաʽΰ̿ȸäϡǿ̣ˡ

ΰ̿

ޤˡñǿξͤ롣

ˡǿΤȤ

[]
pǿ
\forall~a~\in~Z_p^*
Ȥ롣
ΤȤa^x~\equiv~1~\,~(~mod~\,~p)ȤʤǾxaΰ̿Ȥx=ord_p~(a)ɽ

[]p=5ɽǹͤƤߤ롣

a1234
a11234
a21441
a31324
a41111
a51234
  • ord_5~(2)=4
    • mod 5ˤơ24褷ƽ1ˤʤ뤫顣
  • ord_5~(3)=4
    • mod 5ˤơ34褷ƽ1ˤʤ뤫顣
  • ord_5~(4)=2
    • mod 5ˤơ42褷ƽ1ˤʤ뤫顣

̿ȥåȤΤäƤ٤ǰȤϸȤǰ롣ϰ̿p-1ȤʤȤaΤȤǤ롣嵭p=5ǹͤƤߤ롣

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

ϸp-1ȤʤaȤȤʤΤǡ4ʡp-1=5-1)Ȥʤͤ23Ǥʳ̤ͤϸȳФƤФ褤ˡĤޤꡢZ_5^*θϸ2,3ȤȤˤʤ롣

[]pǿȤ롣
1~\le~ord_p~(a)~\le~p-1

[]̿ꡢord_p~(a)1ʾǤ롣

եޡξꡢaͤ˸¤餺p-1褹ɬ1ˤʤΤǡord_p~(a)\le~p-1Ωġ

ˡΤȤ

[]nanȸߤǤȤ롣
a^s~\equiv~1~\pmod{m}Ǿμsˡn˴ؤaΰ̿Ȥord_n(a)ɽ

ΰ˴ؤ

[]pǿȤ롣
a^m~\equiv~1~\,~(mod~\,~p)ע͡ord_p~(a)~|~m

p礭ۤͭƯ̿ȤǤ롣

[]241 (mod 5)եޡξΩġ

4ڤ4,2,1ʤ1ΤȤ餫ʤΤǡ2ͤƤߤ롣22(4 mod 5)1Ǥ롣

äơord_5~(2)~=4Ȱ̿롣

[]nanȸߤǤȤ롣ΤȤƱͤǤ롣
[1]ord_n(a)~=~s
[2]ʲ2郎Ωġ
(a)sϼǡa^s~\equiv~1~\pmod{n}
(b)a^m~\equiv~1~\pmod{n}ʤСmsܿǤ롣

[]ord_n(a)Ϧ(n)Ǥ롣

[]nanȸߤǤȤ롣ΤȤƱͤǤ롣
[1]ord_n(a)~=~s
[2]ʲ2郎Ωġ
(a)sϼǡa^s~\equiv~1~\pmod{n}
(b)a^m~\equiv~1~\pmod{n}ʤСmsܿǤ

[]m1,m22礭ʸߤǤʤȤn=m1m2Ȥ롣
ΤȤnȸߤǤaˤĤơΩġ
ord_n(a)~\le~\frac{\phi(n)}{2}

ʸ

  • ߥΡ
  • ظŹδÿ
  • ر