Fast arithmetics using Chinese remaindering

DOI10.1016/J.IPL.2009.02.024MaRDI QIDQ989447zbMATHOpenAlexFDO

Authors George Davida, Bruce Litow, Guangwu Xu

Publication date 20 August 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0806.1722

zbMATH Keywords

parallel algorithmChinese remaindering representation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Abstract: In this paper, some issues concerning the Chinese remaindering representation are discussed. Some new converting methods, including an efficient probabilistic algorithm based on a recent result of von zur Gathen and Shparlinski cite{Gathen-Shparlinski}, are described. An efficient refinement of the NC${}^1$ division algorithm of Chiu, Davida and Litow cite{Chiu-Davida-Litow} is given, where the number of moduli is reduced by a factor of $logn$.

Recommendations

• Fast Chinese remaindering in practice
• Efficient Implementations of the Chinese Remainder Theorem for Sign Detection and Residue Decoding
• Residue-to-binary converters based on new Chinese Remainder Theorems
• scientific article; zbMATH DE number 1122449
• scientific article; zbMATH DE number 17620

Cites work

• scientific article; zbMATH DE number 1936673 (Why is no real title available?)
• scientific article; zbMATH DE number 1405690 (Why is no real title available?)
• Division in logspace-uniform NC
• Fast Parallel Arithmetic via Modular Representation
• GCD of random linear combinations
• Integer division in residue number systems
• Log Depth Circuits for Division and Related Problems

Cited in

(8)

• Modular exponentiation via the explicit Chinese remainder theorem
• scientific article; zbMATH DE number 17620 (Why is no real title available?)
• A note on Chang-Lai's modular square algorithm based on the generalized Chinese remainder theorem
• Fast Chinese remaindering in practice
• Fast evaluation of iterated multiplication of very large polynomials: an application to Chinese remainder theory
• On Solving a Generalized Chinese Remainder Theorem in the Presence of Remainder Errors
• Census algorithms for chinese remainder pseudorank
• A randomized sublinear time parallel GCD algorithm for the EREW PRAM

This page was built for publication: Fast arithmetics using Chinese remaindering

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