Randomized algorithms in number theory

DOI10.1002/CPA.3160390713zbMATH Open0622.10002OpenAlexW2037038460WikidataQ56226714 ScholiaQ56226714MaRDI QIDQ3758904FDOQ3758904

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

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

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)

Cites Work

• Solving Bivariate Quadratic Congruences in Random Polynomial Time
• Title not available (Why is that?)
• Breaking the Ong-Schnorr-Shamir Signature Scheme for Quadratic Number Fields

Cited In (18)

• 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
• Title not available (Why is that?)
• 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
• Breaking SIDH in polynomial time

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)