The objective of this paper is to give a fast square root com- putation method. First the Frobenius mapping is adopted. Then a lot of calculations over an extension field are reduced to that over a proper subfield by the norm computation. In addition a inverse square root algo- rithm and an addition chain are adopted to save the computation cost. All of the above-mentioned steps have been proven to make the pro- posed algorithm much faster than the conventional algorithm. From the table which compares the computation between the conventional and the proposed algorithm, it is clearly shown that the proposed algorithm ac- celerates the square root computation 10 times and 20 times faster than the conventional algorithm in Fp11 and Fp22 respectively. At the same time, the proposed algorithm reduces the computation cost 10 times and 20 times less than the conventional algorithm.
['Wang Feng', 'Yasuyuki Nogami', 'Yoshitaka Morikawa']
A Fast Square Root Computation Using the Frobenius Mapping