Re: How to compute a finite field nth root using a provided factorization?

[Kurt Foster <drsardonicus@earthlink.net>]

On Mar 27, 2026, at 8:26 AM, Laël Cellier wrote:

> Then, how can I provide such a factorization to Pari/gp in order to  
> compute arbitrary nth roots? I m meaning, doing the reverse of Modexp.

I assume that n divides the order p^f - 1 of the multiplicative group,  
and the n-th root of A is required.

One test of whether A actually is an n-th power is A^((p^f - 1)/n) ==  
1. But this does not, alas, compute an n-th root if one exists,  
whereas ispower(A,&root) computes an n-th root if one exists, and  
stores the answer in root.

If A is some random nonzero element of F_{p^f} and its exact  
multiplicative order is required, you can start with knowing A^(p^f -  
1) == 1, and go through A^((p^f - 1)/q) where q is a prime divisor of  
p^f - 1. If there are any such q, refine the order by dividing out all  
such q and begin again  When none of them evaluate to 1, you have the  
exact order.

In particular, if A^((p^f - 1)/q) =/= 1 for every prime factor of p^f  
- 1, A is a cyclic generator of the multiplicative group of F_{p^f}.

The case f = 1 is widely familiar: If Mod(A,N)^(N-1) == Mod(1, N), N-1  
is completely factored, and

Mod(A,N)^((N-1)/q) =/= Mod(1,N) for every prime factor q of N-1,

then Mod(A,N) has multiplicative order N-1, which proves that N is  
prime.