• Shk, ti 0 ≤ k ≤ s 0 ≤ t ≤ p(|w|)
Shk, ti
Shk, ti = 1 ⇔ HMT M t q
k
(s + 1) · (p(|w|) + 1) ∈ O(p(|w|)).
• Hhi, ti
0 ≤ i ≤ p(|w|) 0 ≤ t ≤ p (|w|)
Hhi, ti
Hhi, ti = 1 ⇔ M t
i
(p(|w|) + 1)
2
∈ O((p(|w|))
2
).
t
(X
j
0
X
j
1
. . . X
j
i−1
q
r
X
j
i
. . . X
j
p(|w|)
)
• Ch0, j
0
, ti = Ch1, j
1
, ti = . . . = Chp(|w |), j
p(|w|)
, ti = 1 Chk, l, ti = 0
• Hhi, ti = 1 Hhj, ti = 0 j ∈ {0, 1, . . . , p(|w|)}, j 6= i
• Shr, ti = 1 Shl, ti = 0 l ∈ {0, 1, . . . , s}, l 6= r
w
t
M p(|w|)
w
Sh1, 3i = Sh3, 3i = Sh7, 3i = 1 Ch2, 1, 3i = Ch2, 2, 3i = 1
3
q
1
q
3
q
7
X
1
X
2
t = 3
(p(|w|) + 2) × (p(|w |) + 1).
(i, j) 0 ≤ i, j ≤ p(|w|)