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

On Mar 27, 2026, at 8:26 AM, La=EBl Cellier wrote:

> Then, how can I provide such a factorization to Pari/gp in order to =20=

> 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, =20=

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) =3D=3D =
=20
1. But this does not, alas, compute an n-th root if one exists, =20
whereas ispower(A,&root) computes an n-th root if one exists, and =20
stores the answer in root.

If A is some random nonzero element of F_{p^f} and its exact =20
multiplicative order is required, you can start with knowing A^(p^f - =20=

1) =3D=3D 1, and go through A^((p^f - 1)/q) where q is a prime divisor =
of =20
p^f - 1. If there are any such q, refine the order by dividing out all =20=

such q and begin again  When none of them evaluate to 1, you have the =20=

exact order.

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

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

Mod(A,N)^((N-1)/q) =3D/=3D 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 =20
prime.=20=