Census algorithms for chinese remainder pseudorank

Laing, David; Litow, Bruce

doi:10.1051/ita:2007024

Laing, David ; Litow, Bruce

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 2, pp. 309-322.

Résumé

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.

MR Zbl

DOI : 10.1051/ita:2007024

Classification : 11Y99, 68R99
Mots clés : chinese remainder representation, rank, pseudorank, pseudorank census algorithms

@article{ITA_2008__42_2_309_0,
     author = {Laing, David and Litow, Bruce},
     title = {Census algorithms for chinese remainder pseudorank},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {309--322},
     publisher = {EDP-Sciences},
     volume = {42},
     number = {2},
     year = {2008},
     doi = {10.1051/ita:2007024},
     mrnumber = {2401264},
     zbl = {1141.11324},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ita:2007024/}
}

TY  - JOUR
AU  - Laing, David
AU  - Litow, Bruce
TI  - Census algorithms for chinese remainder pseudorank
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2008
SP  - 309
EP  - 322
VL  - 42
IS  - 2
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita:2007024/
DO  - 10.1051/ita:2007024
LA  - en
ID  - ITA_2008__42_2_309_0
ER  -

%0 Journal Article
%A Laing, David
%A Litow, Bruce
%T Census algorithms for chinese remainder pseudorank
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2008
%P 309-322
%V 42
%N 2
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita:2007024/
%R 10.1051/ita:2007024
%G en
%F ITA_2008__42_2_309_0

Laing, David; Litow, Bruce. Census algorithms for chinese remainder pseudorank. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 2, pp. 309-322. doi : 10.1051/ita:2007024. http://archive.numdam.org/articles/10.1051/ita:2007024/

Bibliographie
Cité par

[1] D.J. Bernstein and J. Sorenson, Modular exponentiation via the explicit chinese remainder theorem. Math. Comp. 76 (2007) 443-454. | MR

[2] A. Chiu, G. Davida and B. Litow, Division in logspace-uniform ${NC}^{1}$ . RAIRO-Theor. Inf. Appl. 35 (2001) 259-275. | Numdam | MR | Zbl

[3] G. Davida and B. Litow, Fast parallel arithmetic via modular representation. SIAM J. Comput. 20 (1991) 756-765. | MR | Zbl

[4] P. Dusart, The $k$ th prime is greater than $k (ln k - ln ln k - 1)$ for $k \geq 2$ . Math. Comp. 68 (1999) 411-415. | MR | Zbl

[5] G.H. Hardy and E.M. Wright, An Introduction to the Theory of Numbers. Oxford Press, USA (1979). | JFM | MR | Zbl

[6] D. Knuth, The Art of Computer Programming, Vol. II. Addison-Wesley (1969). | MR | Zbl

[7] W. Kuich and A. Salomaa, Semirings, Automata, Languages. Springer-Verlag (1986). | MR | Zbl

[8] B. Litow and D. Laing, A census algorithm for chinese remainder pseudorank with experimental results. Technical Report. http://www.it.jcu.edu.au/ftp/pub/techreports/2005-3.pdf

[9] A. Salomaa and S. Soittola, Automata Theoretic Aspects of Formal Power Series. Springer-Verlag (1978). | MR | Zbl

[10] S.P. Tarasov and M.N. Vyalyi, Semidefinite programming and arithmetic circuit evaluation. Technical report, arXiv:cs.CC/0512035 v1 9 Dec 2005 (2005). | MR

[11] I.M. Vinogradov, Elements of Number Theory. Dover (1954). | MR | Zbl

Cité par Sources :