SONLARNI KO‘PAYTIRISH QOIDASIGA ASOSLANGAN FAKTORIZATSIYALASH ALGORITMI

Ilkhom Boyquziyev

Authors

Boyquziyev Ilkhom Mardanoqulovich Muhammad al-Xorazmiy nomidagi Toshkent axborot texnologiyalari universiteti

Keywords:

Tub sonlar, faktorizatsiya, Tom-Kuk algoritmi, sonlarni ko‘paytirish qoidasi, Fur’e almashtirishlari, ko‘phadlar

Abstract

Ushbu maqolada faktorizatsiya masalasini hal qilish uchun katta sonlarni ko‘paytirishning Tom-Kuk algoritmi qadamlariga asoslangan xotira va hisoblash imkoniyatiga qarab o‘zgarishi mumkin bo‘lgan 200 bitli sonni faktorlash imkoniyatini beruvchi yechim taklif qilindi. Tajribalar katta sonlarni oson va tez ko‘paytirishning Shenhag-Shtrassenning ko‘phadlar va Fur’ye almashtirishlariga asoslangan algoritmi, Fyurer algoritmi, Shenhag-Shtrassenning modul arifmetikasiga asoslangan ikkinchi algoritmi, Karatsuba algoritmi kabi ko‘plab algoritmlaridan foydalanganda ham faktorizatsiya masalasini samaraliroq hal qilish mumkinligini ko‘rsatdi. O‘tkazilgan tajribalar natijalari haqida keyingi maqolalarda batafsil to‘xtalib o‘tish ko‘zda tutilgan.

References

Church, “An unsolvable problem of elementary number theory”, American Journal of Mathematics, 58 (1936), 345–363.

Barbeau,E.J. Polynomials 1st edition, Springer (2003)

Case, M. ”A beginners guide to the general number field sieve” (2003)

Crandall,R. Pomerance,C, Prime Numbers, 2nd edition, Springer (2010)

Hoffstein,J. An introduction to Mathematical Cryptography, 2nd edition, Springer (2010)

Lehmer, D.H, Powers, R.E “On Factoring Large Numbers”. Bulletin of the American Mathematical Society. 37(10): 770-776, (1931)

Mckee J. Speeding Fermat's Factoring Method. American Mathematical Society. Mathematics Computation. Volume 68, Number 228, P. 1729-1737

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

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

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

Pomerance, C. Analysis and Comparison of Some Integer Factoring Algorithms, in Computational Methods in Number Theory, Part 1, H.W. Lenstra, Jr. and R. Tijdeman, eds. Math. Centre Tract 154, p 89-139. Amsterdam, (1982)