mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2008-02-23, 23:10   #1
Yamato
 
Yamato's Avatar
 
Sep 2005
Berlin

1028 Posts
Default 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
Yamato is offline   Reply With Quote
Old 2008-02-24, 00:10   #2
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

110000010112 Posts
Default

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?
Zeta-Flux is offline   Reply With Quote
Old 2008-02-24, 09:11   #3
Yamato
 
Yamato's Avatar
 
Sep 2005
Berlin

2×3×11 Posts
Default

It should be efficient, p is supposed to have at least ~100 digits. For square roots, there is such an efficient method (Shanks-Tonelli).
Yamato is offline   Reply With Quote
Old 2008-02-24, 12:40   #4
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

193416 Posts
Default

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.
fivemack is offline   Reply With Quote
Old 2008-02-24, 12:56   #5
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

2·3,163 Posts
Default

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.
retina is offline   Reply With Quote
Old 2008-02-25, 14:09   #6
m_f_h
 
m_f_h's Avatar
 
Feb 2007

1B016 Posts
Default

Quote:
Originally Posted by retina View Post
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
m_f_h is offline   Reply With Quote
Old 2008-02-25, 15:08   #7
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

22×1,613 Posts
Default

Quote:
Originally Posted by retina View Post
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.
fivemack is offline   Reply With Quote
Reply

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 2015-10-25 18:39
square root modulo prime Raman Math 1 2010-02-16 21:25
Cube Mountains davar55 Puzzles 9 2008-06-03 22:36
Cube root mfgoode Homework Help 10 2007-10-05 04:12
The difference between P2P and distributed computing and grid computing 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔