Fast Arithmetics Using Chinese Remaindering

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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 $\log n$.

Keywords

Data Structures and Algorithms, G.1.0

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/162630

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0806.1722
 http://arxiv.org/abs/0806.1722

Collections

arXiv