Census algorithms for chinese remainder pseudorank

David Laing; Bruce Litow

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2008)

  • Volume: 42, Issue: 2, page 309-322
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Laing, David, and Litow, Bruce. "Census algorithms for chinese remainder pseudorank." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 42.2 (2008): 309-322. <http://eudml.org/doc/245734>.

@article{Laing2008,
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 - Informatique Théorique et Applications},
keywords = {chinese remainder representation; rank; pseudorank; pseudorank census algorithms},
language = {eng},
number = {2},
pages = {309-322},
publisher = {EDP-Sciences},
title = {Census algorithms for chinese remainder pseudorank},
url = {http://eudml.org/doc/245734},
volume = {42},
year = {2008},
}

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
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/245734
ER -

References

top
  1. [1] D.J. Bernstein and J. Sorenson, Modular exponentiation via the explicit chinese remainder theorem. Math. Comp. 76 (2007) 443–454. Zbl1183.11080MR2261030
  2. [2] A. Chiu, G. Davida and B. Litow, Division in logspace-uniform NC 1 . RAIRO-Theor. Inf. Appl. 35 (2001) 259–275. Zbl1014.68062MR1869217
  3. [3] G. Davida and B. Litow, Fast parallel arithmetic via modular representation. SIAM J. Comput. 20 (1991) 756–765. Zbl0736.68040MR1105936
  4. [4] P. Dusart, The k th prime is greater than k ( ln k - ln ln k - 1 ) for k ≥ 2 . Math. Comp. 68 (1999) 411–415. Zbl0913.11039MR1620223
  5. [5] G.H. Hardy and E.M. Wright, An Introduction to the Theory of Numbers. Oxford Press, USA (1979). Zbl0423.10001MR568909JFM64.0093.03
  6. [6] D. Knuth, The Art of Computer Programming, Vol. II. Addison-Wesley (1969). Zbl0191.18001MR378456
  7. [7] W. Kuich and A. Salomaa, Semirings, Automata, Languages. Springer-Verlag (1986). Zbl0582.68002MR817983
  8. [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 Zbl1141.11324
  9. [9] A. Salomaa and S. Soittola, Automata Theoretic Aspects of Formal Power Series. Springer-Verlag (1978). Zbl0377.68039MR483721
  10. [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). Zbl1163.90694MR2437002
  11. [11] I.M. Vinogradov, Elements of Number Theory. Dover (1954). Zbl0057.28201MR62138

NotesEmbed ?

top

You 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.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.