# Modular cube roots

1. Jun 10, 2006

### Hurkyl

Staff Emeritus
Is there a good algorithm for computing such things modulo a prime?

(I'll confess to not yet having tried to see if Shanks' algorithm can be easily adapted; I'll probably fiddle with that tomorrow)

2. Jun 15, 2006

### Hurkyl

Staff Emeritus
Well, Shank's algorithm was easy enough to modify.

But it did bring up another question -- when taking the modular cube root of a mod p, I look for:

(a t³)^m = 1

where m is the largest factor of p-1 not divisible by 3. Then, I have to split into two cases: if m = 2 (mod 3), I take:

a^[ (m+1) / 2 ] t^m

as my cube root of a. But if m = 1 (mod 3), I have to take:

a^[ (m-1) / 2 ] t^m

as my cube root of 1/a.

That's all easy enough, but what about taking modular fifth roots? It seems that if m = 3 (mod 5), then we're stuck with a fifth root of , and have to take a square root in order to get a fifth root of a -- can that be avoided?

3. May 9, 2009

### CyberGhost

What values should be used for t? Are there newer and more effective methods for finding cubic residue? :)

4. May 9, 2009

### Hurkyl

Staff Emeritus
Ack; it's been three years since I was looking at this! All I remember was that when looking at the proof that Shank's algorithm works, it was straightforward to modify for cube roots. If I wanted to work it out again, I would have to go back and relearn why it works for square roots.

Anyways, I do know of another method, but no idea how it compares in efficiency -- you can simply use a polynomial factorization algorithm to factor the polynomial $x^3 - a$ modulo p. (Actually, a polynomial modular root-finding algorithm would suffice)

5. May 9, 2009

### CyberGhost

I assume you've never applied your interpretation of that algo?..

6. May 9, 2009

### Hurkyl

Staff Emeritus
I cannot remember why I was interested in cube roots three years ago, but the reason could easily have been sheer curiousity.

I've thought about using it a couple of times since then, but never in a setting where it was worth spending the effort.

7. May 10, 2009

### CRGreathouse

Well if you re-derive it at some point, post it rather than assuming that it's so obvious you'll remember. :)

8. May 10, 2009

### Hurkyl

Staff Emeritus
Okay, fine. :tongue:

Let p-1 = 3k m, where m is not divisible by 3.

Let g be a generator of the multiplicative group.

Then w := g3k-1 m is a nontrivial cube root of unity.

Let j be the smallest natural number such that x3j m= 1. Suppose j > 0.
Then, x3j-1 m is either w or w2.
If w, then (x g2 3k-j)3j-1 m = w3 = 1
If w2, then (x g3k-j)3j-1 m = w3 = 1

Starting with a, iterating the above procedure gives us a number t such that
(a t3)m = 1

at which point the rest is given in my old post.

9. May 10, 2009

### Hurkyl

Staff Emeritus
Hurkyl's algorithm for division by pk in finite, black-box, additive, cyclic groups of known order.

Let G be an additive cyclic group of order n. Let g be an element of G. The problem is to find an element h such that pkh=g, or to prove such an element doesn't exist.

Case 1: G has no p-torsion

Use the extended Euclidean algorithm to find u, v such that un + vpk = 1. Then, if we choose h = v g, we have
pk h = pk v g = (1 - un) g = g​

Case 2: G has order pe.

For group elements x, let v(x) denote the smallest natural number such that
pv(x) x = 0.​

Let z be a generator of G (i.e. v(z) = e). Note that some h exists if and only if v(g) <= e - k.

Construct the following lookup table, for 0 < n < p:
n <---> n pe-1 z​

Suppose that v(x) = d > 0. Then pd-1 x appears in the right hand side of the lookup table, corresponding to some integer n. Then, we have
pd-1 x = n pe-1 z​
pd-1 (x - n pe-d-k pk z) = 0​

We can compute h with the following algorithm:
Set h := 0
While v(g - pk h) = d > 0:
... Look up n such that pd-1 (g - pk h) = n pe-1 z
... Set h := h + n pe-d-k z

This loop eventually terminates, and the final value of h satisfies
g - pk h = 0​
as desired.

Case 3: G is an arbitrary cyclic group

Let n = pe m with p,m relatively prime.. Use the extended Euclidean algorithm to compute u,v such that um+vpe=1.

Then g = u(mg) + v(peg).

peg lies in a subgroup of order m, and using case 1, we can find h1 such that pkh1 = peg.

mg lies in a subgroup of order pe, and using case 2, we can find h2 such that pkh2 = mg.

Set h = vh1 + uh2. Then pk h = g.

Last edited: May 10, 2009
10. May 10, 2009

### Hurkyl

Staff Emeritus
This solves the question I had three years ago. Surely this has to be a "well-known" algorithm in some circles?

Anyways, I stated it for finite cyclic groups, but it is somewhat more general than that. For example, it should be easy to tweak to work for groups isomorphic to Q/Z.

I think case 3 can be streamlined a bit, but for the moment I'm happy as is.

The algorithm uses O(p) space to compute p-adic reciprocity (is that the right word? I'm looking for the higher analog of quadratic and cubic reciprocity). If there's a more clever way, this can probably be improved for large p.

Last edited: May 10, 2009
11. May 16, 2009

### CyberGhost

I have several questions but let's start with the first. Sorry for that -- I am a mere programmer and I am trying to implement your findings in a small program in order to revert rsa with public exponent 3. What if p-1 != 3^k m? ("!=" is "not equal"). Is there a sense to choose k=0?

12. May 16, 2009

### Hurkyl

Staff Emeritus
k=0 is fine. But in that case, finding cube roots is easy: it's just a single modular exponentiation.

Won't work. Fast root-finding or polynomial factoring algorithms depend on the modulus being a prime power. For composite moduli, finding roots is pretty much equivalent to factoring.

e.g. if you know all of the square roots of an RSA modulus, then you can factor the modulus with a few arithmetic operations (less than 10) and GCD tests (less than 4).

13. May 17, 2009

### CyberGhost

Thank you. Then if I factor messages?..It is easy with primes that are cubes...(e.g. occur 3 times). But the majority of primes are not cubes, of course...And their cubic residues are unknown...

14. Jun 16, 2009

### Chris M.

Inspired by Hurkyl, I tried a slightly modified version Shank's algorithm for finding solutions to modular cube roots. For the three cases I tried it seemed only necessary to use a 3 instead of a 2 when using the algorithm.

Here were the cases.
[x^3 congruent to 24(mod 73),
x^3 congruent to 22(mod 43),
x^3 congruent to 61(mod 127)]

This was a great help ! THANK YOU

At this point I am looking for any leads to WHY Shank's algorithm works.

15. Dec 12, 2009