glatl/Lagrange.go at main · satoshin-des/glatl · GitHub

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
package glatl

import "math"

// Lagrange computes Lagrange reduced basis
//
// panic if dimension of b is not 2
//
// J- L. Lagrange. Recherches d'arithmetique. (1773)
func Lagrange(b Lattice) {
	if b.NumRows != 2 {
		panic("2 dimensional lattice only can be Lagrange-reduced")
	}

	var normTemp1, normTemp2, v int64 = 0, 0, 0

	for j := 0; j < b.NumCols; j++ {
		normTemp1 += b.Basis[0][j] * b.Basis[0][j]
		normTemp2 += b.Basis[1][j] * b.Basis[1][j]
	}

	if normTemp1 > normTemp2 {
		for j := 0; j < b.NumCols; j++ {
			v = b.Basis[0][j]
			b.Basis[0][j] = b.Basis[1][j]
			b.Basis[1][j] = v
		}
	}

	for {
		normTemp1 = 0
		normTemp2 = 0
		for j := 0; j < b.NumCols; j++ {
			normTemp1 += b.Basis[0][j] * b.Basis[1][j]
			normTemp2 += b.Basis[0][j] * b.Basis[0][j]
		}

		for j := 0; j < b.NumCols; j++ {
			v = b.Basis[1][j] - int64(math.Round(float64(normTemp1)/float64(normTemp2)))*b.Basis[0][j]
			b.Basis[1][j] = b.Basis[0][j]
			b.Basis[0][j] = v
		}

		normTemp1 = 0
		normTemp2 = 0
		for j := 0; j < b.NumCols; j++ {
			normTemp1 += b.Basis[0][j] * b.Basis[0][j]
			normTemp2 += b.Basis[1][j] * b.Basis[1][j]
		}

		if normTemp1 >= normTemp2 {
			for j := 0; j < b.NumCols; j++ {
				v = b.Basis[0][j]
				b.Basis[0][j] = b.Basis[1][j]
				b.Basis[1][j] = v
			}
			break
		}
	}
}