Census algorithms for chinese remainder pseudorank
RAIRO - Theoretical Informatics and Applications (2007)
- Volume: 42, Issue: 2, page 309-322
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topLaing, David, and Litow, Bruce. "Census algorithms for chinese remainder pseudorank." RAIRO - Theoretical Informatics and Applications 42.2 (2007): 309-322. <http://eudml.org/doc/92873>.
@article{Laing2007,
abstract = {
We investigate the density and distribution behaviors of the chinese remainder representation
pseudorank. We give a very strong approximation to density, and derive two efficient
algorithms to carry out an exact count (census) of the bad pseudorank integers. One of
these algorithms has been implemented, giving results in excellent agreement with
our density analysis out to 5189-bit integers.
},
author = {Laing, David, Litow, Bruce},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Chinese remainder representation; rank; pseudorank; pseudorank census algorithms},
language = {eng},
month = {8},
number = {2},
pages = {309-322},
publisher = {EDP Sciences},
title = {Census algorithms for chinese remainder pseudorank},
url = {http://eudml.org/doc/92873},
volume = {42},
year = {2007},
}
TY - JOUR
AU - Laing, David
AU - Litow, Bruce
TI - Census algorithms for chinese remainder pseudorank
JO - RAIRO - Theoretical Informatics and Applications
DA - 2007/8//
PB - EDP Sciences
VL - 42
IS - 2
SP - 309
EP - 322
AB -
We investigate the density and distribution behaviors of the chinese remainder representation
pseudorank. We give a very strong approximation to density, and derive two efficient
algorithms to carry out an exact count (census) of the bad pseudorank integers. One of
these algorithms has been implemented, giving results in excellent agreement with
our density analysis out to 5189-bit integers.
LA - eng
KW - Chinese remainder representation; rank; pseudorank; pseudorank census algorithms
UR - http://eudml.org/doc/92873
ER -
References
top- D.J. Bernstein and J. Sorenson, Modular exponentiation via the explicit chinese remainder theorem. Math. Comp.76 (2007) 443–454.
- A. Chiu, G. Davida and B. Litow, Division in logspace-uniform NC1. RAIRO-Theor. Inf. Appl.35 (2001) 259–275.
- G. Davida and B. Litow, Fast parallel arithmetic via modular representation. SIAM J. Comput.20 (1991) 756–765.
- P. Dusart, The kth prime is greater than k(lnk - lnlnk - 1) for k ≥ 2. Math. Comp.68 (1999) 411–415.
- G.H. Hardy and E.M.Wright, An Introduction to the Theory of Numbers. Oxford Press, USA (1979).
- D. Knuth, The Art of Computer Programming, Vol. II. Addison-Wesley (1969).
- W. Kuich and A. Salomaa, Semirings, Automata, Languages. Springer-Verlag (1986).
- B. Litow and D. Laing, A census algorithm for chinese remainder pseudorank with experimental results. Technical Report. URIhttp://www.it.jcu.edu.au/ftp/pub/techreports/2005-3.pdf
- A. Salomaa and S. Soittola, Automata Theoretic Aspects of Formal Power Series. Springer-Verlag (1978).
- S.P. Tarasov and M.N. Vyalyi, Semidefinite programming and arithmetic circuit evaluation. Technical report, arXiv:cs.CC/0512035 v1 9 Dec 2005 (2005).
- I.M. Vinogradov, Elements of Number Theory. Dover (1954).
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.