Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Modular cube roots

  1. Jun 10, 2006 #1

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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. jcsd
  3. Jun 15, 2006 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Well, Shank's algorithm was easy enough to modify. :blushing:


    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?
     
  4. May 9, 2009 #3
    What values should be used for t? Are there newer and more effective methods for finding cubic residue? :)
     
  5. May 9, 2009 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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. :frown:

    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 [itex]x^3 - a[/itex] modulo p. (Actually, a polynomial modular root-finding algorithm would suffice)
     
  6. May 9, 2009 #5
    I assume you've never applied your interpretation of that algo?..
     
  7. May 9, 2009 #6

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  8. May 10, 2009 #7

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

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

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  10. May 10, 2009 #9

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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
  11. May 10, 2009 #10

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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
  12. May 16, 2009 #11
    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?
     
  13. May 16, 2009 #12

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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).
     
  14. May 17, 2009 #13
    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...
     
  15. Jun 16, 2009 #14
    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.
     
  16. Dec 12, 2009 #15
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Modular cube roots
  1. Modular arithmetic (Replies: 1)

  2. Modular arithmetic (Replies: 4)

  3. Modular Arithmatic (Replies: 6)

Loading...