1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
// Copyright © 2021 siddharth ravikumar <s@ricketyspace.net>
// SPDX-License-Identifier: ISC
package lib
import (
"math/big"
)
type GCDResult struct {
Gcd *big.Int
X *big.Int // Bézout coefficient 'x'
Y *big.Int // Bézout coefficient 'y'
}
// Copy b to a.
func biCopy(a, b *big.Int) *big.Int {
a.SetBytes(b.Bytes())
if b.Sign() == -1 {
a.Mul(a, big.NewInt(-1))
}
return a
}
// Extended Euclidian.
func egcd(a, b *big.Int) GCDResult {
// Initialize.
s0 := big.NewInt(1)
s1 := big.NewInt(0)
r0 := biCopy(big.NewInt(0), a)
r1 := biCopy(big.NewInt(0), b)
for r1.Cmp(big.NewInt(0)) != 0 {
q := big.NewInt(0)
q.Div(r0, r1)
tr := big.NewInt(0)
tr = tr.Mul(q, r1)
tr = tr.Sub(r0, tr)
biCopy(r0, r1)
biCopy(r1, tr)
tr = big.NewInt(0)
tr = tr.Mul(q, s1)
tr = tr.Sub(s0, tr)
biCopy(s0, s1)
biCopy(s1, tr)
}
x := biCopy(big.NewInt(0), s0)
y := big.NewInt(0)
if b.Cmp(big.NewInt(0)) != 0 {
y = y.Mul(s0, a)
y = y.Sub(r0, y)
y = y.Div(y, b)
}
return GCDResult{
Gcd: biCopy(big.NewInt(0), r0),
X: x,
Y: y,
}
}
func invmod(a, n *big.Int) (*big.Int, error) {
// Initialize.
t0 := big.NewInt(0)
t1 := big.NewInt(1)
r0 := biCopy(big.NewInt(0), n)
r1 := biCopy(big.NewInt(0), a)
for r1.Cmp(big.NewInt(0)) != 0 {
q := big.NewInt(0)
q.Div(r0, r1)
tt := big.NewInt(0)
tt = tt.Mul(q, t1)
tt = tt.Sub(t0, tt)
biCopy(t0, t1)
biCopy(t1, tt)
tr := big.NewInt(0)
tr = tr.Mul(q, r1)
tr = tr.Sub(r0, tr)
biCopy(r0, r1)
biCopy(r1, tr)
}
if r0.Cmp(big.NewInt(1)) > 0 {
return nil, CPError{"not invertible"}
}
if t0.Cmp(big.NewInt(0)) < 0 {
t0.Add(t0, n)
}
return t0, nil
}
|
