有限域上的逆元计算求解

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

在正整数有限域 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 即 Standards for Efficient Cryptography Parameters，是指比特币中使用的ECDSA(椭圆曲线数字签名算法)曲线的参数，并且在高效密码学标准中进 ...