Rational functions with partial quotients of small degree in their continued fraction expansion
type: Item
instance of: scholarly article
title: Rational functions with partial quotients of small degree in their continued fraction expansion
zbMATH Open document ID: 0624.12011
DOI: 10.1007/BF01318069
author: Harald Niederreiter
published in: Monatshefte für Mathematik
publication date: 1987-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/178331
review text: For a rational function \(f/g=f(x)/g(x)\) over a field \(F\) with \(\gcd (f,g)=1\) and \(\deg(g)\geq 1\) let \(K(f/g)\) be the maximum degree of the partial quotients in the continued fraction expansion of \(f/g\). For \(f\in F[x]\) with \(\deg (f)=k\geq 1\) and \(f(0)\neq 0\) put \(L(f)=K(f(x)/x^k)\). It is shown by an explicit construction that for every integer \(b\) with \(1\leq b\leq k\) there exists an \(f\) with \(L(f)=b\). If \(F=\mathbb F_2\), the binary field, then for every \(k\) there is exactly one \(f\in\mathbb F_2[x]\) with \(\deg (f)=k\), \(f(0)\neq 0\), and \(L(f)=1\). If \(\mathbb F_q\) is the finite field with \(q\) elements and \(g\in\mathbb F_q[x]\) is monic of degree \(k\geq 1\), then there exists a monic irreducible \(f\in\mathbb F_q[x]\) with \(\deg (f)=k\), \(\gcd (f,g)=1\), and \(K(f/g)<2+2(\log k)/\log q,\) where the case \(q=k=2\) and \(g(x)=x^2+x+1\) is excluded. An analogous existence theorem is also shown for primitive polynomials over finite fields. These results have applications to pseudorandom number generation.
Mathematics Subject Classification ID: 11T06
Mathematics Subject Classification ID: 11A55
Mathematics Subject Classification ID: 11K45
Mathematics Subject Classification ID: 65C10
zbMATH DE Number: 4012762
zbMATH Keywords: rational function
zbMATH Keywords: partial quotients
zbMATH Keywords: continued fraction expansion
zbMATH Keywords: polynomials over finite fields
zbMATH Keywords: pseudorandom number generation
MaRDI profile type: Publication
cites work: Badly approximable power series in characteristic 2
cites work: Q5625271
cites work: Q3935355
cites work: Q3216750
cites work: The Performance of k-Step Pseudorandom Number Generators under the Uniformity Test
cites work: Q4724719
cites work: Dyadic fractions with small partial quotients
cites work: Random Numbers Generated by Linear Recurrence Modulo Two
OpenAlex ID: W2055072026
description: scientific article; zbMATH DE number 4012762