## Abstract

This paper focuses on developing a square root (SQRT) algorithm in finite fields GF(p^{2d})(d ≥ 0). Examining the Smart algorithm, a well-known SQRT algorithm, we can see that there is some computation overlap between the Smart algorithm and the quadratic residue (QR) test, which must be implemented before a SQRT computation. It makes the Smart algorithm inefficient. In this paper, we propose a new QR test and a new SQRT algorithm in GF(p^{2d}), in which not only there is no computation overlap, but also most of computations required for the proposed SQRT algorithm in GF(p^{2d}) can be implemented in the corresponding subfields GF(p^{2d-l}) for 1 ≤ i ≤ d, which yields many reductions in the computational time and complexity. The computer simulation also shows that the proposed SQRT algorithm is much faster than the Smart algorithm.

Original language | English |
---|---|

Pages (from-to) | 2792-2799 |

Number of pages | 8 |

Journal | IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences |

Volume | E88-A |

Issue number | 10 |

DOIs | |

Publication status | Published - Oct 2005 |

## Keywords

- Finite fields
- Quadratic residue
- Square root

## ASJC Scopus subject areas

- Signal Processing
- Computer Graphics and Computer-Aided Design
- Electrical and Electronic Engineering
- Applied Mathematics