リーさん対数問題

パーフェクトシャッフルと離散対数問題

N進パーフェクトシャッフルを連続でやって何回でもとにもどるか

ではN進シャッフルでMの置換にするには

N^x ≡M

例えばmod.7

3^x ≡4

法則

全体がmod.pで足すとmod(p-1)となる組が対となるので

逆元をユークリッドのアルゴリズムで計算して

NS≡1

mod.7だと6で

1と5
2と4
3と3

なので

N^1≡S^5

N^2≡S^4

N^3≡S^3

N^4≡S^2

N^5≡S^1

これでもとめるMが逆元ならp-2でよいことになるが

実際には置換の元がそのままM進の配置とはならずに

N進の置換でMとなる

計算した元がポジションをあらわし実際の置換と対称になってる！

だからスペルトリックにつかうには注意

一致トリックならいいんですが。