Badania własności liczb pierwszych i wielomianów nieprzywiedlnych pod kątem zastosowania w telekomunikacji

Paszkiewicz, A.

Artykuł - szczegóły

Tytuł artykułu

Badania własności liczb pierwszych i wielomianów nieprzywiedlnych pod kątem zastosowania w telekomunikacji

Autorzy

Paszkiewicz A.

Identyfikatory

Warianty tytułu

Investigations of prime numbers and irreducible polynomials in terms of applications in telecommunications

Języki publikacji

Abstrakty

Praca stanowi obliczeniowe studium dwóch podstawowych obiektów matematycznych: liczb pierwszych i wielomianów nieprzywiedlnych pod kątem zastosowań w telekomunikacji. Oba z wymienionych obiektów pełnią podobną, podstawową rolę w teorii ciał skończonych, teorii kodowania i kryptografii. Duża część rozprawy obejmuje oryginalne wyniki autora dotyczące najmniejszych niereszt kwadratowych, najmniejszych pierwiastków pierwotnych modulo liczba pierwsza lub potęga liczby pierwszej oraz wybranych własności wielomianów nieprzywiedlnych. Autor pokazuje, jak można je wykorzystać do projektowania generatorów pseudolosowych i szyfrów. Jednym z przykładów zastosowań przywiedzionych w rozprawie jest modyfikacja algorytmu A5/1 wykorzystywanego w komunikacji GSM w celu poprawy jego mocy kryptograficznej.

This dissertation is a numerical study of two basic mathematical objects, prime numbers and irreducible polynomials, in terms of telecommunications applications. The above-mentioned objects play a similar, basic role in finite fields theory, coding theory and cryptography. A large part of the dissertation contains author's original results, concerning the least quadratic non-residues, least primitive roots of a prime or a prime power, as well as some selected properties of irreducible polynomials. The author shows how the theory can be applied in designing pseudorandom generators and stream ciphers. An example is presented - how to modify the A5/1 encryption algorithm, used in GSM communication, to improve its cryptographic strength.

Słowa kluczowe

liczby pierwsze wielomiany nieprzywiedlne ciało skończone generatory liczb pseudolosowych szyfry strumieniowe niereszty kwadratowe pierwiastki pierwotne rozproznawanie liczb pierwszych rozkład liczb naturalnych na czynniki pierwsze

prime numbers irreducible polynomials finite fields pseudorandom number generators stream ciphers quadratic non-residues primitive roots recognition of prime numbers factorizaiion of integers into prime factors

Wydawca

Oficyna Wydawnicza Politechniki Warszawskiej

Czasopismo

Prace Naukowe Politechniki Warszawskiej. Elektronika

Rocznik

2012

Tom

z. 181

Strony

3--175

Opis fizyczny

Bibliogr. 102 poz., tab. wykr.

Twórcy

autor

Paszkiewicz A.

Instytut Telekomunikacji Politechniki Warszawskiej

Bibliografia

[1] Andersen R., Roe M., A5, http://jya.com/crack-a5.htm, 1994.
[2] Babbage S., A Space/Time Tradeoff in Exhaustive Search Attacks on Stream Ciphers, European Convention on Security and Detection, IEE Conference Publication, No 408, May 1995.
[3] Bach E. Comments on search procedures far primitive roots, Math. Comp., 1997, 66, s. 1719-1727.
[4] Bartosik P., Paszkiewicz A., Badania wielomianów nierozkładalnych wysokich stopni nad GF(2) - narzędzia i wyniki. Przegląd Telekomunikacyjny, 2008, 12, s. 1059-1065.
[5] Bartosik P, Paszkiewicz A., New trinomials Xn+X+1 and Xn+X2+1 irreducible over GF(2), Electronics and Telecommunications Quarterly, 2009, 55, no. 2, s. 353-361
[6] Bartosik R, Paszkiewicz A., Wyznaczanie najmłodszych leksykograficznie wielomianów nieprzywiedlnych. Krajowe Symp. Telekomunikacji i Teleinformatyki, Bydgoszcz, 10-12 września 2008, Przegląd Telekomunikacyjny, 2008, 8-9, s. 1282-1292.
[7] Beeger N., On a new case of the congruence 2p-1 =1(mod p2), Messenger of Mathematics, 1922, 51, s. 149-150.
[8] Belino-Studziński P., Korupczyński B., Szyfr A5/A8 i jego słabości, projekt studencki wykonany w ramach przedmiotu PTKA, semestr letni. Wydział EiTl PW, Warszawa 2004,
[9] Blahut R.E., Theory and Practice of Error Correcting Codes, Addison-Wesley, Reading Massachusetts, Menlo Park, Reprinted with correction, 1984.
[10] Blake l.F, Gao S., Lambert R.J., Construction and Distribution Problems for Irreducible Trinomials over Finite Fields, D. Gollman (ed.), Oxford Univ. Press, Oxford 1996.
[11] Blum L., Blum M., Shub M, Comparisiin of two pseudo-random number generators, Advances in Cryptology, Proc. of Crypto 82, 1983, s. 61-78.
[12] Brent R.P., Larvala S., Zimmerman P., A Fast Algorithm for Testing Irreducibility of Trinomials mod 2 and some new primitive trinomials of degree 3021377, Math. Comp., 2003, 72, s. 1443-1452.
[13] Brent R.P., te Riele H.J.J., Factorizations of an±1, 13≤a≤100, Technical Report NM-R9212, Dept. of Num. Math., Centrum voor Wiskunde en Informatica, Amsterdam, June 1992.
[14] Bressoud D., Factorization and Primality Testing, Springer-Verlag, New York 1989.
[15] Briceno M., Goldberg I., Wagner D, A pedagogical implementation/AS/1, http://www.scard.org, May 1999.
[16] Brillhart J., Lehmer D.H., Selfridge J., Tuckerman B., Wagstaff S Jr., Factorization of bn ±1, b = 2, 3, 5, 6, 7, 10, 11, 12 up to high powers, Contemporary Mathematics, vol. 22. American Mathematical Society, 2 ed., 1988.
[17] Burgess D.A., On character sums and primitive roots. Proc. London Math. Soc., 1962, (3), 12, s. 179-192.
[18] Carmichael R.D., On composite numbers p which satisfy the Fermat congruence ap-1=1 mod p, Amer. Math. Monthly, 1912, 19, s. 22-27.
[19] Cohen H., A Course in Computational Algebraic Number Theory, Springer-Verlag, Berlin 1993, Graduate Texts in Mathematics, vol. 138
[20] Cosnard M., Philippe J.L, The Quadratic Sieve Factoring Algorithm on Distributed Memory Multiprocessors, IEEE, 1990, s. 254-262.
[21] Crandall R., Dilcher K., Pomerance C., A search for Wieferich and Wilson primes, Math. Comp., 1997, 66, s. 433-449.
[22] Crandall R., Pomerance C., Prime Numbers. A Computational Perspective, Springer-Verlag, New York 2000.
[23] Cusick T. W., Ding C., Renevall A., Stream Ciphers and Number Theory, Elsevier, Amsterdam 1998, North Holland Mathematical Library, vol. 55.
[24] Deleglise M., Rivat J., Computing π(x): the Meissel. Lehmer, Lagarias Miller, Odlyzko method, Math. Comp., 1996, vol. 68, No 213, s. 235-245.
[25] Elliott P.D.T.A., Murata L., On the average value of the least primitive root modulo p, J. London Math. Soc., 1997, 56 (2), s. 435-454.
[26] Gajowiak L., Implementacja segmentowego sita Eratostenesa i jego wykorzystanie do badania najmniejszych niereszt kwadrtowych modulo liczba pierwsza, praca inżynierska na Wydziale EiTI PW, Warszawa 2006.
[27] Gajowiak Ł,. Projekt i realizacja platformy do rozproszonych obliczeń inżynierskich w sieci Internet, praca magisterska na Wydziale EiTI PW, Warszawa 2007.
[28] Gathen J. von zur, Irreducible Trinomials over Finite Fields. Math. Comp., 2003, vol. 72, No 244, s. 1987-2000.
[29] Gathen J. von zur, Nöcker M., Polynomial and normal bases for finite fields, J. Cryptology, 2005, 18, s. 337-355.
[30] Gauss C.F., Disquisitions Arithmeticae. G. Fleischer, Leipzig 1801, English translation by A.A. Clarke. Springer-Verlag. New York 1986.
[31] Gliwa R., Jasiul B., Komorowski P., Leśniewicz M., Wicik R., Badania sprzętowych generatorów ciągów losowych do zastosowań kryptograficznych, XVIII KST, Bydgoszcz 2002.
[32] Golic J., Cryptanalysis of Alleged AS Stream Cipher, Proc. of Eurocrypt'97, LNCS 1223, S. 239-245, Springer-Verlag, Berlin 1997.
[33] Golomb S. W., Shifts Register Sequences, Aegean Park Press, San Francisco 1982.
[34] Gourdon X., Compilation of pi(x) improvements to the Meissel, Lehmer, Lagarias, Miller, Odlyzko. Deleglise and Rivat method, http://numbers.compulation.free.fr/Constants/ Primes/Pix/piNalgorithm.ps.
[35] Graham S.W., Ringrose C.J., Lower Bounds for Least Quadratic Non-Residues, Analytic Number Theory, Proc. in Honor of Paul T. Bateman, Progress in Mathematics 85, Birkhauser, Boston 1990, s. 269-309.
[36] Gun S., Luca F., Rath P, Sahu B., Thangadurai R., Distributions of residues modulo p, Acta Arith., 129.4 (2007), s. 325-331.
[37] Hauptmann H., Vegh E., Fisher J., Table of all primitive roots for primes less than 5000, Math. Research Center, Naval Res. Lab. Report, 7070, Washington 1970.
[38] Hołubowicz W., Płuciennik P. Cyfrowe systemy telefonii komórkowej GSM 900, GSM 1800, UMTS, 1998, wyd. III,
[39] Hooley C., On Artin‘s conjecture, J. reine und angewendte Mathematik, 1967, 225, s. 209-220.
[40] Hryciuk M., Implementacja algorytmu Mapesa do wyznaczania wartości funkcji n(x), projekt studencki, Wydział EiTI PW, Warszawa 2003.
[41] Hua L.H., Introduction to Number Theory, Springer-Verlag, Heidelberg 1982.
[42] Ireland K., Rosen M., A Classical Introduction to Modern Number Theory, Springer-Verlag, New York 1990, Graduate Texts in Mathematics, 87.
[43] Kasami T., Tokura N., Ivadari E., Inagaki J., Teoria kodirowania, Izd. Mir, Moskva 1978.
[44] Knauer J., Richstein J., Solutions of the congruence ap-1=1(mod pr), Math. Comp. 2005, 74, s. 1559-1563.
[45] Kostrikin A.I., Wstęp do algebry, Wyd. Nauk. PWN, Warszawa 2008.
[46] Kotulski Z., Generatory liczb losowych: algorytmy, testowanie, zastosowania. Matematyka Stosowana, 2001, 2.
[47] Lagarias J.C., Miller V.S., Odlyzko A., Computing π(x): the Meissel-Lehmer method, Math. Comp, 1985, 44, s. 573-560.
[48] Leśniewicz M., Sprzętowy generator ciągów losowych do zastosowań kryptograficznych, XVII KST, Bydgoszcz 2001.
[49] Lidl R., Niederreiter H., Finite Fields, Cambridge Univ. Press, Cambridge 1997.
[50] Litver E.L., Yudina G.E., Primitive roots for prime numbers of the first million and their powers, in: Matematiceskij analiz i ego prilozenijo, vol. 3, Rostov 1971, s. 106-109.
[51] Mapes D.C., Fast method for computing the number of primes less than a given limit, Math. Comp., 1963, 17, s. 179-185.
[52] Marsaglia G., Random numbers fail mainly in planes. Proc. of the Nat. Acc. of Sci., 1968, 61, s. 25-28.
[53] Matthews K.R., A generalization of Artin's of Artin's conjecture for primitive roots, Acta Arith., 1976, 29, s. 113-146.
[54] Meissner W., Über die Teilbarkeit von 2p-2 durch das Quadrat der Primzahl p=1093, Sitzungsberichte Preuss. Akad. Wiss., Berlin 1913, s. 663-667.
[55] Menezes A. et al., Handbook of applied cryptography, CRC Press, Boca Ratan 1997.
[56] Miller G.L, Riemann’s Hypothesis and tests for primality, Journal of Computer and System Sciences, 1976, 13. s. 300-317.
[57] Mister S., Adams C.M. Practical S-box design, SAC'96 - Third Annual Workshop on Selected Areas in Cryptography, Queen's University, Kingston, Ontario 1996, s. 61-76.
[58] Montgomery P.L., New solutions off ap-1= 1(mod sp2), Math. Comp., 1993, 61, s. 361-363.
[59] Moree P., Approximation of singular sense and automata, Manuscript a Mathematica, 2000, 101, s. 385-399.
[60] Mroczkowski P, Paszkiewicz A., Wykorzystanie generatora Legendre'a do konstrukcji wektorowych funkcji boolowskich typu S-box, KSTiT'2007, Bydgoszcz 2007, Przegląd Telekomunikacyjny, 2007, 8-9, s. 396-403.
[61] Murata L., On the magnitude of the least primitive root, J. Number Theory, 1991, 37, s. 47-66.
[62] Narkiewicz W., Classical Problems in Number Theory, PWN - Polish Scientific Publishers, Warszawa 1986.
[63] Nyberg K., Constructions of bent functions and difference sets, Eurocrypt'90, Springer-Verlag, 1991.
[64] Nyberg K., Perfectnonlinear S-boxe, Eurocrypt'91, Springer-Verlag, Berlin 1991.
[65] Osborn R., Tables of all primitive roots of odd primes less than 1000, Austin 1961.
[66] Paszkiewicz A., A Contribution to the Discrete Logarithm Problem, Electronics and Telecommunications Quarterly, 2009, 55, no. 3, s. 493-499.
[67] Paszkiewicz A., Irreducible pentanomials and their applications to effective implementations of arithmetic m binary fields, Electronics and Telecommunications Quarterly, 2009, 55, no. 2, s. 363-375.
[68] Paszkiewicz A., Komputerowe badania najmniejszych pierwiastków pierwotnych w dalach skończonych GF(p) dla liczb pierwszych p niniejszych od jednego miliarda, Inf. WIŁ, 1995, 15, WIŁ, wyd. wewn., s. 29-47.
[69] Paszkiewicz A., Najmniejsze pierwiastki pierwotne w ciałach skończonych. Praktyczna weryfikacja niektórych hipotez. Mat. Krajowego Symp. Telekomunikacji'95. Bydgoszcz, 6-8 września 1995, t. 3, s. 255-263.
[70] Paszkiewicz A.,A New prime p for which the the least primitive root mod p and the least primitive Root mod p2 are not equal, Math. Comp., 2009, 78, 1193-1195.
[71] Paszkiewicz A., O kilku właściwościach trójmianów nierozkładalnych nad małymi ciałami liczbowymi. Przegląd Telekomunikacyjny, 2009, 4, s. 129-135.
[72] Paszkiewicz A., On the average of the least quadratic non-residue modulo a prime number, Electronics and Telecommunications Quarterly, 2009, 55, no. 4, s. 639-647.
[73] Paszkiewicz A., On the least primitive root modulo 2p for odd primes p, Electronics and Telecommunications Quarterly, 2009, 55, no. 4, s, 649-658.
[74] Paszkiewicz A., On Least Primitive Roots mod 2p far Odd Primes p, Electronics and Telecommunications Quarterly, 2009, 55, no. 1, s. 57-69.
[75] Paszkiewicz A., O pewnej hipotezie dotyczącej wielomianów nieprzywiedlnych nad CF(2), Matematyka Stosowana, 2009, 10(51), s. 39-50.
[76] Paszkiewicz A., Projektowanie generatorów kongmencyjnych wytwarzających ciągi okresowe liczb naturalnych. Telekomunikacja i Techniki Informacyjne, 2001, 2, s. 30-45.
[77] Paszkiewicz A., Rzadkie i gęste wielomiany nierozkładalne. Mat. Krajowego Symp. Telekomunikacji'95, Bydgoszcz, 6-8 września 1995, t. B, s. 249-254.
[78] Paszkiewicz A., Some observations concerning irreducible trinomials and pentanomials over Z2, Tatra Mt. Publ., 2005, 32, s. 129-142.
[79] Paszkiewicz A., Trój.miany nieprzywiedlne nad GF(3), Przegląd Telekomunikacyjny, 2009, LXXVIII, nr 8-9, s. 1767-1774.
[80] Paszkiewicz A, Wielomiany koherencyjne dla grafów zwykłych, Biul. WAT, 2001, vol. L, nr 1, s. 149-164.
[81] Paszkiewicz A., Wielomiany nieprzywiedlne nad GF(2). Wyniki projektu badawczego. Przegląd Telekomunikacyjny, 2010, 1, 5. 19-26.
[82] Paszkiewicz A, Mroczkowski P., O pewnej metodzie projektowania silnych kryptograficznie funkcji boolowskich, Enigma 2007, XI Krajowa Konferencja Kryptografii i Ochrony Informacji, Warszawa, 23-25 maja 2007, s. 221-232.
[83] Paszkiewicz A., Schinzel A., Numerical calculation of the density of prime numbers with a given least primitive root, Math. Comp., 2001, 71 (240), s. 1781-1797.
[84] Paszkiewicz A., Schinzel A., On the least prime primitive root modulo a prime, Math. Comp., 2002, 71 (239), s. 1307-1321.
[85] Paszkiewicz A., Będziński M., Obliczenia rozproszone jako efektywne narządzie wspomagania badań w kryptografii. Przegląd Telekomunikacyjny, Wiadomości Telekomunikacyjne, 2006, 8-9, s. 245-251.
[86] Paszkiewicz A., Ziółkowski E., Metoda rozmnażania wielomianów pierwotnych i jej wykorzystanie w kryptografii, Konf. Enigma 2001, Warszawa.
[87] Pollard J., A Monte Carlo Method for Factorization, Nordisk Tidskr. Informationsbehandling (BIT), 1975, 15, s.331-334.
[88] Pomerance C., The Quadratic Sieve Factoring Algorithm, Advances in Cryptology, (T. Beth, N. Cot, I. Ingemarsson, red.) Lecture Notes in Comput, Sci., vol. 209, Springer Verlag, 1985, s. 169-182.
[89] Prachar K., Primzahherleilung, Springer-Verlag, Berlin 1957.
[90] Rachwalik T., Układ reprogramowalny w zastosowaniach do specjalnych zastosowaniach kryptograficznych, WAT, Warszawa 2006.
[91] Rachwalik T., Paszkiewicz A., Wojciechowski W., Reprogramowalny koprocesor kryptograficzny w zastosowaniu do obliczania wielomianów pierwotnych nad GF(1), RUC'03, Szczecin, 2003, s. 147-153.
[92] Rasiowa H., Wstęp do matematyki współczesnej, wyd. XIII, PWN, Warszawa 2003.
[93] Riesel H., Prime Numbers and Computer Methods for Factorization, Birkhauser, Boston 1994, Progress in Mathematics, vol. 126, second ed.
[94] Rosser J.B., Schoenfeld L., Approximate Formulas for Some Functions of Prime Numbers, III, Journ. Math., 1962, 6, s. 64-94.
[95] Roth R.M., Introduction to Coding Theory, Cambridge University Press, Cambridge 2006.
[96] Shanks D., A Theory of Factorizations and Genera, Amer. Math. Soc. Proc. Symposia in Pure Math., 1971, 20, s. 415-420.
[97] Sierpiński W., Elementary Theory of Numbers, PWN-Polish Scientific Publisher, Warszawa, North-Holland, Amsterdam 1987 (red. A. Schinzel).
[98] Silverman R.D., The Multiple Polynomial Quadratic Sieve, Math. Comp., 1987, vol. 48, No 177, s. 329-339.
[99] Wang Y., On the estimation of character sums and its applications, Sc. Record, 1964, 7, s. 78-83.
[100] Westem A.E., Miller J.C.P., Tables of lndices and Primitive Roots, Royal Society Mathematical Tables, vol. 9, Cambridge 1968.
[101] Williams H.C., Edouard Lucas and primality Testing, Wiley, New York 1998, Canadian Mathematical Soc., Series of Monographs and Advanced Texts, vol. 22.
[102] Wrench J.W., Jr, Evaluation of Artin's constant and the twin-prime constant, Math. Comp., 1961, 15, s. 396-398.

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-6897c335-efe6-4e99-ac50-66962b613535