Lattice Basis Reduction

108 Lattice Basis Reduction

• Procedure reduce(k, p):

If |µ

kp

| >

1

2

then

– Set r ← ⌈µ

kp

⌋.

– Set y

k

← y

k

− ry

p

.

– For j = 1, 2, . . . , p−1 do: Set µ

kj

← µ

kj

− rµ

pj

.

– Set µ

kp

← µ

kp

− r.

• Procedure exchange(k, ℓ):

– Set µ

k,k−1

← νγ

∗

k−1

/δ.

– Set γ

∗

k

← γ

∗

k−1

γ

∗

k

/δ.

– For j = k+1, . . . , ℓ do:

Set



µ

j,k−1

µ

jk



←



1 µ

k,k−1

0 1



0 1

1 −ν



µ

j,k−1

µ

jk



.

FIGURE 6.1

Reduce and exchange procedures for the MLLL algorithm

The first modification occurs at (P2) where row 2 is reduced using row 1:

Y =





6

−2

15





The next modification occ urs at (P5) where rows 1 and 2 are exchanged:

Y =





−2

6

15





At (P2) row 2 is re duced using row 1:

Y =





−2

0

15





A zero row has appeared and so (P4) swaps rows 2