Efficient Computation of Roots in Finite Fields期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

Efficient Computation of Roots in Finite Fields

Authors:	Paulo S L M Barreto José Felipe Voloch

Institution:	1. Laboratório de Arquitetura e Redes de Computadores (LARC), Escola Politécnica, Universidade de S?o Paulo, Brazil 2. Department of Mathematics, University of Texas, Austin, TX, 78712, USA

Abstract:	We present an algorithm to compute rth roots in $\mathbb{F}_{q^m}We present an algorithm to compute rth roots in $\mathbb{F}_{q^m}$ with complexity ?(log m + r log q) m log q] if (m,q) = 1 and either (q(q−1),r) = 1 or r\|(q−1) and ((q−1)/r,r) = 1. This compares well to previously known algorithms, which need O(r m³ log³ q) steps. Paulo S. L. M. Barreto: Supported by Scopus Tecnologia S. A. José Felipe Voloch: Supported by NSA grant MDA904-03-1-0117.

Keywords:	finite fields root computation efficient algorithms
本文献已被 SpringerLink 等数据库收录！