golang 实现比特币内核:处理椭圆曲线中的天文数字

news/2024/11/6 21:53:58/

在比特币密码学中，我们需要处理天文数字，这个数字是如此巨大，以至于它很容易超出我们宇宙中原子的总数，也许 64 位的值不足以表示这个数字，而像加、乘、幂这样的操作如果使用 64 位整数会导致溢出，因此我们可能需要借助 golang 的 big 包，我们将通过使用 big.Int 来表示其值字段来更改 FieldNumber 的代码，代码将如下所示：

package elliptic_curveimport ("fmt""math/big"
)//using big package to deal with Astronomical figurestype FieldElement struct {order *big.Int //field ordernum   *big.Int //value of the given element in the field
}func NewFieldElement(order *big.Int, num *big.Int) *FieldElement {/*constructor for FieldElement, its the __init__ if you are from python*/if order.Cmp(num) == -1 {err := fmt.Sprintf("Num not in the range from 0 to %v", order)panic(err)}return &FieldElement{order: order,num:   num,}
}func (f *FieldElement) String() string {//format the object to printable string//its __repr__ if you are from pythonreturn fmt.Sprintf("FieldElement{order: %v, num: %v}", *f.order, *f.num)
}func (f *FieldElement) EqualTo(other *FieldElement) bool {/*two field element is equal if their order and value are equal*/return f.order.Cmp(other.order) == 0 && f.num.Cmp(other.num) == 0
}func (f *FieldElement) checkOrder(other *FieldElement) {if f.order.Cmp(other.order) != 0 {panic("add need to do on field element with the same order")}
}func (f *FieldElement) Add(other *FieldElement) *FieldElement {f.checkOrder(other)//remember to do the modulurvar op big.Intreturn NewFieldElement(f.order, op.Mod(op.Add(f.num, other.num), f.order))
}func (f *FieldElement) Negate() *FieldElement {/*for a field element a, its negate is another element b in field such that(a + b) % order= 0(remember the modulur over order), because the value of elementin the field are smaller than its order, we can easily get the negate of a byorder - a,*/var op big.Intreturn NewFieldElement(f.order, op.Sub(f.order, f.num))
}func (f *FieldElement) Subtract(other *FieldElement) *FieldElement {//first find the negate of the other//add this and the negate of the otherreturn f.Add(other.Negate())
}func (f *FieldElement) Multiply(other *FieldElement) *FieldElement {f.checkOrder(other)//multiplie over modulur of ordervar op big.Intmul := op.Mul(f.num, other.num)return NewFieldElement(f.order, op.Mod(mul, f.order))
}func (f *FieldElement) Power(power *big.Int) *FieldElement {var op big.IntpowerRes := op.Exp(f.num, power, nil)modRes := op.Mod(powerRes, f.order)return NewFieldElement(f.order, modRes)
}func (f *FieldElement) ScalarMul(val *big.Int) *FieldElement {var op big.Intres := op.Mul(f.num, val)res = op.Mod(res, f.order)return NewFieldElement(f.order, res)
}

现在我们需要确保这些更改不会破坏我们的逻辑，让我们再次运行测试，在 main.go 中，我们有以下代码：

package mainimport (ecc "elliptic_curve""fmt""math/big""math/rand"
)func SolveField19MultiplieSet() {//randomly select a num from (1, 18)min := 1max := 18k := rand.Intn(max-min) + minfmt.Printf("randomly select k is : %d\n", k)element := ecc.NewFieldElement(big.NewInt(19), big.NewInt(int64(k)))for i := 0; i < 19; i++ {fmt.Printf("element %d multiplie with %d is %v\n", k, i,element.ScalarMul(big.NewInt(int64(i))))}}func main() {f44 := ecc.NewFieldElement(big.NewInt(57), big.NewInt(44))f33 := ecc.NewFieldElement(big.NewInt(57), big.NewInt(33))// 44 + 33 equal to (44+33) % 57 is 20res := f44.Add(f33)fmt.Printf("field element 44 add to field element 33 is : %v\n", res)//-44 is the negate of field element 44, which is 57 - 44 = 13fmt.Printf("negate of field element 44 is : %v\n", f44.Negate())fmt.Printf("field element 44 - 33 is : %v\n", f44.Subtract(f33))fmt.Printf("field element 33 - 44 is : %v\n", f33.Subtract(f44))//it is easy to check (11+33)%57 == 44//check (46 + 44) % 57 == 33fmt.Printf("check 46 + 44 over modulur 57 is %d\n", (46+44)%57)//check by field elementf46 := ecc.NewFieldElement(big.NewInt(57), big.NewInt(46))fmt.Printf("field element 46 + 44 is %v\n", f46.Add(f44))SolveField19MultiplieSet()
}

运行上述代码将获得以下结果：


field element 44 add to field element 33 is : FieldElement{order: 57, num: 20}
negate of field element 44 is : FieldElement{order: 57, num: 13}
field element 44 - 33 is : FieldElement{order: 57, num: 11}
field element 33 - 44 is : FieldElement{order: 57, num: 46}
check 46 + 44 over modulur 57 is 33
field element 46 + 44 is FieldElement{order: 57, num: 33}
randomly select k is : 2
element 2 multiplie with 0 is FieldElement{order: 19, num: 0}
element 2 multiplie with 1 is FieldElement{order: 19, num: 2}
element 2 multiplie with 2 is FieldElement{order: 19, num: 4}
element 2 multiplie with 3 is FieldElement{order: 19, num: 6}
element 2 multiplie with 4 is FieldElement{order: 19, num: 8}
element 2 multiplie with 5 is FieldElement{order: 19, num: 10}
element 2 multiplie with 6 is FieldElement{order: 19, num: 12}
element 2 multiplie with 7 is FieldElement{order: 19, num: 14}
element 2 multiplie with 8 is FieldElement{order: 19, num: 16}
element 2 multiplie with 9 is FieldElement{order: 19, num: 18}
element 2 multiplie with 10 is FieldElement{order: 19, num: 1}
element 2 multiplie with 11 is FieldElement{order: 19, num: 3}
element 2 multiplie with 12 is FieldElement{order: 19, num: 5}
element 2 multiplie with 13 is FieldElement{order: 19, num: 7}
element 2 multiplie with 14 is FieldElement{order: 19, num: 9}
element 2 multiplie with 15 is FieldElement{order: 19, num: 11}
element 2 multiplie with 16 is FieldElement{order: 19, num: 13}
element 2 multiplie with 17 is FieldElement{order: 19, num: 15}
element 2 multiplie with 18 is FieldElement{order: 19, num: 17}

通过检查结果，我们可以确保 FieldElement 中的更改不会破坏我们之前的逻辑。现在让我们考虑以下问题：
p = 7, 11, 17, 19, 31，以下集合会是什么：
{1 ^(p-1), 2 ^ (p-1), … (p-1)^(p-1)}
让我们在 main.go 中编写代码来解决它：


func ComputeFieldOrderPower() {orders := []int{7, 11, 17, 31}for _, p := range orders {fmt.Printf("value of p is: %d\n", p)for i := 1; i < p; i++ {elm := ecc.NewFieldElement(big.NewInt(int64(p)), big.NewInt(int64(i)))fmt.Printf("for element: %v, its power of p - 1 is: %v\n", elm,elm.Power(big.NewInt(int64(p-1))))}fmt.Println("-------------------------------")}
}func main() {ComputeFieldOrderPower()
}

结果如下：

value of p is: 7
for element: FieldElement{order: 7, num: 1}, its power of p - 1 is: FieldElement{order: 7, num: 1}
for element: FieldElement{order: 7, num: 2}, its power of p - 1 is: FieldElement{order: 7, num: 1}
for element: FieldElement{order: 7, num: 3}, its power of p - 1 is: FieldElement{order: 7, num: 1}
for element: FieldElement{order: 7, num: 4}, its power of p - 1 is: FieldElement{order: 7, num: 1}
for element: FieldElement{order: 7, num: 5}, its power of p - 1 is: FieldElement{order: 7, num: 1}
for element: FieldElement{order: 7, num: 6}, its power of p - 1 is: FieldElement{order: 7, num: 1}
-------------------------------
value of p is: 11
for element: FieldElement{order: 11, num: 1}, its power of p - 1 is: FieldElement{order: 11, num: 1}
for element: FieldElement{order: 11, num: 2}, its power of p - 1 is: FieldElement{order: 11, num: 1}
for element: FieldElement{order: 11, num: 3}, its power of p - 1 is: FieldElement{order: 11, num: 1}
for element: FieldElement{order: 11, num: 4}, its power of p - 1 is: FieldElement{order: 11, num: 1}
for element: FieldElement{order: 11, num: 5}, its power of p - 1 is: FieldElement{order: 11, num: 1}
for element: FieldElement{order: 11, num: 6}, its power of p - 1 is: FieldElement{order: 11, num: 1}
for element: FieldElement{order: 11, num: 7}, its power of p - 1 is: FieldElement{order: 11, num: 1}
for element: FieldElement{order: 11, num: 8}, its power of p - 1 is: FieldElement{order: 11, num: 1}
for element: FieldElement{order: 11, num: 9}, its power of p - 1 is: FieldElement{order: 11, num: 1}
for element: FieldElement{order: 11, num: 10}, its power of p - 1 is: FieldElement{order: 11, num: 1}
-------------------------------
value of p is: 17
for element: FieldElement{order: 17, num: 1}, its power of p - 1 is: FieldElement{order: 17, num: 1}
for element: FieldElement{order: 17, num: 2}, its power of p - 1 is: FieldElement{order: 17, num: 1}
for element: FieldElement{order: 17, num: 3}, its power of p - 1 is: FieldElement{order: 17, num: 1}
for element: FieldElement{order: 17, num: 4}, its power of p - 1 is: FieldElement{order: 17, num: 1}
for element: FieldElement{order: 17, num: 5}, its power of p - 1 is: FieldElement{order: 17, num: 1}
for element: FieldElement{order: 17, num: 6}, its power of p - 1 is: FieldElement{order: 17, num: 1}
for element: FieldElement{order: 17, num: 7}, its power of p - 1 is: FieldElement{order: 17, num: 1}
for element: FieldElement{order: 17, num: 8}, its power of p - 1 is: FieldElement{order: 17, num: 1}
for element: FieldElement{order: 17, num: 9}, its power of p - 1 is: FieldElement{order: 17, num: 1}
for element: FieldElement{order: 17, num: 10}, its power of p - 1 is: FieldElement{order: 17, num: 1}
for element: FieldElement{order: 17, num: 11}, its power of p - 1 is: FieldElement{order: 17, num: 1}
for element: FieldElement{order: 17, num: 12}, its power of p - 1 is: FieldElement{order: 17, num: 1}
for element: FieldElement{order: 17, num: 13}, its power of p - 1 is: FieldElement{order: 17, num: 1}
for element: FieldElement{order: 17, num: 14}, its power of p - 1 is: FieldElement{order: 17, num: 1}
for element: FieldElement{order: 17, num: 15}, its power of p - 1 is: FieldElement{order: 17, num: 1}
for element: FieldElement{order: 17, num: 16}, its power of p - 1 is: FieldElement{order: 17, num: 1}
-------------------------------
value of p is: 31
for element: FieldElement{order: 31, num: 1}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 2}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 3}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 4}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 5}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 6}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 7}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 8}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 9}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 10}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 11}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 12}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 13}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 14}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 15}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 16}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 17}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 18}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 19}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 20}, its power of p - 1 is: FieldElement{order: 31, num: 1}
my@MACdeMacBook-Air bitcoin % go run main.go
value of p is: 7
for element: FieldElement{order: 7, num: 1}, its power of p - 1 is: FieldElement{order: 7, num: 1}
for element: FieldElement{order: 7, num: 2}, its power of p - 1 is: FieldElement{order: 7, num: 1}
for element: FieldElement{order: 7, num: 3}, its power of p - 1 is: FieldElement{order: 7, num: 1}
for element: FieldElement{order: 7, num: 4}, its power of p - 1 is: FieldElement{order: 7, num: 1}
for element: FieldElement{order: 7, num: 5}, its power of p - 1 is: FieldElement{order: 7, num: 1}
for element: FieldElement{order: 7, num: 6}, its power of p - 1 is: FieldElement{order: 7, num: 1}
-------------------------------
value of p is: 11
for element: FieldElement{order: 11, num: 1}, its power of p - 1 is: FieldElement{order: 11, num: 1}
for element: FieldElement{order: 11, num: 2}, its power of p - 1 is: FieldElement{order: 11, num: 1}
for element: FieldElement{order: 11, num: 3}, its power of p - 1 is: FieldElement{order: 11, num: 1}
for element: FieldElement{order: 11, num: 4}, its power of p - 1 is: FieldElement{order: 11, num: 1}
for element: FieldElement{order: 11, num: 5}, its power of p - 1 is: FieldElement{order: 11, num: 1}
for element: FieldElement{order: 11, num: 6}, its power of p - 1 is: FieldElement{order: 11, num: 1}
for element: FieldElement{order: 11, num: 7}, its power of p - 1 is: FieldElement{order: 11, num: 1}
for element: FieldElement{order: 11, num: 8}, its power of p - 1 is: FieldElement{order: 11, num: 1}
for element: FieldElement{order: 11, num: 9}, its power of p - 1 is: FieldElement{order: 11, num: 1}
for element: FieldElement{order: 11, num: 10}, its power of p - 1 is: FieldElement{order: 11, num: 1}
-------------------------------
value of p is: 17
for element: FieldElement{order: 17, num: 1}, its power of p - 1 is: FieldElement{order: 17, num: 1}
for element: FieldElement{order: 17, num: 2}, its power of p - 1 is: FieldElement{order: 17, num: 1}
for element: FieldElement{order: 17, num: 3}, its power of p - 1 is: FieldElement{order: 17, num: 1}
for element: FieldElement{order: 17, num: 4}, its power of p - 1 is: FieldElement{order: 17, num: 1}
for element: FieldElement{order: 17, num: 5}, its power of p - 1 is: FieldElement{order: 17, num: 1}
for element: FieldElement{order: 17, num: 6}, its power of p - 1 is: FieldElement{order: 17, num: 1}
for element: FieldElement{order: 17, num: 7}, its power of p - 1 is: FieldElement{order: 17, num: 1}
for element: FieldElement{order: 17, num: 8}, its power of p - 1 is: FieldElement{order: 17, num: 1}
for element: FieldElement{order: 17, num: 9}, its power of p - 1 is: FieldElement{order: 17, num: 1}
for element: FieldElement{order: 17, num: 10}, its power of p - 1 is: FieldElement{order: 17, num: 1}
for element: FieldElement{order: 17, num: 11}, its power of p - 1 is: FieldElement{order: 17, num: 1}
for element: FieldElement{order: 17, num: 12}, its power of p - 1 is: FieldElement{order: 17, num: 1}
for element: FieldElement{order: 17, num: 13}, its power of p - 1 is: FieldElement{order: 17, num: 1}
for element: FieldElement{order: 17, num: 14}, its power of p - 1 is: FieldElement{order: 17, num: 1}
for element: FieldElement{order: 17, num: 15}, its power of p - 1 is: FieldElement{order: 17, num: 1}
for element: FieldElement{order: 17, num: 16}, its power of p - 1 is: FieldElement{order: 17, num: 1}
-------------------------------
value of p is: 19
for element: FieldElement{order: 19, num: 1}, its power of p - 1 is: FieldElement{order: 19, num: 1}
for element: FieldElement{order: 19, num: 2}, its power of p - 1 is: FieldElement{order: 19, num: 1}
for element: FieldElement{order: 19, num: 3}, its power of p - 1 is: FieldElement{order: 19, num: 1}
for element: FieldElement{order: 19, num: 4}, its power of p - 1 is: FieldElement{order: 19, num: 1}
for element: FieldElement{order: 19, num: 5}, its power of p - 1 is: FieldElement{order: 19, num: 1}
for element: FieldElement{order: 19, num: 6}, its power of p - 1 is: FieldElement{order: 19, num: 1}
for element: FieldElement{order: 19, num: 7}, its power of p - 1 is: FieldElement{order: 19, num: 1}
for element: FieldElement{order: 19, num: 8}, its power of p - 1 is: FieldElement{order: 19, num: 1}
for element: FieldElement{order: 19, num: 9}, its power of p - 1 is: FieldElement{order: 19, num: 1}
for element: FieldElement{order: 19, num: 10}, its power of p - 1 is: FieldElement{order: 19, num: 1}
for element: FieldElement{order: 19, num: 11}, its power of p - 1 is: FieldElement{order: 19, num: 1}
for element: FieldElement{order: 19, num: 12}, its power of p - 1 is: FieldElement{order: 19, num: 1}
for element: FieldElement{order: 19, num: 13}, its power of p - 1 is: FieldElement{order: 19, num: 1}
for element: FieldElement{order: 19, num: 14}, its power of p - 1 is: FieldElement{order: 19, num: 1}
for element: FieldElement{order: 19, num: 15}, its power of p - 1 is: FieldElement{order: 19, num: 1}
for element: FieldElement{order: 19, num: 16}, its power of p - 1 is: FieldElement{order: 19, num: 1}
for element: FieldElement{order: 19, num: 17}, its power of p - 1 is: FieldElement{order: 19, num: 1}
for element: FieldElement{order: 19, num: 18}, its power of p - 1 is: FieldElement{order: 19, num: 1}
-------------------------------
value of p is: 31
for element: FieldElement{order: 31, num: 1}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 2}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 3}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 4}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 5}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 6}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 7}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 8}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 9}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 10}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 11}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 12}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 13}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 14}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 15}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 16}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 17}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 18}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 19}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 20}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 21}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 22}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 23}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 24}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 25}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 26}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 27}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 28}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 29}, its power of p - 1 is: FieldElement{order: 31, num: 1}
for element: FieldElement{order: 31, num: 30}, its power of p - 1 is: FieldElement{order: 31, num: 1}
-------------------------------

你可以看到集合中的所有元素都是1，无论字段的顺序如何，这意味着对于任何有限字段中的任意元素k和顺序p，我们会有：
k ^(p-1) % p == 1
这是一个重要结论，我们将在后续视频中使用它来驱动我们的加密算法。

有限域元素上最难的操作是除法，我们有乘法操作，对于字段中的元素3和7（顺序为19），它们的乘积是(3 * 7) % 19 = 2。现在给定两个字段元素2和7，我们如何得到7？我们定义一个除法操作，它是乘法的逆运算，即2 / 7 = 3，这相当直观。这里我们需要确保分母不是0。

记住在有限的定义中，如果a在字段中，那么还有一个b在字段中，使得a * b = 1。对于3 7 = 2（注意表示模顺序的乘法），如果我们能找到b，使得b * 7 = 1，那么我们就会有3 * 7 * b = 2 * b => 3 * (7 * b) = 2 * b => 3 = 2 * b，这意味着2 / 7是2乘以b的结果，b. 也就是说，如果我们想做除法a / b，我们可以找到b的乘法逆元，称之为c，并使用c与模顺序相乘。

现在问题来了，我们如何找到b的乘法逆元？记住我们上面的问题吗？b ^ (p - 1) % p = 1 => b * b ^(p-2) % p = 1 => b的乘法逆元是b ^ (p-2)。

如果你不能确定为什么对于给定元素b在字段中且b^(p-1) % p = 1，我们有一个小代码片段来获得结果，我们需要使其数学上稳固，然后我们就有了它的证明，结论b^(p-1) % p = 1被称为费马小定理：

对于任何字段元素k（k!=0）和顺序p，我们有{1, 2, 3 …, p-1} <=> {k 1 % p, …, k (p-1) %p} =>
[1 2 3… (p-1)] % p == (k1) (k2) … (k* (p-1)) % p = k^(p-1) * [1 2 … p-1] % p，两边消去[12…p-1]我们得到1 % p == k ^(p-1) % p => 1 == k^(p-1)%p

现在让我们看看如何使用代码实现除法操作：


func (f *FieldElement) Multiply(other *FieldElement) *FieldElement {f.checkOrder(other)// 模顺序进行乘法var op big.Intmul := op.Mul(f.num, other.num)return NewFieldElement(f.order, op.Mod(mul, f.order))
}

因为b ^ (p - 1) % p = 1，所以当我们计算字段元素k的T次方时，我们可以优化为首先获取t = T % (p-1)，然后计算k^(t) % p，这里是代码：


func (f *FieldElement) Power(power *big.Int) *FieldElement {/*k ^ (p-1) % p = 1，我们可以计算t = power % (p-1)然后k ^ power % p == k ^ t %p*/var op big.Intt := op.Mod(power, op.Sub(f.order, big.NewInt(int64(1))))powerRes := op.Exp(f.num, t, nil)modRes := op.Mod(powerRes, f.order)return NewFieldElement(f.order, modRes)
}

现在我们可以在main.go中检查我们的代码：


package mainimport (ecc "elliptic_curve""fmt""math/big""math/rand"
)func main() {f2 := ecc.NewFieldElement(big.NewInt(int64(19)), big.NewInt(int64(2)))f7 := ecc.NewFieldElement(big.NewInt(int64(19)), big.NewInt(int64(7)))fmt.Printf("field element 2 / 7 with order 19 is %v\n", f2.Divide(f7))f46 := ecc.NewFieldElement(big.NewInt(57), big.NewInt(46))fmt.Printf("field element 46 * 46 with order 57: %v\n", f46.Multiply(f46))fmt.Printf("field element 46 ^ (58) is %v\n", f46.Power(big.NewInt(int64(58))))
}

运行上述代码我们得到以下结果：

``go
复制代码
field element 2 / 7 with order 19 is FieldElement{order: 19, num: 3}
field element 46 * 46 with order 57: FieldElement{order: 57, num: 7}
field element 46 ^ (58) is FieldElement{order: 57, num: 7}

    
这正是我们所期望的，这就是字段元素的实现。

http://www.ppmy.cn/news/1544888.html

相关文章

需求分析管理

需求分析管理

软件需求工程是包括创建和维护软件需求文档所必须得一切活动的过程&#xff0c;可以分为需求开发和需求管理两大工作。 需求开发过程&#xff08;四阶段&#xff09; 需求的分析(或者需求开发)过程包括&#xff0c;收集与获取需求&#xff0c;进行需求分析&#xff0c;定义需…
阅读更多...
【react框架之dvajs】dva数据流你可能还不知道的subscriptions隐藏的秘密

【react框架之dvajs】dva数据流你可能还不知道的subscriptions隐藏的秘密

Subscriptions 是一种从 源 获取数据的方法&#xff0c;它来自于 elm。 语义是订阅&#xff0c;用于订阅一个数据源&#xff0c;然后根据条件 dispatch 需要的 action。数据源可以是当前的时间、服务器的 websocket连接、keyboard 输入、geolocation 变化、history 路由变化等等…
阅读更多...
机器学习—前向传播的一般实现

机器学习—前向传播的一般实现

可以写一个函数来实现一个密集的层&#xff0c;那是神经网络的单层&#xff0c;所以定义稠密函数&#xff0c;它将上一层的激活作为输入以及给定层神经元的参数w和b。看下边图片所展示的例子&#xff0c;把所有这些权重向量堆叠成一个矩阵&#xff0c;wnp.array([[1,-3,5][2,4,…
阅读更多...
机器学习，生成式Ai ,LLM大模型，人工智能，他们之间的关系是什么？有什么不同？

机器学习，生成式Ai ,LLM大模型，人工智能，他们之间的关系是什么？有什么不同？

这些概念都是现代计算机科学和人工智能领域的重要组成部分&#xff0c;它们之间既有联系&#xff0c;也有区别。以下是它们的关系和不同之处&#xff1a; 人工智能 (AI) 人工智能是一个广义的概念&#xff0c;指的是计算机系统能够执行通常需要人类智能才能完成的任务&#x…
阅读更多...
MySQL数据库的使用

MySQL数据库的使用

一 关系数据库基本概念 关系数据库是一种使用关系模型来组织和管理数据的数据库。它使用了一种称为表的结构来存储数据&#xff0c;并通过表之间的关系来描述数据之间的联系。每个表由一组行和列组成&#xff0c;每一行代表一个记录&#xff0c;每一列代表一个属性。关系数据…
阅读更多...
Go：接口和反射

Go：接口和反射

接口 定义 在传统的面向对象的语言中&#xff0c;是会存在类和继承的概念的&#xff0c;但是Go并没有 那Go如何实现类似的方法呢&#xff1f;它提供了接口的概念&#xff0c;可以实现很多面向对象的特性 接口定义会实现一组方法集&#xff0c;但是这些方法不包含实现的代码…
阅读更多...
【机器学习导引】ch4-决策树

【机器学习导引】ch4-决策树

基本流程 两个需要解决的问题 属性顺序&#xff1a; 问题&#xff1a;哪些属性在前面&#xff0c;哪些属性在后面&#xff1f;这个问题指的是在处理数据或进行排序时&#xff0c;需要确定属性的排列顺序&#xff0c;以便更好地进行数据处理或分析。 属性选择&#xff1a; 问题…
阅读更多...
C++中，如何找到一个vector中最大的元素

C++中，如何找到一个vector中最大的元素

动态规划中&#xff0c;经常需要找到一个线性表中最大的元素&#xff0c;C 最常用的是vector&#xff0c;而不是 C 中的数组&#xff0c;虽然结构更加复杂&#xff0c;但是用起来更方便。就连 C 创始人 Bjarne Stroustrup 都推荐使用vector&#xff0c;如下是《A Tour of C Thi…
阅读更多...
最新文章

Copyright @ 2022~2023