Advertisement
Published in:
2006 | OriginalPaper | Chapter
A High-Speed Square Root Algorithm in Extension Fields
Authors : Hidehiro Katou, Feng Wang, Yasuyuki Nogami, Yoshitaka Morikawa
Published in: Information Security and Cryptology – ICISC 2006
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
A square root (SQRT) algorithm in
GF
(
p
m
) (
m
=
r
0
r
1
⋯
r
n
− − 1
2
d
,
r
i
: odd prime,
d
> 0: integer) is proposed in this paper. First, the Tonelli-Shanks algorithm is modified to compute the inverse SQRT in
$GF(p^{2^d})$
, where most of the computations are performed in the corresponding subfields
$GF{(p^{2^{i}})}$
for 0 ≤
i
≤
d
–1. Then the Frobenius mappings with an addition chain are adopted for the proposed SQRT algorithm, in which a lot of computations in a given extension field
GF
(
p
m
) are also reduce to those in a proper subfield by the norm computations. Those reductions of the field degree increase efficiency in the SQRT implementation. More specifically the Tonelli-Shanks algorithm and the proposed algorithm in
GF
(
p
22
),
GF
(
p
44
) and
GF
(
p
88
) were implemented on a Pentium4 (2.6 GHz) computer using the C++ programming language. The computer simulations showed that, on average, the proposed algorithm accelerates the SQRT computation by 25 times in
GF
(
p
22
), by 45 times in
GF
(
p
44
), and by 70 times in
GF
(
p
88
), compared to the Tonelli-Shanks algorithm, which is supported by the evaluation of the number of computations.