I make research about big numbers in finite fields and I need to calculate a cube root modulo prime P for the number N:

N = 33307028807218380701173040920772273133747152666242396962200448019852017733098.

P = 115792089237316195423570985008687907853269984665640564039457584007908834671663

All algorithms that I can find over the web is not for modulo prime, or can not calculate cube roots of this number N.

Please, can anyone share the algorithm for finding the cube roots for this number in finite field of P.

  • 1
    $\begingroup$ Hint: the little Fermat theorem tells that since $P$ is prime, if $X\not\equiv0\pmod P$ then $X^{P-1}\equiv1\pmod P$. That holds for example for $X=N$, and for the number $X$ such that $X^3\equiv N\pmod P$ that you want to compute. $\endgroup$ – fgrieu Jul 11 '18 at 11:37
  • 3
    $\begingroup$ I'm voting to close this question as off-topic because it is about general mathematics. $\endgroup$ – fkraiem Jul 11 '18 at 18:22

There is no cubic root for this N in GF(P).

But if, for example, N=1, you would run here (or on your computer):

GF(115792089237316195423570985008687907853269984665640564039457584007908834671663)(1).nth_root(3, all=True)

That will return a list of 3 elements, that are all cubic roots of 1 in Fp.

| improve this answer | |
  • $\begingroup$ Technically you can link a permalink that contains your code. Example here $\endgroup$ – kelalaka Feb 25 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.