Cryptography Reference
In-Depth Information
preliminary \squarefree factorization" of the polynomial, but that factorization
has essentially linear cost; see [
29
, Theorem 14.23].
In the case of linear factors (i.e., roots) the entire factorization procedure uses
`
2+o(1)
d(lg d)
2+o(1)
bit operations for `-coecient polynomials with d-bit integer
coecients; see [
29
, Theorem 15.21]. There has been a tremendous amount of
research on algorithms for the rst step, factoring in (Z=p)[y], but rather naive
algorithms are adequate if ` is much smaller than d and if one allows random-
ization. There has also been a tremendous amount of research on algorithms to
handle higher-degree factors, but for this paper linear factors are adequate.
One can obtain essentially the same speed by computing approximate roots in
R with an analogous Newton iteration, but working with the p-adic numbers Q
p
is simpler because it avoids roundoff error. There are still a few technical details
that require attention: one must avoid primes p that divide denominators of
the original coecients; one must also avoid primes p that create new squared
factors. There are not many bad choices of p; see [
29
, Lemma 15.1].
Zassenhaus's method is not limited to the rational number eld Q. Replacing
Q by the rational function field F
q
m
(x), and replacing the small prime p of
Z by a small irreducible element p of F
q
m
[x], produces a factorization method
for F
q
m
(x)[y]; see, e.g., [
29
, Theorem 15.23]. Squarefree factorization becomes
slightly more complicated, as discussed in [
29
, page 447], but is still fast. The
cost for the initial factorization modulo p is `
2+o(1)
(lg q
m
)
1+o(1)
by [
29
, Theorem
14.14]. There are subquadratic factorization algorithms in the literature, but this
refinement is not necessary for this paper.
The root-nding conclusion that matters for this paper|the polynomial ana-
logue of [
29
, Theorem 15.21]|is the following. There is a standard algorithm
that, given a nonzero polynomial Q 2 F
q
m
(x)[y], finds all y-roots of Q. If Q is an
`-coecient polynomial (in y), each coecient in turn being a d-coecient poly-
nomial (in x), then the entire procedure costs `
2+o(1)
((lg q
m
)
1+o(1)
+d(lg d)
2+o(1)
).
Note that this cost bound is influenced by lg q
m
, the number of bits of the parent
eld F
q
m
; one needs to put limits on q
m
not merely to control the translation
from cost into bit operations, but also to control the cost of factorization.
Correcting Nearlyn
p
n(n
t
1) Errors
3
This section states a simple high-speed list-decoding algorithm that corrects
errors up to the big-field Johnson bound. The algorithm in the next section is
more general and more powerful, correcting more errors; but the algorithm in
this section is slightly simpler, and the reader is encouraged to read it first.
Parameters. This algorithm has three parameters: a positive integer w n,
the number of errors to be corrected; an integer k 0; and an integer ` k.
The algorithm assumes that t + 1 n and that these parameters satisfy
n
k(k + 1)
2
+ (nt 1)
`(` 1)
2
< `k(nw);
i.e., (1 (t + 1)=n)(1 1=`) < (1 w=n)
2
(1 w=nk=`)
2
k=`
2
.
