mersenneforum.org > Math Computing the cube root modulo p
 Register FAQ Search Today's Posts Mark Forums Read

 2008-02-23, 23:10 #1 Yamato     Sep 2005 Berlin 1028 Posts Computing the cube root modulo p Let p be a prime, such that p-1 is divisible by 3. And given a number 1 < a < p. How do I get the cube root of a modulo p (means a number r so that r³ = a)? If p-1 is not divisible by 3, r can be taken as a^e, where e is the modular inverse of 3 modulo (p-1), but that doesn't work here. Last fiddled with by Yamato on 2008-02-23 at 23:11
 2008-02-24, 00:10 #2 Zeta-Flux     May 2003 110000010112 Posts Well, first you have to check that a will have a cube root, by finding its order modulo p, which better be a divisor of (p-1)/3. If it does have a cube root, I suppose brute force will work. Or do you want an efficient algorithm?
 2008-02-24, 09:11 #3 Yamato     Sep 2005 Berlin 2×3×11 Posts It should be efficient, p is supposed to have at least ~100 digits. For square roots, there is such an efficient method (Shanks-Tonelli).
 2008-02-24, 12:40 #4 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 193416 Posts The Wikipedia article on Shanks-Tonelli claims that, if you replace 'quadratic' with 'cubic' and 2 with 3 throughout, you get a cube-root algorithm. Cube roots modulo primes are a special case of factoring polynomials over prime fields, and for that there are efficient algorithms implemented in things like gp: Code: gp > p=10^120+267 > factor(x^3-Mod(19,p)) takes about 80 milliseconds on a slow PC to find that 47970552105796978034550792419787283893791969956599592477241757612897065709745650364324681802104708046834360375790877318^3 = 19 mod p There are lovely tricks for polynomial factorisation; the easiest one is to notice that, by Fermat's little theorem, x^p = x for all numbers mod p. So x^(p-1)-1 will have roots at all non-zero numbers mod p. But it factorises as (x^q-1)(x^q+1) with q=(p-1)/2. So x^q-1 and x^q+1 will each have roots at half the non-zero numbers mod p - specifically, the quadratic residues and non-residues respectively. So GCD(f(x), x^q-1) will be the product of the roots of f(x) which are quadratic residues, and GCD(f(x), x^q+1) will be the product of the roots of f(x) which aren't quadratic residues. And GCD(f(x+1), x^q-1) will be the product of the roots which are one less than quadratic residues; GCD(f(x+17), x^q-1) will be the product of the roots which are seventeen less than quadratic residues ... since the quadratic residues are basically randomly distributed, you can proceed roughly recursively, and all you need is a routine for computing huge powers of x modulo a polynomial of degree at most three modulo p.
 2008-02-24, 12:56 #5 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 2·3,163 Posts But you need to find all three roots. 1^(1/3) mod 7 = {1, 2, 4} 6^(1/3) mod 7 = {3, 5, 6} 1^(1/3) mod 13 = {1, 3, 9} 5^(1/3) mod 13 = {7, 8, 11} 8^(1/3) mod 13 = {2, 5, 6} 12^(1/3) mod 13 = {4, 10, 12} etc.
2008-02-25, 14:09   #6
m_f_h

Feb 2007

1B016 Posts

Quote:
 Originally Posted by retina But you need to find all three roots. 1^(1/3) mod 7 = {1, 2, 4} 6^(1/3) mod 7 = {3, 5, 6} 1^(1/3) mod 13 = {1, 3, 9} 5^(1/3) mod 13 = {7, 8, 11} 8^(1/3) mod 13 = {2, 5, 6} 12^(1/3) mod 13 = {4, 10, 12} etc.
on one hand, factor(x^3-Mod(y,p)) gives of course all 3 roots
on the other hand, r=sqrtn( Mod(y,p), 3, &z) will give one root r and z such that all roots are given by r*z^k (k=0,1,2 here).
PS: still in gp, ??sqrtn shows you a (very inefficiently written) function sqrtnall() returning the vector of all n-th roots.
No idea why they use "sqrtn" for the n-th roots, the "sq" obviously is useless here...

Last fiddled with by m_f_h on 2008-02-25 at 14:14

2008-02-25, 15:08   #7
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

22×1,613 Posts

Quote:
 Originally Posted by retina But you need to find all three roots.
If there are three roots, then their ratios are non-trivial cube roots of 1; therefore non-trivial cube roots of 1 must exist, which means the prime must be 1 mod 3, which is the case where cube roots can be done by a single exponentiation.

 Similar Threads Thread Thread Starter Forum Replies Last Post Brain GPU Computing 20 2015-10-25 18:39 Raman Math 1 2010-02-16 21:25 davar55 Puzzles 9 2008-06-03 22:36 mfgoode Homework Help 10 2007-10-05 04:12 GP2 Lounge 2 2003-12-03 14:13

All times are UTC. The time now is 22:01.

Wed Jan 19 22:01:28 UTC 2022 up 180 days, 16:30, 0 users, load averages: 1.83, 1.62, 1.67