A simple and fast probabilistic algorithm for computing square roots modulo a prime number (Corresp.)

DOI10.1109/TIT.1986.1057236zbMath0658.68043OpenAlexW2024686830MaRDI QIDQ3806810

René Peralta

Publication date: 1986

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/tit.1986.1057236

zbMATH Keywords

finite fieldssquare rootscomputational number theoryrandom polynomial time algorithmRP algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Finite fields and commutative rings (number-theoretic aspects) (11T99) Power residues, reciprocity (11A15) Software, source code, etc. for problems pertaining to field theory (12-04)

Related Items (15)

Taking cube roots in \(\mathbb Z_{m}\) ⋮ An algorithm for recognising the exterior square of a matrix ⋮ On the Cipolla-Lehmer type algorithms in finite fields ⋮ Improved authenticated multiple-key agreement protocol ⋮ Univariate polynomial factorization over finite fields ⋮ Unnamed Item ⋮ Improved low-computation partially blind signatures. ⋮ Unnamed Item ⋮ On splitting sets in block designs and finding roots of polynomials ⋮ On Relationship of Computational Diffie-Hellman Problem and Computational Square-Root Exponent Problem ⋮ On taking square roots without quadratic nonresidues over finite fields ⋮ Efficient randomized generation of optimal algorithms for multiplication in certain finite fields ⋮ On the complexity of the discrete logarithm and Diffie-Hellman problems ⋮ New cube root algorithm based on the third order linear recurrence relations in finite fields ⋮ An algorithm to compute the number of points on elliptic curves of \(j\)-invariant 0 or 1728 over a finite field

This page was built for publication: A simple and fast probabilistic algorithm for computing square roots modulo a prime number (Corresp.)