Petitverse

体とは
雑に言うと四則演算(加減乗除)が定義される値の集合だと認識してます。
集合に対して加法と乗法が定義されていて、加法の逆数と乗法の逆数が定義されています。
あとは、分配法則とか結合法則とかお馴染みの法則が成り立ちます。(積の交換法則は成りたたないものについて扱うこともあるけど、だいたい成り立つ)

正直この認識で十分だと思うので、詳しくはお馴染みフェルミウム湾さんのブログでも載せときます。
https://fermiumbay13.hatenablog.com/entry/2022/08/11/091103

身近なところだと、実数はもちろん、有理数や複素数も体です。
あと、整数は体じゃないです(除算が定義できないため環になる)

有限体

値の個数が有限個の体です。
実数も有理数も複素数も値は無限個ありますが、無限個の値はコンピュータでは扱えないので有限個で済むと嬉しい…ぐらいの認識で大丈夫だと思います。
あと、値が有限個だと1の簡単でない累乗根が定義できたり出来なかったり(実数と有理数は1の累乗根は1と-1以外に存在しない。)

有限体の例

一応、一番簡単な有限体として0と1からなる整数の集合があるんですけど、ここの人ってブール代数に馴染みあるんですかね？

この場合、加法と乗法はお馴染みXORとANDになります。
0の加法における逆数は0で、1の逆数は加法乗法ともに1になります。
ブール代数をある程度勉強すると、途中からXORとANDしか扱わなくなりますが、あれは四則演算が定義できて嬉しいからですね。

もう少し馴染みのある例を挙げると、整数を素数pで割ったあまり(合同式)も有限体です。先のブール代数もp=2の合同式と言えます。
素数pは1000000007や20123,31などなんでも良いですが、ここでは小さめの素数として13を例に挙げます。

加算,乗算は普通に計算した後、mod pすれば良いです。
減算については、普通に減算した後、pを足してmod pすれば良いです。

除算についても、0以外の全ての要素について逆数が存在(モジュラ逆数)します。
p=13の場合、リンク先に逆数の表があります。
http://nadamath2012.web.fc2.com/bushi/2006_simoo.pdf

一般の有限体

そろそろ僕の代数学の知識が追い付かなくなってきた…

https://qiita.com/bellbind/items/5636c99be7ed8d7eaaf1

一般の有限体の要素数(位数)は素数pと整数nを用いてpow(p,n)と表現できます。
ところで、コンピュータのメモリは整数nを用いて2^n個の値を表現できる(3^nのコンピュータも無くはない)ので、有限体と相性が良い気がします。

一般の有限体は、係数がp未満,次数がn未満の多項式で表すことが出来ます。

例えば、p=3,n=2の場合
(0a+0,0a+1,0a+2,1a+0,1a+1,1a+2,2a+0,2a+1,2a+2)
=(0,1,2,a,a+1,a+2,2a,2a+1,2a+2)
の要素を持ちます。

このaの具体的な値については一旦考えないでください。
複素数における虚数単位jのような独立した次元を持つ単位です。

係数はp未満,次数はn未満である必要があります。
通常の多項式と同様に計算した場合、これを超える可能性があります。
そのため、何らかの工夫が必要です。
合同式ではある素数pで割ったあまりを求めたわけなので、多項式で割ったあまりを考えます。

多項式pは有限体上で0である必要があります。

有限体の加減算
次数の同じ項どうしを加減算します。

定数倍
加減算とそう変わりません。

乗算
この辺から分からない
先に書いた通り、多項式で割ったあまりを求める必要があって、その多項式で割ったあまりも有限体である必要がある。

あぁ…楕円曲線暗号も有限体ですね。
いや、暗号なら実装するとしてもRSAの方やりたいですし、書くとしてもCUDAですね。

何やりたいかって言うと、QRコードでPCとかにデータ送れるようにしたいんですよね。

で、調べたらどうやら一般の有限体でもフェルマーの小定理が成り立つ…のかな？
これは何かヒントになりそう。

https://www.swetake.com/qrcode/qr3.html

あー。やっぱりあるんですね。SwitchではQR古寺使ってたのでそういうの使うのもありなんですよね。

それはそれとして、有限体上でFFTしたいので引き続き情報収集
いや、乗算さえ理解できればFFTも理解できそうなんですけどね。
…？
合同式上でのFFT(高速数論変換)では原始根というものを調べる必要があった(有名な素数だとgoogle検索で出てくる)んですけど、合同式を一般化した有限体では原始根は必要なさそう…？

これは僕の理解が間違っているのか、合同式を有限体と見なすことで原始根を効率的に見付けられるのか、あるいは原始多項式を見付けるのは原始根を見付けるのと同様に難しいのか…

https://zuruyasumineko2002.hatenablog.com/entry/2020/11/28/183343
お気持ちが書いてあるサイト。
素数が合同式上の任意の元と互いに素なように、有限体のそれ(原始多項式)もそう…ってことなんですかね？

別件で疑似乱数について調べてたら、どうも疑似乱数にも有限体が使われてるとか…

今更ながらお気持ちが書いてあるサイト読みました。
まず、既約多項式である必要性について、例えば値が法の約数である場合、逆数が存在しなくなって除算が定義できないので約数の存在しない既約多項式である必要があるって感じですね。

そして、既約多項式が素数と対応するように、原始多項式は原始根と対応する。原始多項式は原始根同様簡単には見つからないって感じですね。


原始多項式は原始根と同様の性質を持っていて、つまり(位数-1)乗することで初めて1になる。


…なるほど。完全には理解できてないですが、イメージは掴めた気がしますね。

原始多項式がというより、原始多項式の根が原始根と同様の性質を持っている感じか。
で、この原始多項式の根は虚数単位のようなもので、多項式で表現される。

https://youtu.be/gZph3LmttqQ
わかりやすい動画