C言語で楕円曲線の勉強(3.拡張Euclid互除法)

有限体Fp上での除算を拡張Euclid互除法を用いて高速化する.
 

有限体Fpでa÷bしたい

px+by=1となるx,yが求まる.(p,bは互いに素なので,拡張Euclidの互除法を適用可)

by=1となる.(有限体Fp上では,pxは0となる)

b^-1=yとなる.

a÷b=a*(b^-1)=a*yとなる.

除算が乗算になってうれしい.
 
ソースコードは以下のようになる.

 
 
 
Githubの方