Rational functions with partial quotients of small degree in their continued fraction expansion |
| |
Authors: | Harald Niederreiter |
| |
Institution: | (1) Kommission für Mathematik, Österreichische Akademie der Wissenschaften, Dr. Ignaz-Seipel-Platz 2, A-1010 Wien, Austria |
| |
Abstract: | For a rational functionf/g=f(x)/g(x) over a fieldF with ged (f,g)=1 and deg (g) 1 letK(f/g) be the maximum degree of the partial quotients in the continued fraction expansion off/. Forf Fx] with deg (f)=k 1 andf(O) O putL(f)=K(f(x)/x
k
). It is shown by an explicit construction that for every integerb with 1 b k there exists anf withL(f)=b. IfF=F
2, the binary field, then for everyk there is exactly onef F
2x] with deg (f)=k,f(O) O, andL(f)=1. IfF
q
is the finite field withq elements andg F
q
x] is monic of degreek 1, then there exists a monic irreduciblef F
q
x] with deg (f)=k, gcd (f,g)=1, andK(f/g)<2+2 (logk)/logq, where the caseq=k=2 andg(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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|