Computing Modular Cube Roots Modulo a Prime

[Hurkyl]

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)

 

[Hurkyl]

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 a², and have to take a square root in order to get a fifth root of a -- can that be avoided?

 

[CyberGhost]

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

 

[Hurkyl]

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)

 

[CyberGhost]

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

 

[Hurkyl]

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.

 

[CRGreathouse]

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

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

 

[Hurkyl]

Okay, fine.

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

Let g be a generator of the multiplicative group.

Then w := g^{3k-1 m} is a nontrivial cube root of unity.

Let j be the smallest natural number such that x^{3j m}= 1. Suppose j > 0.
Then, x^{3j-1 m} is either w or w².
If w, then (x g^{2 3k-j})^{3j-1 m} = w³ = 1
If w², then (x g^3k-j)^{3j-1 m} = w³ = 1

Starting with a, iterating the above procedure gives us a number t such that

(a t³)^m = 1​

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

 

[Hurkyl]

Hurkyl's algorithm for division by p^k 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 p^kh=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 + vp^k = 1. Then, if we choose h = v g, we have

p^k h = p^k v g = (1 - un) g = g​

Case 2: G has order p^e.

For group elements x, let v(x) denote the smallest natural number such that

p^v(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 p^e-1 z​

Suppose that v(x) = d > 0. Then p^d-1 x appears in the right hand side of the lookup table, corresponding to some integer n. Then, we have

p^d-1 x = n p^e-1 z​

p^d-1 (x - n p^e-d-k p^k z) = 0​

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

This loop eventually terminates, and the final value of h satisfies

g - p^k h = 0​

as desired.

Case 3: G is an arbitrary cyclic group

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

Then g = u(mg) + v(p^eg).

p^eg lies in a subgroup of order m, and using case 1, we can find h₁ such that p^kh₁ = p^eg.

mg lies in a subgroup of order p^e, and using case 2, we can find h₂ such that p^kh₂ = mg.

Set h = vh₁ + uh₂. Then p^k h = g.

 

[Hurkyl]

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.

 

[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?

 

[Hurkyl]

What if p-1 != 3^k m? ("!=" is "not equal"). Is there a sense to choose k=0?

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

in order to revert rsa

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).

 

[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...

 

[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.

 

[CyberGhost]

http://eprint.iacr.org/2009/457.pdf"