Arithmetic of finite fields
type: Item
instance of: scholarly article
title: Arithmetic of finite fields
zbMATH Open document ID: 0492.12009
DOI: 10.1016/0020-0190(82)90130-2
author: Ben-Zion Chor
published in: Information Processing Letters
publication date: 1982-01-01T00:00:00Z
review text: Let \(p\) be a fixed prime and \(n=m_1m_2\cdots m_l\) be a factorization of a positive integer \(n\) such that \(m_1\ge m_2\ge \ldots\ge m_l\ge 1\). The author proposes an algorithm for realizing the finite field \(\mathrm{GF}(p^n)\) with \(p^n\) elements, by the chain of field extensions \[ \mathrm{GF}(p)\subseteq \mathrm{GF}(p^{m_1})\subseteq \mathrm{GF}(p^{m_1m_2}) \subseteq \ldots\subseteq \mathrm{GF}(p^{m_1m_2\cdots m_l}) = \mathrm{GF}(p^n). \] The algorithm requires for each \(i\), \(1\le i\le l\), to find an irreducible polynomial of degree \(m_i\) in \(\mathrm{GF}(p^{m_1m_2\cdots m_{l-1}})[x] \) \((m_1m_2\cdots m_{l-1} = 1\) if \(i = 1)\). The author claims that his method, on appealing in each step of extensions to the best algorithm known so far finding irreducible polynomials over finite fields, can improve the run-time of constructing \(\mathrm{GF}(p^n)\) with usual procedure, by an \(n^{1/2}\) factor for most (non-prime) integers \(n\).
reviewed by: Saburô Uchiyama
Mathematics Subject Classification ID: 11T06
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 11T30
zbMATH DE Number: 3773730
zbMATH Keywords: algorithm
zbMATH Keywords: irreducible polynomials over finite fields
zbMATH Keywords: run-time
MaRDI profile type: Publication
full work available at URL: 0020-0190(82)90130-2
OpenAlex ID: W2019303997
cites work: Analysis of a simple factorization algorithm
cites work: Probabilistic Algorithms in Finite Fields
description: scientific article; zbMATH DE number 3773730