Efficient algorithms for the gcd and cubic residuosity in the ring of Eisenstein integers

DOI10.1016/j.jsc.2004.02.006zbMath1156.11346MaRDI QIDQ2456564

Gudmund Skovbjerg Frandsen, Ivan B. Damgård

Publication date: 19 October 2007

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jsc.2004.02.006

zbMATH Keywords

gcd; cubic residuosity

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

13P99: Computational aspects and applications of commutative rings

11Y16: Number-theoretic algorithms; complexity

Related Items

Unnamed Item, Identity based signature scheme based on cubic residues, Lower bounds for decision problems in imaginary, norm-Euclidean quadratic integer rings, A refinement of Müller's cube root algorithm, New number-theoretic cryptographic primitives, The eleventh power residue symbol, New cube root algorithm based on the third order linear recurrence relations in finite fields

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient algorithms for computing the Jacobi symbol
• A fast Euclidean algorithm for Gaussian integers
• Fast computation of the biquadratic residue symbol.
• A public-key cryptosystem utilizing cyclotomic fields
• The Euclidean algorithm in algebraic number fields
• Computational problems associated with Racah algebra
• Fast multiplication of large numbers
• Fast computation of continued fraction expansions.
• Computation of the Solution of x 3 + Dy 3 = 1
• Computing Gretest Common Divisors and Factorizations in Quadratic Number Fields
• Algorithmic Number Theory
• Fundamentals of Computation Theory
• Fundamentals of Computation Theory
• \((1+i)\)-ary GCD computation in \(\mathbb Z[i\) as an analogue to the binary GCD algorithm.]