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
101
102
|
// Copyright © 2021 siddharth ravikumar <s@ricketyspace.net>
// SPDX-License-Identifier: ISC
package lib
import (
"math/big"
"testing"
)
func TestEGCD(t *testing.T) {
a := big.NewInt(128)
b := big.NewInt(96)
r := egcd(a, b)
if r.Gcd.Cmp(big.NewInt(32)) != 0 {
t.Errorf("gcd(128, 96) != 32")
}
if r.X.Cmp(big.NewInt(1)) != 0 || r.Y.Cmp(big.NewInt(-1)) != 0 {
t.Errorf("bézout_coef(128, 96) != {1,-1}")
}
a = big.NewInt(360)
b = big.NewInt(210)
r = egcd(a, b)
if r.Gcd.Cmp(big.NewInt(30)) != 0 {
t.Errorf("gcd(360, 210) != 30")
}
if r.X.Cmp(big.NewInt(3)) != 0 || r.Y.Cmp(big.NewInt(-5)) != 0 {
t.Errorf("bézout_coef(360, 210) != {3,-5}")
}
a = big.NewInt(108)
b = big.NewInt(144)
r = egcd(a, b)
if r.Gcd.Cmp(big.NewInt(36)) != 0 {
t.Errorf("gcd(108, 144) != 36")
}
if r.X.Cmp(big.NewInt(-1)) != 0 || r.Y.Cmp(big.NewInt(1)) != 0 {
t.Errorf("bézout_coef(108, 144) != {-1,1}")
}
a = big.NewInt(240)
b = big.NewInt(46)
r = egcd(a, b)
if r.Gcd.Cmp(big.NewInt(2)) != 0 {
t.Errorf("gcd(240, 46) != 2")
}
if r.X.Cmp(big.NewInt(-9)) != 0 || r.Y.Cmp(big.NewInt(47)) != 0 {
t.Errorf("bézout_coef(240, 46) != {-9,47}")
}
}
func TestInvMod(t *testing.T) {
a := big.NewInt(17)
b := big.NewInt(3120)
e := big.NewInt(2753) // Expected inverse.
i, err := invmod(a, b)
if err != nil {
t.Errorf("invmod(%v,%v) failed: %v", a, b, err)
return
}
if i.Cmp(e) != 0 {
t.Errorf("gcd(%v,%v) != %v", a, b, e)
}
a = big.NewInt(240)
b = big.NewInt(47)
e = big.NewInt(19) // Expected inverse.
i, err = invmod(a, b)
if err != nil {
t.Errorf("invmod(%v,%v) failed: %v", a, b, err)
return
}
if i.Cmp(e) != 0 {
t.Errorf("gcd(%v,%v) != %v", a, b, e)
}
a = big.NewInt(11)
b = big.NewInt(26)
e = big.NewInt(19) // Expected inverse.
i, err = invmod(a, b)
if err != nil {
t.Errorf("invmod(%v,%v) failed: %v", a, b, err)
return
}
if i.Cmp(e) != 0 {
t.Errorf("gcd(%v,%v) != %v", a, b, e)
}
a = big.NewInt(3)
b = big.NewInt(7)
e = big.NewInt(5) // Expected inverse.
i, err = invmod(a, b)
if err != nil {
t.Errorf("invmod(%v,%v) failed: %v", a, b, err)
return
}
if i.Cmp(e) != 0 {
t.Errorf("gcd(%v,%v) != %v", a, b, e)
}
}
|
