Re: Q: Finding primitive polynomials

From: Bryan Olson (fakeaddress_at_nowhere.org)
Date: 10/29/04 

Date: Fri, 29 Oct 2004 05:12:40 GMT

Mok-Kong Shen wrote:
> [...] Now suppose algorithm 4.77 succeeds and
> 'additionally' for r_0=1 one has l(x)=1, wouldn't that establish
> that x is a generator? Note that the last computation shows that
> the order of x must be a divisor of p^m-1 and that the success
> of the original algorithm shows that that can't be a proper
> divisor of p^m-1. (In what I said about the trials I did in
> the post that initiated this thread, I actually did the the
> test that way.) With this extension algorithm 4.77 would
> then be self-sufficient to decide whether a given arbitrary
> polynormial is primitive, since the other criteria of being
> a field are obviously fulfilled.

Seems right. The next question is whether the "self-sufficient" method
would be an improvement over first finding irreducible polynomials, then
testing whether they are primitive. 

-- 
--Bryan
Quantcast