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

[Laël Cellier <lael.cellier@gmail.com>]

On Fri, Mar 27, 2026 at 02:26:49PM +0100, Laël Cellier wrote:
> Bonjour,
> 
> if I have a finite field factorization which too complex to be compute
> automatically. For example, let s say
> 21888242871839275222246405745257275088696311157297823662689037894645226208583¹²−1=2
> × 2 × 2 × 2 × 2 × 3 × 3 × 3 × 5 × 7 × 11 × 13 × 17 × 29 × 67 × 163 × 229 ×
> 311 × 397 × 983 × 3769 × 4051 × 11003 × 43913 × 1400587 × 5830087 ×
> 32159167 × 405928799 × 11465965001 × 41692944763 × 152001576931 ×
> 52920684769483 × 3005054907817151659 × 3388996819669187238034903 ×
> 13427688667394608761327070753331941386769 ×
> 104348903484733242407804502753091803656481823949 ×
> 64146966983547661987959683617937708319359041535057415875983506058816159059153647304344187619
> × 292709098791663788479256587 × 1205121599218991770543597748775484291 ×
> 1299287670584980812472075235801753046609485536283861463811601644579 ×
> 64177052757608003316984792821190393947290473614419530386479121451917641122805418393835009573667434937689392838890413030823815490004914389366996109
> × 493356762637 × 493356762637 × 2126437289207585950861 ×
> 9995833923756684738781965197815373170308644162274632051814072493202397844660250015701566068986573044824282137417344512724173063386133700835584740751075324811175115719549874430103358645783161654857
> 
> 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.

The simplest way is to use addprimes on all primes factors larger than 2^28.

Cheers,
Bill






Hi, but what do you mean ? Using addprimes with which functions ?
Cordialement,