有限域上的逆元计算求解

逆元,即逆元素,是指一个可以取消另一给定元素运算的元素,在数学里,逆元素广义化了加法中的加法逆元和乘法中的倒数。

在正整数有限域 Fp (p是素数)上,a 的乘法逆元 b 满足:ab ≡ 1(mod p)。

例如: a=4, p=23 ,因为 4 * 6 mod 23 = 1,所以 a=4 的逆元为 6。

使用 go 语言求解有限域上的逆元:

package main
import "fmt"

func inv(x, p int) int {
	if x == 0 || x>=p {
		panic("参数 x 必须在 1 到 p-1 之间")
		return 0
	}
	if x == 1 {
		return 1
	}
	return (p - p/x) * inv(p%x, p) % p
}

func main() {
	x := 4
	p := 23
	y := inv(x, p)
	fmt.Printf("x=%v,p=%v 有限域上的逆元:%v", x, p, y)
}

运行后输出结果:

x=4,p=23 有限域上的逆元:6

下一章:比特币协议 Secp256k1

Secp256k1 即 Standards for Efficient Cryptography Parameters,是指比特币中使用的ECDSA(椭圆曲线数字签名算法)曲线的参数,并且在高效密码学标准中进 ...