Cryptography Reference
In-Depth Information
Table 2.1
Expected complexity of basic algorithms for numbers of size relevant for
cryptography and related applications. The symbol
∗
indicates that better asymptotic
complexities are known.
Computational problem
Expected complexity for cryptography
O
(
m
2
)or
O
(
m
1
.
585
) bit operations
Multiplication of
m
-bit integers,
M
(
m
)
Compute
a/n
,a
(mod
n
)
O
((log(
|
a
|
)
−
log(
n
)) log(
n
))
or
O
(
M
(log(
|
a
|
)) bit operations
Compute
√
|
a
|
O
(
M
(log(
|
a
|
))) bit operations
O
(
m
2
)or
O
(
M
(
m
) log(
m
)) bit operations
Extended gcd(
a,b
)where
a
and
b
are
m
-bit
integers
Legendre/Jacobi symbol (
n
),
|
a
|
<n
O
(log(
n
)
2
)or
O
(
M
(log(
n
)) log(log(
n
))) bit operations
Multiplication modulo
n
O
(
M
(log(
n
))) bit operations
Inversion modulo
n
O
(log(
n
)
2
)or
O
(
M
(log(
n
)) log(
n
)) bit
operations
Compute
g
m
(mod
n
)
O
(log(
m
)
M
(log(
n
))) bit operations
Compute square roots in
F
q
(
q
odd)
O
(log(
q
)
M
(log(
q
))) bit operations
Multiplication of two-degree
d
polys in
k
[
x
]
O
(
M
(
d
))
k
-multiplications
Multiplication of two-degree
d
polys in
F
q
[
x
],
O
(
M
(
d
log(
dq
))) bit operations
M
(
d,q
)
Inversion in
k
[
x
]
/
(
F
(
x
)) where deg(
F
(
x
))
=
d
(
d
2
)or
O
(
M
(
d
)log(
d
))
k
-operations
Multiplication in
F
q
m
O
(
M
(
m
)) operations in
F
q
∗
Evaluate a degree
d
polynomial at
α
∈ k
O
(
d
)
k
-operations
O
(log(
d
) log(
q
)
d
2
)
F
q
-operations
∗
Find all roots in
F
q
of a degree
d
polynomial in
F
q
[
x
]
Find one root in
F
q
of a degree
d
polynomial in
F
q
[
x
]
O
(log(
dq
)
M
(
d,q
)) bit operations
Determine if degree
d
poly over
F
q
is irreducible
O
(
d
3
log(
q
))
F
q
-operations
∗
Factor degree
d
polynomial over
F
q
O
(
d
3
log(
q
))
F
q
-operations
∗
Construct polynomial basis for
F
q
m
O
(
m
4
log(
q
))
F
q
-operations
∗
Construct normal basis for
F
q
m
given a poly basis
O
(
m
3
log
q
(
m
))
F
q
-operations
∗
Solve quadratic equations in
F
q
O
(log(
q
)
4
) bit operations
∗
O
(
m
3
)
F
q
-operations
Compute the minimal poly over
F
q
of
α
∈ F
q
m
F
q
m
O
(
m
3
)
F
q
-operations
Compute an isomorphism between repns of
Compute order of
α
∈ F
q
given factorisation of
q
−
O
(log(
q
) log(log(
q
)))
F
q
-multiplications
1
Compute primitive root in
F
q
given factorisation
O
(log(
q
) log(log(
q
)))
F
q
-multiplications
of
q
−
1
Compute
f
(
α
j
)
∈ k
for
f
∈ k
[
x
]ofdegree
n
and
α
1
,...,α
n
∈ k
O
(
M
(
n
) log(
n
))
k
-multiplications
