Recall that the period of a polynomial p(x) is the smallest n such that p divides x^n-1.The average is known to be of the order of q^n . I am interested in order of magnitude of the tail of the distribution...Say how many polys have period at most Kn for some fixed constant K.
The number of monic irreducible polynomials in 〖 F〗_q [x] of degree m and order e is equal to ( φ(e))/m, where φ(e) is denoted by different primitive e th roots of unity over F_q.
If e≥2 and m is the multiplicative order of q (modulo e), equal to 2.
If m=e=1, equal to 0 in all other cases.
The degree of an irreducible polynomial in 〖 F〗_q [x] of order e must be equal to the multiplicative order of q modulo e.
Hi Selda,
thanks for the tip. Part of the difficulty is that I want to count all polys not just the irreducible ones...
If you want the period with kn. Thus, you must be chosen the Gaussian normal basis representation that equals to the period kn.
- Badges
- Science topic
- Similar topics
- Control Systems Engineering
- Filtering