On the average of the least quadratic non-residue modulo a prime number

• Autorzy: Paszkiewicz A.
• Języki publikacji: EN

Abstrakty

EN

In this paper we focus on a problem of existence the mean value of the least quadratic non-residue modulo a prime number. We prove that the answer to that question is positive and calculate the exact value of that constant with high accuracy. We also prove that the density of all primes having its least quadratic non-residue equal to k-th prime is 1/2k. Some computational results are included to provide numerical arguments that the convergence is very fast.

Słowa kluczowe

EN

east quadratic non-residue; multiplicative group modulo a prime number; least primitive root; primality testing algorithms

PL

matematyka; arytmetyka modulo; multiplikatywna grupa modulo; liczby pierwsze; pierwiastki pierwotne; algorytm prymalny

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: Electronics and Telecommunications Quarterly
• Rocznik: 2009
• Tom: Vol. 55, No 4
• Strony: 639--647
• Opis fizyczny: Bibliogr. 10 poz., wykr.

Twórcy

autor

Paszkiewicz A.

• Warsaw University of Technology,

Bibliografia

• 1. R. Crandall, C. Pomerance: Prime Numbers, a Computational Perspective, Springer Verlag New York, Berlin, 2001.
• 2. P. D. T. A. Elliott, L. Murata: On the average value of the least primitive root modulo p, J. London Math. Soc. 56 (2), pp. 435-454, 1997.
• 3. V. R. Friedlander: On the least n-th power non-residue, Dokl. Akad. Nauk SSSR 66, pp. 351-352, 1949.
• 4. S. W. Graham, C. J. Ringrose: Lower bounds for least quadratic non-residues, Analytic Number Theory, Proceedings in Honor of Paul T. Bateman, Progress in Mathematics 85, Birkhäuser, Boston, pp. 269-309, 1990.
• 5. K. Ireland, M. Rosen: A Classical Introduction to modern Number Theory, Springer-Verlag, New York, Heidelberg, Berlin, 1982, Graduate Texts in Mathematics, 87.
• 6. A. Menezes et all: Handbook of Applied Cryptography, CRC Press, Boca Raton, 1997
• 7. H. L. Montgomery: Topics in Multiplicative Number Theory, Lecture Notes in Math. Springer Verlag, New York, 1971.
• 8. H. Riesel: Prime Numbers and Computer Methods for Factorizations, 2nd ed., Birkhauser, Boston, Basel, Berlin 1994.
• 9. H. Salie: Über den kleinsten positiven quadratischen Nichtrest nach einer Primzahl, Math. Nachr. 3, pp. 7-8, 1949.
• 10. R. M. Solovay, V. Strassen: A fast Monte-Carlo test for primality, SIAM Journal on Computing, 6(1), pp. 84-85, 1971.