有限体整数の除算でもしかしたら計算コストが低くなるかもしれない作業仮説

※この文章は私の作業仮説であって、査読（ツッコミ）を必要としています。何かご意見ありましたら是非どうぞ！　

\
こんにちは。
皆さん有限体の除算をしていますか？　
私はアマチュアですがちょっとだけしています。

\
例えば、１９を法とする世界で掛け算をする時、

（３×７）％１９＝２１％１９≡２となりますが、

この逆の場合（割り算）は、

（２／７）％１９＝［ほにゃららら］≡３

になるはずです。

で、この中間の計算の［ほにゃららら］を丁寧に書く時、
フェルマーの小定理を使うと、


```math
（2/7）％19=2・7^{(19-2)}=465261027974414％19≡3
```

となり、これだけでも掛け算の逆は巨大な数を使う計算量が必要になる形です。

で、私が思ったのは、「これって雑な計算でもっと簡素にできるんじゃないか？　」と言うことです。
（お前の考えたことは間違っているぜ、と言うのであればご指摘下さい。
　合ってるけど、もう既にこれは使われているぜ！　と言う話しがあれば、私もそれを知りたいのでこちらも是非教えて下さい。）

では参りましょう。

# １．法の世界のおさらい

有限体とは一体なんぞや？　なんですが、これは時計の世界とほぼ同じです。

夜中の０時から数えて１時間後は１時、２時間後は２時になる訳ですが、では夜中の０時から数えて２５時間後は何時でしょうか？　となる時、それは１時になります。
１日の時刻を０〜２３の数字で全部表現している世界の中ではこのように考えますが、これを私は書籍の中で、「有限体」と表現しているのを読みました。
あるいは要素集合の中で閉じている、とも表現されています。
また、この場合は２４と言う単位の中で数字をやりとりしているので、この０〜２３の数字を使った、閉じた世界で表現されるこの「２４」と言う数字は位数と言っています。
また、２４を位数として存在する有限体は、２４を法とする、とも書きます。

上記の例であればこれはほぼ割り算の余りの世界です。
0時から25時間経過したら何時になった？　と言うと、答えは25/24で、余りが1になるから1時、と言う具合です。

ではこんな要領で、次は24ではなく19を位数とした時計版を考えます。


# ２．法の中の掛け算

例えば、１９を法とする場合の３×７を考えます。

（３×７）％１９＝２１％１９≡２

は２４時ではなく１９時まである世界での時計版を考えると次のようになります。

![3_7_mod19_001a.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3897419/f9b5173f-91a6-ff9b-3f0d-5cfe5351af3c.png)

３時間のフェーズが７回経過したら、その時１９時まである世界では２時になる、と言うことですね。

あるいは１９を法とする場合の９×５を考えます。

（９×５）％１９＝４５％１９≡７

![9_5_mod19_001a.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3897419/0ea7b266-91dd-6717-9283-45c265d32da1.png)

９時間のフェーズが５回経過したら、その時１９時まである世界では７時になる、と言うことです。

\
ではお題ですが、この計算の逆、すなわち、
\
「１９を時刻の法とする世界で、今２時である。作業フェーズが前日以前から７回行われている時の、作業の最短時間は何時間か？　（時間は正の整数）」
\
「１９を時刻の法とする世界で、今７時である。作業フェーズが前日以前から５回行われている時の、作業の最短時間は何時間か？　（時間は正の整数）」



\
と言うことが有限体内での除算（割り算）に当たるでしょう。


# ３．法の中の割り算

ではこの時に割り算ではどうするかというと、フェルマーの小定理を使います。

フェルマーの小定理
```math
b^{-1}=b^{-1}・_f1=b^{-1}・_f b^{　p-1}=b^{p-2}
```

と言うことで、とある数で割りたい時には、pを法とする世界であるならば、そのp-2乗で掛け算してMODすればいいんだよ、と言う形で解決します。

上記の例の場合は、

```math
(2/7)％19=2・7^{(19-2)}=465261027974414％19≡3
```
```math
(7/5)％19=7・5^{(19-2)}=5340576171875％19≡9
```

となりますが、これがもうちょっと雑に計算してコスト下げられないか？　と思ってます。

さっきの図を改めて見てみると、

![3_7_mod19_001a.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3897419/f9b5173f-91a6-ff9b-3f0d-5cfe5351af3c.png)

と言うことで、これって最終的な掛け算の答えは２だけれども、じゃあ３時間の作業を７回行って２１時間経過後になって今２時だ、と言うのは分かるけど、途中の１９時間はどこに言ったんだ？　と言うことを考えると、法の世界では切り捨ててるわけですね。
ちなみに私はこのことを「無限の闇に消えている」と表現しています（数学的に凄い不正確な表現であると言うのはご容赦下さいませ）。

何回時計の針が回っても、１日２４時間の世界で生きている我々は、途中で２４ｎ時間経過しようともそれは無視され、あるいは、１日１９時間の世界で生きている人であれば、途中で１９ｎ時間経過した場合、これも同様に法の世界の中ではそれは無視されるのです。

では、掛け算の場合は、余剰した位数×ｎの整数は「無限の闇に消えている」のであれば、割り算の場合は、「余剰した位数×ｎの整数は『無限の闇から持ってくる』」ことを可能にしてもいいのではないか、と考えたのです。

要は、上記の例であれば、適当に１９ｎの数字を割り当てて、余りゼロで割り切れればそれを答えにしてしまっていいのではないか、と。

```math
(2/7)％19=2・7^{(19-2)}=465261027974414％19≡3
```

の場合は、2は7で割り切れない。なので、19×1を足して7で割り切れる21にし、
```math
（2/7)19　→　\lbrace(2+19)/7\rbrace=21/7=3
```

で出してしまう。





```math
(7/5)％19=7・5^{(19-2)}=5340576171875％19≡9
```
の場合は、7は5で割り切れない。
で、一回位数の19を足してみる。
7+19×1=26 →　5で割り切れない。
もう一回位数の19を足してみる。
7+19×2=45 →　5で割り切れる。
と言う感じで割り切れる数になるまで位数を加算する。

この場合、
```math
（7/5)％19　→　\lbrace(7+19*2)/5\rbrace=45/5=9
```

と言う感じでいいんじゃないか、と。

まとめますと、割り算の結果が割り切れるまでに、割られる数（被除数）に対して位数の整数倍を足しこんでいけば解が得られるんじゃなかろーか、と。

異論反論すごいお待ちしてます！　
この場合はダメなんじゃね？　だとか、そもそも考え方自体間違っとる！　だとかですね。