Rational functions with partial quotients of small degree in their continued fraction expansion. (English) Zbl 0624.12011

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.


11T06 Polynomials over finite fields
11A55 Continued fractions
11K45 Pseudo-random numbers; Monte Carlo methods
65C10 Random number generation in numerical analysis
Full Text: DOI EuDML


[1] Artin, E.: Quadratische K?rper im Gebiet der h?heren Kongruenzen. I. Math. Z.19, 153-206 (1924). · JFM 50.0107.01 · doi:10.1007/BF01181074
[2] Baum, L. E., Sweet, M. M.: Continued fractions of algebraic power series in characteristic 2. Ann. Math.103, 593-610 (1976). · Zbl 0322.10018 · doi:10.2307/1970953
[3] Baum, L. E., Sweet, M. M.: Badly approximable power series in characteristic 2. Ann. Math.105, 573-580 (1977). · Zbl 0352.10017 · doi:10.2307/1970925
[4] De Mathan, B.: Approximations diophantiennes dans un corps local. Bull. Soc. Math. France Suppl. M?m.21 (1970). · Zbl 0221.10037
[5] Knuth, D. E.: The Art of Computer Programming, vol 2: Seminumerical Algorithms. 2nd ed. Reading: Addison-Wesley. 1981. · Zbl 0477.65002
[6] Lidl, R., Niederreiter, H.: Finite Fields. Reading: Addison-Wesley. 1983. · Zbl 0554.12010
[7] Niederreiter, H.: The performance ofk-step pseudorandom number generators under the uniformity test. SIAM J. Sci. Statist. Computing5, 798-810 (1984). · Zbl 0557.65005 · doi:10.1137/0905057
[8] Niederreiter, H.: Pseudozufallszahlen und die Theorie der Gleichverteilung. Sitzungsber. ?sterr. Akad. Wiss. Math.-Naturwiss. Kl.195, 109-138 (1986). · Zbl 0616.10040
[9] Niedereiter, H.: Dyadic fractions with small partial quotients. Mh. Math.101, 309-315 (1986). · Zbl 0584.10004 · doi:10.1007/BF01559394
[10] Tausworthe, R. C.: Random numbers generated by linear recurrence modulo two. Math. Comp.19, 201-209 (1965). · Zbl 0137.34804 · doi:10.1090/S0025-5718-1965-0184406-1
[11] Zaremba, S. K.: La m?thode des ?bons treillis? pour le calcul des int?grales multiples. In: Applications of Number Theory to Numerical Analysis (S. K. Zaremba, ed.), pp. 39-119. New York: Academic Press. 1972.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.