Аналіз прискорення методу квадратичного решета на основі рішення матриці на ходу

Автор(и)

  • Stepan Vynnychuk Інститут проблем моделювання в енергетиці ім. Г. Є. Пухова НАН України вул. Генерала Наумова, 15, м. Київ, Україна, 03164, Україна https://orcid.org/0000-0002-0605-1576
  • Vitalii Misko Інститут проблем моделювання в енергетиці ім. Г. Є. Пухова НАН України вул. Генерала Наумова, 15, м. Київ, Україна, 03164, Україна https://orcid.org/0000-0001-5952-1140

DOI:

https://doi.org/10.15587/1729-4061.2018.127596

Ключові слова:

факторизація, квадратичне решето, В-гладкі, вирішення матриці на ходу, факторна база

Анотація

Запропоновано алгоритм рішення матриці на ходу. Досліджено степінь прискорення базового методу квадратичного решета на основі вирішення матриці на ходу. Показано, що модифікований алгоритм збільшив кількість вдалих розкладань. Тобто, було зменшено кількість випадків, коли базовий квадратичного решета (при стандартному інтервалі просіюванні та розміру факторної бази) не зміг сформувати матрицю для отримання рішення

Біографії авторів

Stepan Vynnychuk, Інститут проблем моделювання в енергетиці ім. Г. Є. Пухова НАН України вул. Генерала Наумова, 15, м. Київ, Україна, 03164

Доктор технічних наук, старший науковий співробітник

Відділ автоматизації проектування енергетичних установок

Vitalii Misko, Інститут проблем моделювання в енергетиці ім. Г. Є. Пухова НАН України вул. Генерала Наумова, 15, м. Київ, Україна, 03164

Аспірант

Відділ автоматизації проектування енергетичних установок

Посилання

  1. Yan, S. Y. (2009). Primality Testing and Integer Factorization in Public-Key Cryptography. Springer, 372. doi: 10.1007/978-0-387-77268-4
  2. Gorbenko, I. D., Dolgov, V. I., Potiy, A. V., Fedorchenko, V. N. (1995). Analiz kanalov uyazvimosti sistemy RSA. Bezopasnost' informacii, 2, 22–26.
  3. Brown, D. (2005). Breaking RSA May Be As Difficult As Factoring. Cryptology ePrint Archive. Available at: https://eprint.iacr.org/2005/380
  4. Pomerance, C. (1996). A Tale of Two Sieves. The Notices of the Amer. Math. Soc., 43 (23), 1473–1485.
  5. Landquist, E. (2001). The Quadratic Sieve Factoring Algorithm. MATH 488: Cryptographic Algorithms. Available at: http://www.cs.virginia.edu/crab/QFS_Simple.pdf
  6. Ishmuhametov, Sh. T. (2011). Metody faktorizacii natural'nyh chisel. Kazan': Kazan. un., 190.
  7. Vasilenko, O. N. (2003). Teoretiko – chislovye algoritmy v kriptografii. Moscow: MCNMO, 328.
  8. Shnaer, B. (2003). Prikladnaya kriptografiya. Moscow: Dialektika, 610.
  9. Buhler, J. P. (2008). Algorithmic Number Theory. Lattices, Number Fields, Curves and Cryptography: Mathematical Sciences Research Institute Publications. Cambridge University Press, 664.
  10. Pomerance, C. (1985). The quadratic sieve factoring algorithm. Lecture Notes in Computer Science, 169–182. doi: 10.1007/3-540-39757-4_17
  11. Hoffstein, J., Pipher, J., Silverman, J. (2001). The Quadratic Sieve Factoring Algorithm. An Introduction to Mathematical Cryptography. New York, 538.
  12. Crandall, R., Pomerance, C. (2005). Prime Numbers. A Computational Perspective. New York, 597.
  13. Pomerance, C. (2008). Smooth numbers and the quadratic sieve. Algorithmic Number Theory, 69–81.
  14. Pomerance, C. (1982). Analysis and comparison of some integer factoring algorithms. In Computational Methods in Number Theory. Vol. 154. Amsterdam, 89–139.
  15. Misko, V. (2018). Pryskorennia metodu kvadratychnoho resheta na osnovi vykorystannia umovno B-hladkykh chisel. Systemni doslidzhennia ta informatsiyni tekhnolohiyi, 1.
  16. MSDN Archive. Factoring large numbers with quadratic sieve. MSDN. 2006. Available at: https://blogs.msdn.microsoft.com/devdev/2006/06/19/factoring-large-numbers-with-quadratic-sieve
  17. Vynnychuk, S., Misko, V. (2017). Pryskorennia metodu kvadratychnoho resheta na osnovi vykorystanni rozshyrenoi faktornoi bazy ta formuvannia dostatnoi kilkosti B-hladkykh chysel. Information technology and security.
  18. Pomerance, C. (1994). The number field sieve. Proceedings of Symposia in Applied Mathematics, 465–480. doi: 10.1090/psapm/048/1314884
  19. Stevenhagen, P.; Buhler, J. P., Stevenhagen, P. (Eds.) (2008). The number field sieve. Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography. Cambridge.

##submission.downloads##

Опубліковано

2018-04-03

Як цитувати

Vynnychuk, S., & Misko, V. (2018). Аналіз прискорення методу квадратичного решета на основі рішення матриці на ходу. Eastern-European Journal of Enterprise Technologies, 2(4 (92), 33–38. https://doi.org/10.15587/1729-4061.2018.127596

Номер

Том 2 № 4 (92) (2018): Математика та кібернетика - прикладні аспекти

Розділ

Математика та кібернетика - прикладні аспекти

Ліцензія

Авторське право (c) 2018 Stepan Vynnychuk, Vitalii Misko

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.

Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.