Census algorithms for chinese remainder pseudorank

Laing, David; Litow, Bruce

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008), p. 309-322 / Harvested from Numdam

Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2008-01-01

MR 2401264 | Zbl 1141.11324

DOI : https://doi.org/10.1051/ita:2007024
Classification: 11Y99, 68R99

@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},
     volume = {42},
     year = {2008},
     pages = {309-322},
     doi = {10.1051/ita:2007024},
     mrnumber = {2401264},
     zbl = {1141.11324},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 309-322. doi : 10.1051/ita:2007024. http://gdmltest.u-ga.fr/item/ITA_2008__42_2_309_0/

Bibliographie

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

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

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

[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 1620223 | Zbl 0913.11039

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

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

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

[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 483721 | Zbl 0377.68039

[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 2437002

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