$? (e1,e2,...,en)Î{0,1} | n |
|
ei× ai=c |
" iÎ[2,n] bi> |
|
bj |
L=× b1+× b1+...+× bn= |
ì í î |
|
ri× bi : (r1,r2...,rn)În |
ü ý þ |
<(a1,a2,...,an),(b1,b2,...,bn)>= |
|
ai× bi |
Algorithme 1 LLL(b1,b2,...,bn)
1 b1*¬b1, B1¬<b1*,b1*>
2 pour i¬2 à n faire
3 bi*¬bi
4 pour j¬1 à i-1 faire
5 µi,j¬<bi,bj*>/Bj, bi*¬bi*-µi,jbj*
6 Bi¬<bi*,bi*>
7 k¬2
8 si |µk,k-1|>1/2 alors
9 r¬ëµk,k-1ù, bk¬bk-rbk-1
10 pour j¬1 à k-2 faire
11 µk,j¬µk,j-rµk-1,j
12 µk,k-1¬µk,k-1-r
13 si Bk<(3/4-µk,k-12)Bk-1 alors
14 µ¬µk,k-1, B¬Bk+µ2Bk-1, µk,k-1¬µ Bk-1/B, Bk¬Bk-1Bk/B, Bk-1¬B
15 échanger les vecteurs bk et bk-1
16 si k>2 alors
17 pour j¬1 à k-2 faire
18 échanger µk,j et µk-1,j
19 pour i¬k+1 à n faire
20 t¬µi,k, µi,k¬µi,k-1-µ t, µi,k-1¬t+µk,k-1µi,k
21 k¬max(2,k-1)
22 retourner à l'étape 8
23 sinon
24 pour l¬k-2 à 1 faire
25 si |µk,l|>1/2 alors
26 r¬ëµk,lù, bk¬bk-rbl
27 pour j¬1 à l-1 faire
28 µk,j¬µk,j-rµl,j
29 µk,l¬µk,l-r
30 k¬k+1
31 si k£ n alors
32 retourner à l'étape 8
33 sinon
34 retourner(b1,b2,...,bn) comme base réduite
Figure 1 : Algorithme LLL permettant de réduire la base (b1,b2,...,bn)
æ ç ç ç ç ç ç ç ç è |
|
ö ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ø |
|
mi× bi-bn+1= | ( | m1,m2,...,mn,0 | ) |
æ ç ç ç ç ç ç ç è |
|
ö ÷ ÷ ÷ ÷ ÷ ÷ ÷ ø |
æ ç ç ç ç ç ç ç è |
|
ö ÷ ÷ ÷ ÷ ÷ ÷ ÷ ø |
æ ç ç ç ç ç ç ç ç ç ç ç è |
|
ö ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ø |
Ce document a été traduit de LATEX par HEVEA.