20080223, 23:10  #1 
Sep 2005
Berlin
102_{8} Posts 
Computing the cube root modulo p
Let p be a prime, such that p1 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 p1 is not divisible by 3, r can be taken as a^e, where e is the modular inverse of 3 modulo (p1), but that doesn't work here. Last fiddled with by Yamato on 20080223 at 23:11 
20080224, 00:10  #2 
May 2003
11000001011_{2} 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 (p1)/3.
If it does have a cube root, I suppose brute force will work. Or do you want an efficient algorithm? 
20080224, 09:11  #3 
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 (ShanksTonelli).

20080224, 12:40  #4 
(loop (#_fork))
Feb 2006
Cambridge, England
1934_{16} Posts 
The Wikipedia article on ShanksTonelli claims that, if you replace 'quadratic' with 'cubic' and 2 with 3 throughout, you get a cuberoot 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^3Mod(19,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^(p1)1 will have roots at all nonzero numbers mod p. But it factorises as (x^q1)(x^q+1) with q=(p1)/2. So x^q1 and x^q+1 will each have roots at half the nonzero numbers mod p  specifically, the quadratic residues and nonresidues respectively. So GCD(f(x), x^q1) 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^q1) will be the product of the roots which are one less than quadratic residues; GCD(f(x+17), x^q1) 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. 
20080224, 12:56  #5 
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. 
20080225, 14:09  #6  
Feb 2007
1B0_{16} Posts 
Quote:
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 nth roots. No idea why they use "sqrtn" for the nth roots, the "sq" obviously is useless here... Last fiddled with by m_f_h on 20080225 at 14:14 

20080225, 15:08  #7 
(loop (#_fork))
Feb 2006
Cambridge, England
2^{2}×1,613 Posts 
If there are three roots, then their ratios are nontrivial cube roots of 1; therefore nontrivial 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.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
GPU Computing Cheat Sheet (a.k.a. GPU Computing Guide)  Brain  GPU Computing  20  20151025 18:39 
square root modulo prime  Raman  Math  1  20100216 21:25 
Cube Mountains  davar55  Puzzles  9  20080603 22:36 
Cube root  mfgoode  Homework Help  10  20071005 04:12 
The difference between P2P and distributed computing and grid computing  GP2  Lounge  2  20031203 14:13 