C言語で楕円曲線の勉強(1.有限体)

最近,卒研の関係で楕円曲線暗号の勉強をしている.
その勉強のまとめをここに吐き出しておきたい.
個人のまとめなので,内容に不備があろうとも責任を負う事はできない.
 

教科書としては『楕円曲線暗号入門』を使用している.
とても良い資料なので,この資料を読みつつ独自にC言語でプログラムを書いていく予定.
 
まずは,有限体Fpについて.
有限体Fp上では,その要素a,bの加算は(a+b) mod pとなる.
減算も同様に(a-b) mod pとなる.

 
なお,a<0については a = a+p = a+p+p = a+p+p+p =…
p-1<bについてはb = b-p = b-p-p = b-p-p-p =…
と続けていくと0からp-1の範囲で計算することができる.

 
乗算は加算と同様に(a*b) mod pとなる.
乗算については,a/b=(a+p)/b=(a+p+p)/b=…
と変形できるので,割り切れた値を用いる.

 
ソースコード
※除算の関数名をdiviとしているのは,stdlibの中で既にdiv関数が定義されているため.