Ask Your Question
1

Finding order of a polynomial over finite field

asked 2016-08-27 01:06:49 -0500

vishb gravatar image

updated 2016-08-27 01:10:00 -0500

order of a polynomial $f(x)$ in $\mathbb{F}_p [x]$ is defined as minimum $e$ such that $f(x) | x^e -1$ . Do we have an inbuilt function in sage to find the same ?

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
2

answered 2016-08-28 16:10:36 -0500

nbruin gravatar image

I would expect that you mainly need this for irreducible polynomials. In that case it's the multiplicative order of one of its roots in an appropriate extension:

L = GF(p^f.degree(),name='b')
[a[1].multiplicative_order() for a in f.roots(L)]

(all those numbers should be equal and you only need to compute one of them)

If your polynomial is square-free, you'd have to do this for each of the irreducible factors and take the LCM.

If your polynomial has higher multiplicity factors, you have to take the appropriate powers before taking LCMs

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2016-08-27 01:06:49 -0500

Seen: 106 times

Last updated: Aug 28 '16