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 -bit integers.
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/
[1] Modular exponentiation via the explicit chinese remainder theorem. Math. Comp. 76 (2007) 443-454. | MR
and ,[2] Division in logspace-uniform . RAIRO-Theor. Inf. Appl. 35 (2001) 259-275. | Numdam | MR | Zbl
, and ,[3] Fast parallel arithmetic via modular representation. SIAM J. Comput. 20 (1991) 756-765. | MR | Zbl
and ,[4] The th prime is greater than for . Math. Comp. 68 (1999) 411-415. | MR | Zbl
,[5] An Introduction to the Theory of Numbers. Oxford Press, USA (1979). | JFM | MR | Zbl
and ,[6] The Art of Computer Programming, Vol. II. Addison-Wesley (1969). | MR | Zbl
,[7] Semirings, Automata, Languages. Springer-Verlag (1986). | MR | Zbl
and ,[8] A census algorithm for chinese remainder pseudorank with experimental results. Technical Report. http://www.it.jcu.edu.au/ftp/pub/techreports/2005-3.pdf
and ,[9] Automata Theoretic Aspects of Formal Power Series. Springer-Verlag (1978). | MR | Zbl
and ,[10] Semidefinite programming and arithmetic circuit evaluation. Technical report, arXiv:cs.CC/0512035 v1 9 Dec 2005 (2005). | MR
and , ,Cité par Sources :