すべての数理トリックの原理はつながってる
いままでのまとめ
sands -matsuyama の原理は
ひとつは素数ならばそれ以下のすべての数と互いに素なのでかぶらないという素朴な事実
もうひとつは有限素体Fpの元(乗法群の剰余類)は逆元があって可換となる
そして代表元同士の乗法はモジュラー算術で全射となるのでそれで置換の写像となる
シャッフルなら置換の写像が全射なのは当たり前だとわかるけど
だから素数ならN進の閉じた環ができてサイステビンスのシステムができる
SM法でN進数の写像の置換表示をあらわし
剰余の数列としてサイクルをあらわすことができる
あみだくじの写像
N進パーフェクトシャッフルは乗法群でおなじ置換をくりかえすと対称となる
異なる元の置換をしても結果がおなじになる
それは離散対数となる
でもあみだくじみたいに異なる置換の合成は可換でない
順番によって結果が違う
対称群(全置換群)の部分群が置換群？
ということは計算可能な群と可能でない群とがあるのか？
組み合わせ問題というか？
ある置換のサイクルは簡単にもとまるのに
離散対数の問題が困難なのは単純に桁数が多いとメモリーがたりなくなる
処理ができなくなるということでしょう
カードのシャッフルなら何枚が限界なのでしょう？
二つのデックか４つのデックか
わり算して剰余をだす計算じゃなくて
置換表示をソーティングして周期を求めたらどうかと思ったけど
ソーティングでやってもそうなるか？二百桁以上なら。
0 件のコメント:
コメントを投稿