Anomalie w rozkładzie statystycznym dużych liczb pierwszych o zadanym najmniejszym pierwiastku pierwotnym

• Autorzy: Paszkiewicz A.

Warianty tytułu

EN

Searching anomalies in the statistical distribution of large prime numbers with a given least primitive root

• Języki publikacji: PL

Abstrakty

PL

Przedstawiono wyniki badań komputerowych dotyczących statystycznego zachowania się dużych liczb pierwszych, których najmniejszym pierwiastkiem pierwotnym jest zadana liczba naturalna niebędąca kwadratem. Eksperyment przeprowadzono z wykorzystaniem metody obliczeń rozproszonych w sieci Internet. Dla 36 przedziałów postaci dk = [10k, 10k + 109], (k=10, 11, ..., 45) wyznaczono zawarte w nich liczby pierwsze i ich najmniejsze pierwiastki pierwotne, a następnie policzono w każdym z nich częstość tych liczb pierwszych, które mają swój najmniejszy pierwiastek pierwotny równy zadanej liczbie naturalnej. Istotnym elementem pracy było przeprowadzenie samego eksperymentu obliczeniowego oraz ustalenie strategii wyboru odpowiednich metod faktoryzacji, koniecznej do wyznaczenia pierwiastka pierwotnego, zależnie od wielkości badanych liczb naturalnych w analizowanych przedziałach. Praca zawiera opis eksperymentu, użytych narzędzi oraz uzyskane wyniki.

EN

In this paper we present results of computer investigations concerning statistical behavior of large prime numbers with given least primitive root being not a square. All necessary computations were performed by the aid of distributed computing method. For 36 intervals of the form dk = [10k, 10k + 109], (k=10, 11, ..., 45) primes in these intervals were determined together with their least primitive roots. Significant and difficult element of this work was the computational experiment as well as the strategy of choice proper methods of integer factorization necessary to determine primitive roots modulo a prime. The paper contains description of experiment, tools involved and results.

Słowa kluczowe

PL

liczby pierwsze; testowanie pierwszości; faktoryzacja liczb całkowitych; metody faktoryzacji; pierwiastki pierwotne modulo liczba pierwsza

EN

prime numbers; primality testing; factorization of integers; methods of factorization; primitive roots modulo a prime

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne
• Rocznik: 2010
• Tom: nr 7
• Strony: 724--729
• Opis fizyczny: Bibliogr. 13 poz., rys., tab.

Twórcy

autor

Paszkiewicz A.

• Instytut telekomunikacji, Politechnika Warszawska,

Bibliografia

• [1] Cohen H.: A Course in Computational Algebraic Number Theory, Springer-Verlag, Berlin, 1993, Graduate Texts in Mathematics vol. 138;
• [2] Cosnard M.: Philippe J.L: The Quadratic Sieve Factoring Algorithm on Distributed Memory Multi processors, IEEE, 1990
• [3] Crandall R.: Pomerance C.: Prime Numbers. A Computational Perspective, Springer-Verlag, New York, 2000
• [4] Gajowiak Ł.: Implementacja segmentowego siki Eratostenesa i jego wykorzystanie do badania najmniejszych nie reszte kwadratowych modulo liczba pierwsza, Politechnika Warszawska praca inżynierska, Warszawa 2006
• [5] Gajowiak Ł.: Projekt i realizacja platformy do rozproszonych obliczeń inżynierskich w sieci Internet, Politechnika Warszawska, praca magi¬sterska, Warszawa 2007
• [6] Pappalardi R: On Artin's Conjecture for Primitive floote, PhD Thesis, Dept. of Math and Statistics, McGill University, Australia, 1993
• [7] Pollard J.: A Monte Carlo Method for Factorizstion, Nordisk Tidskr. Infomnations behandling (BIT), 15:331-334, 1975
• [8] Pomerance C.: The Ouadratic Sieve Factoring Algorithm, Advances in Cryptology (T. Beth, N. Cot and Ingemarrson, eds.) Lecture Notes in Comput. Sci., vol. 209, Springer-Verlag, 1985
• [9] Paszkiewicz A., Schinzel A.: On the least prime primitive root modulo a prime, Math. Comp. 71 (239)
• [10] Paszkiewicz A., Schinzel A.: Numerica lcalculation of the density of prime numbers with a given least primitive root, Malh. Comp. 71 (240)
• [11] Riesel H.: Prime Numbers and Computer Methods for Factorization, Birkhauser, Boston, 1994, Progress in Mathematics vol. 126, second ed.
• [12] Shanks D.: A Theory of Factorizations and Genera, Amer. Math. Soc. Proc. Symposia in Pure Math. 20(1971)
• [13] Silverman R.D.: The Multiple Polynomial Quadratic Sieve, Math. Comp. vol. 48, No. 177, Jan. 1987