FAKTORIZATSIYALASH MUAMMOSINI BARTARAF ETUVCHI ALGORITMLAR TAHLILI

Baxtiyor Abduraximov; Ilxom Boyquziyev; O‘g‘iloy Axadova

Авторы

Baxtiyor Abduraximov Mirzo Ulug‘bek nomidagi O‘zbekiston Milliy universiteti
Ilxom Boyquziyev Muhammad al-Xorazmiy nomidagi Toshkent axborot texnologiyalari univeristeti
O‘g‘iloy Axadova Mirzo Ulug‘bek nomidagi O‘zbekiston Milliy universiteti

Ключевые слова:

Fermaning faktorizatsiya usuli, Pollardning ρ algoritmi, Tug‘ilgan kun paradoksi, Floydning siklni, topish algoritmi, Pollardning ρ-1 algoritmi, Shanksning kvadrat shakllarini faktorizatsiyasi, Eylerning faktorizatsiya usuli, Brahmagupta-Fibonachchi identifikatori

Аннотация

Ayrim kriptografik algoritmni yechishning murakkabligi ko‘pincha butun sonlarni faktorizatsiya qilish yoki diskret logarifmlash yoki bir vaqtning o‘zida ikkala masalaga asoslanadi. Butun sonlarni faktorizatsiyalashga asoslangan eng xavfsiz ochiq kalitli kriptografik algoritm berilgan kompozit sonning tub ko‘paytuvchilarini topish uchun ma’lum deterministik polinom vaqt algoritmi mavjud emasligi sababli o‘zining xavfsizlik darajasiga erishadi. Ushbu maqola butun sonlarni faktorizatsiya qilish muammosiga qaratilgan. Maqolada Fermaning faktorizatsiya usuli, Pollardning ρ algoritmi, Pollardning ρ -1 algoritmi, Shanksning kvadrat shakllarini faktorizatsiyasi va Eylerning faktorizatsiya usuli tahlili keltirilgan. Har bir algoritm qiyosiy xulosaga kelish uchun ba’zi raqamlar to‘plamida bajarilgan.

Библиографические ссылки

DIXON, J. D. Asymptotically fast factorization of integers. Mathematics of computation 36, 153 (1981), 255–260.

POLLARD, J. M. Theorems on factorization and primality testing.

In Mathematical Proceedings of the Cambridge Philosophical Society (1974), vol. 76, Cambridge Univ Press, pp. 521–528.

POMERANCE, C. A tale of two sieves. Biscuits of Number Theory

(2008), 175.

Akbarov D.Y., Xasanov P.F., Xasanov X.P., Axmedova O.P.,

Xolimtayeva I.U. “Kriptografiyaning matematik asoslari”. O‘quv qo‘llanma. –Toshkent. TATU. 2018 – 208 bet

В.Ф. Шаньгин, Информационная безопасность и защита

информации, Москва, ИД «Форум» -- Инфра-М, 2017.

Bressoud, D. M. Factorization and Primality Testing. — N. Y.:

Springer-Verlag, 1989. — 260 p. — ISBN 0-387-97040-1.

Pollard, J.M. A Monte Carlo method for factorization. BIT 15, 331-334 (1975).

Mollins, R. A brief history of factoring and primality testing B.C. (before computers) Mathematics Magazine), (2002).

Morrison, M. Brillhart, J. A Method of Factoring and the Factorization of Ϝ7. Mathematics of computation, volume 29, number 129, pages 183-205, January (1975).

Mahoney, M. S. The Mathematical Career of Pierre de Fermat. — 2. — Princeton: Princeton Univercity Press, 1994. — P. 324—332. — 438 p. — ISBN 0-691-03666-7.

Lenstra, H. W.,”Factoring integers with elliptic curves”,Annals of Math, 126: 649-673, 1987.

Nisha,S. Farik,M. RSA Public Key Cryptography Algorithm – A review. International Journal of Scientific & Technology Research. 6, (2017)