Modular exponentiation via the explicit Chinese remainder theorem

DOI10.1090/S0025-5718-06-01849-7MaRDI QIDQ3420440zbMATH OpenFDO

Authors Daniel J. Bernstein, Jonathan P. Sorenson

Publication date 2 February 2007

Published in Mathematics of Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1090/S0025-5718-06-01849-7

zbMATH Keywords

parallel complexity of modular exponentiation

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Parallel algorithms in computer science (68W10)

Recommendations

• A practical parallel algorithm for computinga b modc *
• The parallel complexity of exponentiating polynomials over finite fields
• A fast modular square computing method based on the generalized Chinese remainder theorem for prime moduli
• scientific article; zbMATH DE number 18647
• Fast arithmetics using Chinese remaindering

Cites work

• A Survey of Fast Exponentiation Methods
• An FFT Extension to the P - 1 Factoring Algorithm
• Approximate formulas for some functions of prime numbers
• Computing Powers in Parallel
• Efficient algorithms for computing the Jacobi symbol
• Fast modular transforms
• Fast multiplication and its applications
• Fast multiplication of large numbers
• Faster optimal parallel prefix sums and list ranking
• High primes and misdemeanours: lectures in honour of the 60th birthday of Hugh Cowie Williams. Selected papers from the international conference on number theory, Banff, AB, Canada, May 24--30, 2003.
• scientific article; zbMATH DE number 435565 (Why is no real title available?)
• scientific article; zbMATH DE number 475435 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 2154267 (Why is no real title available?)
• scientific article; zbMATH DE number 954401 (Why is no real title available?)
• scientific article; zbMATH DE number 3303655 (Why is no real title available?)
• Log Depth Circuits for Division and Related Problems
• PRIMES is in P
• Simulation of Parallel Random Access Machines by Circuits
• The development of the number field sieve
• Two fast parallel prime number sieves

Cited in

(21)

• A fast modular square computing method based on the generalized Chinese remainder theorem for prime moduli
• Delay encryption
• How to Remove the Exponent GCD in HK09
• Computing Hilbert class polynomials with the Chinese remainder theorem
• Census algorithms for chinese remainder pseudorank
• Exact exponent in the remainder term of Gelfond's digit theorem in the binary case
• scientific article; zbMATH DE number 1189246 (Why is no real title available?)
• Improved Parallel Polynomial Division
• The CREW PRAM Complexity of Modular Inversion
• Accelerating the CM method
• Improved Stage 2 to P ± 1 Factoring Algorithms
• Modular polynomials via isogeny volcanoes
• Time-release cryptography from minimal circuit assumptions
• (Verifiable) delay functions from Lucas sequences
• On sequential functions and fine-grained cryptography
• Computing modular polynomials by deformation
• Greyhound: fast polynomial commitments from lattices
• Reducing the number of qubits in quantum factoring
• Watermarkable and zero-knowledge verifiable delay functions from any proof of exponentiation
• Reducing the number of qubits in quantum discrete logarithms on elliptic curves
• A randomized sublinear time parallel GCD algorithm for the EREW PRAM

This page was built for publication: Modular exponentiation via the explicit Chinese remainder theorem

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