Ask Your Question

The meaning of arguments of is_primitive

asked 2021-10-04 13:48:48 +0200

anonymous user


Say we have

R.<x> = PolynomialRing( GF(5) )
f = x^2 + 2*x +3

then we can use f.is_primitive() to tell if f is primitive. But is_primitive has two argument n and n_prime_divs. The document say

"n" (default: "None") - if provided, should equal q-1 where
        "self.parent()" is the field with q elements;  otherwise it
        will be computed.

But this is whose 'self'? Is it the self of polynomial f? so n=4? I think here the n shall be 5^2-1. The following code will result in error.

f.is_primitive(4, [2])


f.is_primitive(5^2-1, prime_divisors(5^2-1))

will give the correct answer.

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2021-10-08 19:48:51 +0200

According to the source code, it looks like n should be q^d-1 where q is the cardinality of the field and d is the degree of the polynomial. So the documentation seems to be wrong.

edit flag offensive delete link more



I assume the meaning of $n$ is to provide a multiple of the order of $x$ modulo $f$ - in some cases (when it's known and smaller than $q^d-1$) it may speed up computation.

Max Alekseyev gravatar imageMax Alekseyev ( 2021-10-08 23:21:10 +0200 )edit

I think providing its prime divisors will speed up calculation even more.

John Palmieri gravatar imageJohn Palmieri ( 2021-10-09 03:30:27 +0200 )edit

Thank you!

zxl gravatar imagezxl ( 2021-10-10 11:47:44 +0200 )edit

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


Asked: 2021-10-04 13:48:48 +0200

Seen: 40 times

Last updated: Oct 08