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

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

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

int add(int a,int b,int p){
	return (a+b)%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の範囲で計算することができる．

int sub(int a,int b,int p){
	int res=a-b;
	while(res<0||p<res){
		if(res<0){
			res+=p;
		}else{
			res-=p;
		}
	}
	return res;
}

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

int mul(int a,int b,int p){
	return (a*b)%p;
}

int divi(int a,int b,int p){
	if(b==0){
		return -1;
	}
	while(a%b!=0){
		a+=p;
	}
	return a/b;
}

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