Newer
Older
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
package resolver
import (
"fmt"
"math/big"
"git.noc.ruhr-uni-bochum.de/danieljankowski/gomatrix"
)
// LinearDependenciesInGauss tries to resolve linear dependencies in the gaussian
// elimination.
//
// This function is used in order to try to resolve linear dependencies while
// using the function PartialGaussianWithLinearChecking as linearCheck-function.
func LinearDependenciesInGauss(
f *gomatrix.F2,
startRow int,
startCol int,
stopRow int,
stopCol int,
pivotBit int,
) error {
// create a bitmask for the row check
bitmask := big.NewInt(0).SetBit(big.NewInt(0), stopCol-startCol+1, 1)
bitmask = bitmask.Sub(bitmask, big.NewInt(1))
bitmask = bitmask.Lsh(bitmask, uint(startCol))
foundValidRow := false
// iterate through the rows
for index, row := range f.Rows {
// skip all rows, that are processed by the gaussian elimination
if index >= startRow && index <= stopRow {
continue
}
// get the bits to check
bitsToCheck := big.NewInt(0).And(
bitmask,
row,
)
// if the bits are 0...
if bitsToCheck.Cmp(big.NewInt(0)) == 0 {
// ...skip the row
continue
}
// swap the rows
f.SwapRows(pivotBit-1, index)
foundValidRow = true
// exit the loop
break
}
if !foundValidRow {
return fmt.Errorf("cannot resolve linear dependency")
}
for i := startCol; i < pivotBit; i++ {
if f.Rows[pivotBit-startCol].Bit(i) == uint(0) {
continue
}
fmt.Printf("%d xor %d\n", pivotBit-startCol, startRow+i-startCol)
f.Rows[pivotBit-startCol].Xor(
f.Rows[pivotBit-startCol],
f.Rows[startRow+i-startCol],
)
}
return nil
}