Lattice Basis Reduction

Two-Dimensional Lattices 31

The first iteration calc ulates

m =



v

2

·v

1

v

1

·v

1



=



−256

203



≈ ⌈−1.261⌋ = −1.

We now set

v

2

← v

2

+ v

1

= [ 9, 19, −13], |v

2

| ≈ 24.72.

Since |v

2

| < |v

1

| we interchange the vectors; we now have

v

1

= [ 9, 19 , −13], v

2

= [ −49, −70, 35 ].

The second iteration calculates

m =



v

2

· v

1

v

1

· v

1



=



−2226

611



≈ ⌈−3.643⌋ = −4.

We now set

v

2

← v

2

+ 4v

1

= [ −13, 6, −17], |v

2

| ≈ 22.23.

Since |v

2

| < |v

1

| we interchange the vectors; we now have

v

1

= [ −13, 6, −17], v

2

= [ 9, 19, −13].

The third iteration calculates

m =



v

2

·v

1

v

1

·v

1



=



109

247



≈ ⌈0.44 13⌋ = 0.

Thus v

2

does not change, and the algorithm terminates.

2.3 Vall´ee’s analysis of the Gaussian algorithm

In this