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

--00000000000081c833064e11d734
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Le sam. 28 mars 2026 =C3=A0 08:49, La=C3=ABl Cellier <[email protected]=
m> a
=C3=A9crit :

> On Fri, Mar 27, 2026 at 02:26:49PM +0100, La=C3=ABl Cellier wrote:
> > Bonjour,
> >
> > if I have a finite field factorization which too complex to be compute
> > automatically. For example, let s say
> > 21888242871839275222246405745257275088696311157297823662689037894645226=
208583=C2=B9=C2=B2=E2=88=921=3D2
> > =C3=97 2 =C3=97 2 =C3=97 2 =C3=97 2 =C3=97 3 =C3=97 3 =C3=97 3 =C3=97 5=
 =C3=97 7 =C3=97 11 =C3=97 13 =C3=97 17 =C3=97 29 =C3=97 67 =C3=97 163 =C3=
=97 229 =C3=97
> > 311 =C3=97 397 =C3=97 983 =C3=97 3769 =C3=97 4051 =C3=97 11003 =C3=97 4=
3913 =C3=97 1400587 =C3=97 5830087 =C3=97
> > 32159167 =C3=97 405928799 =C3=97 11465965001 =C3=97 41692944763 =C3=97 =
152001576931 =C3=97
> > 52920684769483 =C3=97 3005054907817151659 =C3=97 3388996819669187238034=
903 =C3=97
> > 13427688667394608761327070753331941386769 =C3=97
> > 104348903484733242407804502753091803656481823949 =C3=97
> > 64146966983547661987959683617937708319359041535057415875983506058816159=
059153647304344187619
> > =C3=97 292709098791663788479256587 =C3=97 12051215992189917705435977487=
75484291 =C3=97
> > 1299287670584980812472075235801753046609485536283861463811601644579 =C3=
=97
> > 64177052757608003316984792821190393947290473614419530386479121451917641=
122805418393835009573667434937689392838890413030823815490004914389366996109
> > =C3=97 493356762637 =C3=97 493356762637 =C3=97 2126437289207585950861 =
=C3=97
> > 99958339237566847387819651978153731703086441622746320518140724932023978=
446602500157015660689865730448242821374173445127241730633861337008355847407=
51075324811175115719549874430103358645783161654857
> >
> > Then, how can I provide such a factorization to Pari/gp in order to com=
pute
> > 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=E2=80=AF? Using addprimes with which functions=
=E2=80=AF?
> Cordialement
>
>
      Simplement
{
addprimes([
3005054907817151659,
3388996819669187238034903,
3388996819669187238034903,
641469669835476619879596836179377083193590415350574158759835060588161590591=
53647304344187619,
...
}

    en incluant tous les premiers "grands", c'est =C3=A0 dire >2^28

          Lo=C3=AFc

--00000000000081c833064e11d734
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div dir=3D"ltr"><div class=3D"gmail_default" style=3D"fon=
t-family:verdana,sans-serif"><br></div></div><br><div class=3D"gmail_quote =
gmail_quote_container"><div dir=3D"ltr" class=3D"gmail_attr">Le=C2=A0sam. 2=
8 mars 2026 =C3=A0=C2=A008:49, La=C3=ABl Cellier &lt;<a href=3D"mailto:lael=
[email protected]">[email protected]</a>&gt; a =C3=A9crit=C2=A0:<br><=
/div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;bo=
rder-left:1px solid rgb(204,204,204);padding-left:1ex"><u></u>

 =20
   =20
 =20
  <div>
    <pre>On Fri, Mar 27, 2026 at 02:26:49PM +0100, La=C3=ABl Cellier wrote:
&gt; Bonjour,
&gt;=20
&gt; if I have a finite field factorization which too complex to be compute
&gt; automatically. For example, let s say
&gt; 2188824287183927522224640574525727508869631115729782366268903789464522=
6208583=C2=B9=C2=B2=E2=88=921=3D2
&gt; =C3=97 2 =C3=97 2 =C3=97 2 =C3=97 2 =C3=97 3 =C3=97 3 =C3=97 3 =C3=97 =
5 =C3=97 7 =C3=97 11 =C3=97 13 =C3=97 17 =C3=97 29 =C3=97 67 =C3=97 163 =C3=
=97 229 =C3=97
&gt; 311 =C3=97 397 =C3=97 983 =C3=97 3769 =C3=97 4051 =C3=97 11003 =C3=97 =
43913 =C3=97 1400587 =C3=97 5830087 =C3=97
&gt; 32159167 =C3=97 405928799 =C3=97 11465965001 =C3=97 41692944763 =C3=97=
 152001576931 =C3=97
&gt; 52920684769483 =C3=97 3005054907817151659 =C3=97 338899681966918723803=
4903 =C3=97
&gt; 13427688667394608761327070753331941386769 =C3=97
&gt; 104348903484733242407804502753091803656481823949 =C3=97
&gt; 6414696698354766198795968361793770831935904153505741587598350605881615=
9059153647304344187619
&gt; =C3=97 292709098791663788479256587 =C3=97 1205121599218991770543597748=
775484291 =C3=97
&gt; 1299287670584980812472075235801753046609485536283861463811601644579 =
=C3=97
&gt; 6417705275760800331698479282119039394729047361441953038647912145191764=
112280541839383500957366743493768939283889041303082381549000491438936699610=
9
&gt; =C3=97 493356762637 =C3=97 493356762637 =C3=97 2126437289207585950861 =
=C3=97
&gt; 9995833923756684738781965197815373170308644162274632051814072493202397=
844660250015701566068986573044824282137417344512724173063386133700835584740=
751075324811175115719549874430103358645783161654857
&gt;=20
&gt; Then, how can I provide such a factorization to Pari/gp in order to co=
mpute
&gt; 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=E2=80=AF? Using addprimes with which functions=E2=
=80=AF?
Cordialement</pre></div></blockquote><div><br></div><div><div style=3D"font=
-family:verdana,sans-serif" class=3D"gmail_default">=C2=A0 =C2=A0 =C2=A0 Si=
mplement</div><div style=3D"font-family:verdana,sans-serif" class=3D"gmail_=
default">{</div><div style=3D"font-family:verdana,sans-serif" class=3D"gmai=
l_default">addprimes([</div><div style=3D"font-family:verdana,sans-serif" c=
lass=3D"gmail_default">3005054907817151659,</div><div style=3D"font-family:=
verdana,sans-serif" class=3D"gmail_default">3388996819669187238034903,</div=
><div style=3D"font-family:verdana,sans-serif" class=3D"gmail_default">3388=
996819669187238034903,</div><div style=3D"font-family:verdana,sans-serif" c=
lass=3D"gmail_default">6414696698354766198795968361793770831935904153505741=
5875983506058816159059153647304344187619,</div><div style=3D"font-family:ve=
rdana,sans-serif" class=3D"gmail_default">...</div><div style=3D"font-famil=
y:verdana,sans-serif" class=3D"gmail_default">}</div></div><div><br></div><=
div><div style=3D"font-family:verdana,sans-serif" class=3D"gmail_default">=
=C2=A0 =C2=A0 en incluant tous les premiers &quot;grands&quot;, c&#39;est =
=C3=A0 dire &gt;2^28</div><div style=3D"font-family:verdana,sans-serif" cla=
ss=3D"gmail_default"><br></div><div style=3D"font-family:verdana,sans-serif=
" class=3D"gmail_default">=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 Lo=C3=AFc</div=
><br></div></div></div>

--00000000000081c833064e11d734--