Cryptography Reference
In-Depth Information
M
0
=A
k
F
0
;
(start of initial batch)
M
1
=A
k1
F
1
;
.
M
kj1
=A
j+1
F
kj1
;
M
kj
=A
j
F
kj
;
(start of intermediate batch 0)
M
kj+1
=A
j
F
kj+1
;
.
M
kj+q1
=A
j
F
kj+q1
;
M
kj+q
=A
j1
EF
kj
;
(start of intermediate batch 1)
M
kj+q+1
=A
j1
EF
kj+1
;
.
M
kj+2q1
=A
j1
EF
kj+q1
;
.
.
M
kj+(j1)q
=AE
j1
F
kj
;
(start of intermediate batchj 1)
M
kj+(j1)q+1
=AE
j1
F
kj+1
;
.
M
kj+jq1
=AE
j1
F
kj+q1
;
M
kj+jq
=E
j
F
kj
;
(start of final batch)
M
kj+jq+1
=E
j
F
kj+1
;
.
M
`1
=E
j
F
`qj1
Fig.4.1.Polynomials constructed in the new algorithm. There is an initial batch of
lengthkj;jintermediate batches, each of lengthq; and a nal batch of length
`(q1)jk. If`= (q1)j+kandj>0 then the last polynomial isAE
j1
F
kj+q1
;
if`= (q 1)j+kandj= 0 then the last polynomial isAF
k1
.
k(nw) + jw; but the image of Q has degree below k(nw) + jw, so it must
be 0 as desired.
Notes on parameter sele
ction. Assume
that t+1 n
0
where n
0
= n(q1)=q.
As before write J
0
= n
0
p
n
0
(n
0
t 1).
Suitable j;k;` exist with ` 2 O(qnt) for each positive integer w < J
0
. For
example, the integers j = 2w(t + 1), k = 2(q 1)(n w)(t + 1), and ` =
2(q1)n(t+ 1) have (1(t+ 1)=n)(11=`) = 1(t+ 1)=n1=`+ 1=2(q1)n
2
