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 theoryexpected run timesoverviewrepresentation of integersselection of randomized algorithmssums of three triangular numberssums of two, three or four squares

Mathematics Subject Classification ID

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

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

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

Cited in

(23)

• Super-Golden-Gates for PU(2)
• Randomized proofs in arithmetic
• Efficient range proofs with transparent setup from bounded integer commitments
• Integral matrix Gram root and lattice Gaussian sampling without floats
• Some notes on the linear complexity of Sidel'nikov-Lempel-Cohn-Eastman sequences
• Optimal ancilla-free Pauli+V circuits for axial rotations
• scientific article; zbMATH DE number 3761286 (Why is no real title available?)
• Dirichlet’s proof of the three-square theorem: An algorithmic perspective
• Random arithmetic formulas can be reconstructed efficiently
• Solovay functions and their applications in algorithmic randomness
• Efficient Non-interactive Range Proof
• Finding the four squares in Lagrange's theorem
• Removing the strong RSA assumption from arguments over the integers
• 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
• A framework for UC secure privacy preserving biometric authentication using efficient functional encryption
• SQIsignHD: new dimensions in cryptography
• Complexity of robust orbit problems for torus actions and the abc-conjecture
• DewTwo: a transparent PCS with quasi-linear prover, logarithmic verifier and 4.5KB proofs from falsifiable assumptions
• On the efficient representation of isogenies. A survey for NuTMiC 2024
• Efficient algorithms for decomposing integers as sums of few tetrahedral numbers
• Inner-product commitments over integers with applications to succinct arguments

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)