Taking cube roots in \(\mathbb Z_{m}\) (Q1614110): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3139838 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A simple and fast probabilistic algorithm for computing square roots modulo a prime number (Corresp.) / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5617656 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Lattice Point Covering Theorem for Rectangles / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0893-9659(02)00031-9 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1969847147 / rank | |||
Normal rank |
Latest revision as of 11:51, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Taking cube roots in \(\mathbb Z_{m}\) |
scientific article |
Statements
Taking cube roots in \(\mathbb Z_{m}\) (English)
0 references
3 September 2002
0 references
The authors investigate methods to compute third roots modulo an integer \(m\). They assume the factorization of \(m\) to be known and thereby reduce the problem to computing third roots modulo a prime \(p\), where the case \(p\equiv 1 \bmod 3\) is the interesting one. The algorithms involve random choices in a given set, therefore, the running times are probabilistic. They provide two generalizations of Peralta's algorithm [\textit{R. Peralta}, IEEE Trans. Inf. Theory 32, 846-847 (1986; Zbl 0658.68043)]. For a cubic residue \(a\) they work in the ring \(\mathbb{Z}_p[x]/(x^3-a)\) and obtain \(\sqrt[3]{a}\) on the cost of computing \(z^{(p-1)/3)}, z\in R\) chosen randomly and one inversion if the result is appropriate. If \(q\) is small in \(p=3^eq+1\) they derive a faster variant. Both have a running time of \(O(\log^3 p)\). The second algorithm extends the Tonelli-Shanks method [see \textit{D. Shanks}, Proc. 2nd Manit. Conf. Numer. Math., Winnipeg 1972, 51-70 (1973; Zbl 0307.10015)]. The algorithm uses properties of the 3-Sylow subgroup of \(\mathbb{Z}_p^*\) and has a running time of \(O(\log^4 p)\).
0 references
cube root
0 references
Peralta algorithm
0 references
Tonelli-Shanks algorithm
0 references
0 references