period calc

Infinite Period? PhL 7.10.13 How do you compute the period of some f(x) other than Maple brute force? I never really found a way, though looked down some Avenues here. Also, still not sure there are no nice f(x) which has an infinite period. I managed to work around not knowing the answers to these questions. I wanted to say something about the period of the CRC polynomial but decided to say just that it is probably very large. New question. Are there polynomials which have no period ? That is to say f(x) for which there exists no n>1 such that Rem[(xn-1)/f(x)] ≠ 0. 1. We know this is true of f(x) = xiF(x), for example. 2. We know that if f(x) is a min poly for some GF(q), then there does exist such an n ≤ q-1. So if we could show that f(x) was not a min poly for any GF(q), maybe that would be convincing. Question: How do I know that (xn-1)/x has a remainder? (xn -1) = q(x)x + r(x). Here q(x) must have a term of degree xn-1 . Write q(x) = Axn-1 + Bxn-2 + F (xn -1) = Axn + Bxn-1 + ... + Fx cannot balance against the -1. Contradiction so need r(x) ≠ 0 Plan A. Suppose g(x)h(x) = xn-1 = 1 + xn GF2 only. Then either g(1) = 0, h(1) = 0, or both. Try general form g = g0 + g1x + g2x2 + .....gsxs h = h0 + h1x + h2x2 + .....hrxr gh = 1 + xn = g0h0 + gsxs hrxr + intermediate terms Need r+s = n, gshr = 1, g0h0 = 1, all intermediate terms have even coefficients so 0. c(x) = a(x) b(x) cs = !Syntax Error, I (as-jbj) . Plan B. Suppose f(x) is irreducible in GF(2) and non-linear. Plan C Plan D This seems to be saying that the period of any polynomial must divide 2d - 1. I think they are just saying that you have to find some GF(pm) which does the trick, so maybe only try such values in a search. I tried n = 2m -1 up to n = 4095 and could not divide my CRC-32 into xn-1, and it is very slow at those numbers. Conclusion: I don't think there is any easy way to find n for a given f(x). Fact: If some monic f(x) is a min poly for some GF(q), then it must divide xq-1 - 1. If you find that f(x) does not divide xq-1 - 1, then you know it is not a min poly for that GF(q). You can keep testing higher values of q. A min poly must be irreducible I know. And the CRC one is irreducible. The question is: is it a min poly of some GF(q) ? IN any event, I know that there is no n up to 1573 that works, so n < this would be OK. Comment: Since the CRC has order 32, you would have to get to GF(232) just to have a min poly of that degree! Then you are testing xn-1 for n ≥ 232= 4,294,967,296. So if this CRC is a min poly, you have to go way out there before you can even start looking for a viable min poly! This field has 4 billion roots.