Randomized algorithms in number theory

DOI10.1002/CPA.3160390713zbMath0622.10002OpenAlexW2037038460WikidataQ56226714 ScholiaQ56226714MaRDI QIDQ3758904

Michael O. Rabin, Jeffrey O. Shallit

Publication date: 1986

Published in: Communications on Pure and Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/cpa.3160390713

zbMATH Keywords

representation of integerscomputational number theoryoverviewexpected run timesselection of randomized algorithmssums of three triangular numberssums of two, three or four squares

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Waring's problem and variants (11P05) Radix representation; digital problems (11A63) Software, source code, etc. for problems pertaining to number theory (11-04)

Related Items (12)

Optimal ancilla-free Pauli+V circuits for axial rotations ⋮ Dirichlet’s proof of the three-square theorem: An algorithmic perspective ⋮ Efficient Non-interactive Range Proof ⋮ Pourchet’s theorem in action: decomposing univariate nonnegative polynomials as sums of five squares ⋮ Breaking SIDH in polynomial time ⋮ Zero-knowledge arguments for subverted RSA groups ⋮ Super-Golden-Gates for \(PU(2)\) ⋮ Removing the Strong RSA Assumption from Arguments over the Integers ⋮ Some notes on the linear complexity of Sidel'nikov-Lempel-Cohn-Eastman sequences ⋮ Efficient range proofs with transparent setup from bounded integer commitments ⋮ Unnamed Item ⋮ Integral matrix Gram root and lattice Gaussian sampling without floats

Cites Work

• Unnamed Item
• Breaking the Ong-Schnorr-Shamir Signature Scheme for Quadratic Number Fields
• Solving Bivariate Quadratic Congruences in Random Polynomial Time

This page was built for publication: Randomized algorithms in number theory