問題の変形

剰余類で周期を求める

周期(サイクル)とは

a^r ≡1(mod.p)

となるrでありパーフェクトシャッフルならトップカードが何度かのシャッフルで周遊してまた

もとのトップにもどる(それいがいの枚数のカードも同様にして)その一巡の回数をいう

パーフェクトシャッフルとは

おなじ置換で何度かの入れ換えをやること

たとえば

六枚のカードで二進のパーフェクトシャッフルをやると
(これはin-perfect faro shuffleという)

1 2 3 4 5 6
2 4 6 1 3 5

という置換表示なら

実際には

1 →4→2→1
2 →1→4→2
3 →5→6→3
4→ 2→1→4
5→6→3→5
6→3→5→6

とそれぞれが動くのであり

これを表にすると

    1 2 3 4 5 6
1)2 4 6 1 3 5
2)4 1 5 2 6 3
3)1 2 3 4 5 6

これをサイクル表示で

(1,2,4)
(3,6,5,)

で３サイクルの素なサイクルになる

循環節の長さ

1/19=

循環節なら底が１０ですが

2*10=20≡1　mod.19

から逆元もおなじ周期なはず

十九枚なら

パーフェクトシャッフルでももとめられるか

(パーフェクトファロシャッフルの底は２)

しかも対称性があるので剰余の数列が逆になるだけなので

つまり十九枚のカードでパーフェクトファロシャッフルしてもとにもどる回数がおなじと

10:[10,5,12,6,3,11,15,17,18,9,14,7,13,16,8,4,2,1]

2:  [2,4,8,16,13,7,14,9,18,17,15,11,3,6,12,5,10,1]

しかも対称性から上下にみると

10*2=20≡1
5*4=20≡1
12*8=96≡1
6*16=96≡1
13*3=39≡1
11*7=77≡1
15*14=210≡1
17*9=153≡1

と逆元のペアが全部デテルジャアリマセンカ？

ということはひとつ原始根の元をまわせればその剰余の逆置換をだしてみれば逆元が求まると

ということは逆に

ある原始元のひとつで剰余演算のうえで逆元をもとめて(拡張版ユークリッドのアルゴリズム)
前と後ろから同時に並行で剰余の数列(サイクル)を求めていけるか

いやむしろ相補性があるのでp-1の半分かp-1がでてくるまで計算すればいいことになる。