Cryptography Reference
In-Depth Information
span
{
v
1
,...,
v
n
}
Span of a set of vectors over
R
rank(
A
)
Rank of a matrix
A
x
Closest integer to
x
,
1
/
2
=
1
B
Basis matrix for a lattice
L
Lattice
b
i
Gram-Schmidt vector arising from ordered basis
{
b
1
,...,
b
n
}
b
i
,
b
j
b
j
,
b
j
µ
i,j
Gram-Schmidt coefficient
/
b
i
2
B
i
λ
i
Successive minima of a lattice
det(
L
)
Determinant of a lattice
γ
n
Hermite's constant
X
Bound on the size of the entries in the basis matrix
L
B
(
i
)
i
×
m
matrix formed by the first
i
rows of
B
d
i
Determinant of matrix of
b
j
,
b
k
for 1
≤
j,k
≤
i
D
Product of
d
i
P
1
/
2
(
B
)
Fundamental domain (parallelepiped) for lattice basis
B
F
(
x
),
F
(
x,y
)
Polynomial with “small” root
G
(
x
)
,G
(
x,y
)
Polynomial with “small” root in common with
F
(
x
) (resp.,
F
(
x,y
))
X,Y
Bounds on size of root in Coppersmith's method
b
F
Coefficient vector of polynomial
F
R
(
F,G
)
,R
x
(
F
(
x
)
,G
(
x
))
Resultant of polynomials
W
Bound in Coppersmith's method
P,R
Constants in noisy Chinese remaindering
−
amp(
x
)
The amplitude gcd(
P,x
R
) in noisy Chinese remaindering
16.1 Basic notions on lattices
m
. We write all vectors as
rows
; be warned that
many topics and papers write lattice vectors as columns. We denote by
A lattice is a subset of the vector space
R
v
the Euclidean
m
; though some statements also hold for other norms.
norm of a vector
v
∈ R
m
Definition 16.1.1
Let
{
b
1
,...,
b
n
}
be a linearly independent set of (row) vectors in
R
(
m
≥
n
). The
lattice
generated by
{
b
1
,...,
b
n
}
is the set
n
L
=
l
i
b
i
:
l
i
∈ Z
i
=
1
of
integer
linear combinations of the
b
i
. The vectors
b
1
,...,
b
n
are called a
lattice basis
.
The
lattice rank
is
n
and the
lattice dimension
is
m
.If
n
=
m
then
L
is said to be a
full
rank lattice
.
