# zbMATH — the first resource for mathematics

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.

##### MSC:
 11T06 Polynomials over finite fields 11A55 Continued fractions 11K45 Pseudo-random numbers; Monte Carlo methods 65C10 Random number generation in numerical analysis
Full Text:
##### References:
  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  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  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  De Mathan, B.: Approximations diophantiennes dans un corps local. Bull. Soc. Math. France Suppl. M?m.21 (1970). · Zbl 0221.10037  Knuth, D. E.: The Art of Computer Programming, vol 2: Seminumerical Algorithms. 2nd ed. Reading: Addison-Wesley. 1981. · Zbl 0477.65002  Lidl, R., Niederreiter, H.: Finite Fields. Reading: Addison-Wesley. 1983. · Zbl 0554.12010  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  Niederreiter, H.: Pseudozufallszahlen und die Theorie der Gleichverteilung. Sitzungsber. ?sterr. Akad. Wiss. Math.-Naturwiss. Kl.195, 109-138 (1986). · Zbl 0616.10040  Niedereiter, H.: Dyadic fractions with small partial quotients. Mh. Math.101, 309-315 (1986). · Zbl 0584.10004 · doi:10.1007/BF01559394  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  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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.