Randomized algorithms in number theory

DOI10.1002/CPA.3160390713MaRDI QIDQ3758904zbMATH OpenOpenAlexWikidataFDO

Authors Michael O. Rabin, Jeffrey 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

computational number theoryrepresentation of integersoverviewexpected 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) Radix representation; digital problems (11A63) Waring's problem and variants (11P05) Software, source code, etc. for problems pertaining to number theory (11-04)

Recommendations

• Finding the four squares in Lagrange's theorem
• An introduction to randomized algorithms
• How to Generate Factored Random Numbers
• Realistic analysis of some randomized algorithms
• Dirichlet’s proof of the three-square theorem: An algorithmic perspective

Cites work

• scientific article; zbMATH DE number 3972987 (Why is no real title available?)
• Breaking the Ong-Schnorr-Shamir Signature Scheme for Quadratic Number Fields
• Solving Bivariate Quadratic Congruences in Random Polynomial Time

Cited in

(18)

• Breaking SIDH in polynomial time
• Dirichlet’s proof of the three-square theorem: An algorithmic perspective
• Super-Golden-Gates for \(PU(2)\)
• Optimal ancilla-free Pauli+V circuits for axial rotations
• Efficient Non-interactive Range Proof
• scientific article; zbMATH DE number 3761286 (Why is no real title available?)
• SQIsignHD: new dimensions in cryptography
• Zero-knowledge arguments for subverted RSA groups
• Pourchet’s theorem in action: decomposing univariate nonnegative polynomials as sums of five squares
• Removing the strong RSA assumption from arguments over the integers
• A framework for UC secure privacy preserving biometric authentication using efficient functional encryption
• Finding the four squares in Lagrange's theorem
• Efficient range proofs with transparent setup from bounded integer commitments
• Some notes on the linear complexity of Sidel'nikov-Lempel-Cohn-Eastman sequences
• Integral matrix Gram root and lattice Gaussian sampling without floats
• Random arithmetic formulas can be reconstructed efficiently
• Solovay functions and their applications in algorithmic randomness
• Randomized proofs in arithmetic

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3758904)