Fast arithmetics using Chinese remaindering

DOI10.1016/J.IPL.2009.02.024zbMATH Open1215.68268arXiv0806.1722OpenAlexW1972292206MaRDI QIDQ989447FDOQ989447

Authors: George Davida, Bruce Litow, Guangwu Xu 

Publication date: 20 August 2010

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

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$.

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

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

zbMATH Keywords

parallel algorithmChinese remaindering representation

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Log Depth Circuits for Division and Related Problems
• Division in logspace-uniform NC
• Fast Parallel Arithmetic via Modular Representation
• Title not available (Why is that?)
• GCD of random linear combinations
• Integer division in residue number systems

Cited In (6)

• On Solving a Generalized Chinese Remainder Theorem in the Presence of Remainder Errors
• A randomized sublinear time parallel GCD algorithm for the EREW PRAM
• Census algorithms for chinese remainder pseudorank
• A note on Chang-Lai's modular square algorithm based on the generalized Chinese remainder theorem
• Modular exponentiation via the explicit Chinese remainder theorem
• Title not available (Why is that?)

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)