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
|
// 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,
}
}
|
