逆元の計算

乗法逆元とは

mod.pで

ax ≡1
なる元

ふつうの場合は逆数で

3* 1/3 =1

加法なら

7+(-7)=0

ですが

カードシャッフリングでの乗法逆元はアンチシャッフル

逆元の計算

ax + by =GCD(m)

ふつう
mod.pで

ax ≡1

はGCD(1)だから

ax + by =1

すなわち

ax + yp=1

さらに真ん中の符号をマイナスにしておく

例

十七枚のカードで十進のパーフェクトシャッフルをやったあとに完全にもとのならびに戻すには？

十進の乗法逆元をもとめればよい

拡張版ユークリッドのアルゴリズム

そこでつかうのが拡張版ユークリッドのアルゴリズムというもん

原理はさておいて実際には筆算で簡単にとける

逆元の求め方

10x - 17y =1

のxとyとの特別解を求めればよい

どうやるか

まず大きい方の数をかく

17

そのしたに小さい方の数をかく

17
10

大きい方から小さいほうを引けるだけ引く

その商を右にかく
17
10 1

そうしたら余りをしたにかく

17
10 1
7

またおなじように

17
10 1
7    1
3
これを余りが１になるまでやる

17
10  1
7    1

3    2
1

今度はその列の右側にしたから上に向かって0と1をかきこむ
それはきまりとなってる2

17
10  1
7    1
3    2             1
1→→→→→0

今度はそのうえに先程だした商をかけ算したものをかく

17
10  1
7    1             2
3    2  →→→1    
1→→→→→0

今度も同様にしてとなりの商とかけ算するがその結果に下の数を足した数をかきこむ

17
10  1　　　 3
7 　1→→→ 2
3    2  →→→1    
1→→→→→0

同様にして上までやる

17                5
10   1→→→3
7 　1→→→ 2
3    2  →→→1    
1→→→→→0

うえの二つの数がxyのはず

ここで検算
もとの数字とたすきにかけてみて差が１になればよい

17        \  /    5　=50
10   1   /  \    3   =51
7 　1→→→ 2
3    2  →→→1    
1→→→→→0

答えは小さい方がxで１つ大きい方がy
x=5
y=3

10*5 - 3*17 =-1?

ここでマイナス１となる場合はそれぞれ符号をかえればよい

10*(-5) -17(-3)=1

で

-5≡12  mod.17

ということに注意すると

求める答えは

10*12≡1

十二進のシャッフルをすればよい。