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

Скорочена інформація про документ
dc.contributor.authorВинничук, Степан Дмитрович
dc.contributor.authorМісько, Віталій Миколайович
dc.contributor.authorVynnychuk, Stepan
dc.contributor.authorMisko, Vitalii
dc.date.accessioned2018-07-18T08:30:50Z
dc.date.available2018-07-18T08:30:50Z
dc.date.issued2017
dc.description.abstractenIn information and telecommunication systems, RSA algorithms are often used to solve information security problems. At the core of the cryptostability of the most popular today asymmetric cryptographic algorithm RSA is the complexity of the factorization of large integers. Quadratic sieve method is the best for factorization of integers under 110 decimal digits or so. The most time consuming part of the algorithm of a quadratic sieve is the sieving process. The size of the factor base is one of the key parameters that determine the effectiveness of the sieving algorithm. Too large factor base requires the search for a large number of B–smooth numbers, which increases the total execution time of the algorithm. When the size is less than necessary, it will not be possible to find a sufficient number of B–smooth numbers. In this paper, the method for determining and applying a sufficient size of B–smooth numbers with doubling the factor base size in comparison with the basic algorithm of a quadratic sieve is proposed. With the expansion of the factor base, the number of N numbers increases, which can be decomposed into factors by the quadratic sieve method. It is also noted that its increase leads to an increase in computational complexity, since it is advisable to find a greater number of B–smooth numbers. However, when conducting numerical experiments, where the size of the factor base increased twice, it turned out that using the proposed algorithm, the time necessary to find a sufficient number of B-smooth numbers, on the contrary, decreased.uk
dc.description.abstractruВ информационно-телекоммуникационных системах для решения задачи защиты информации часто используют RSA алгоритм. В основе криптостойкости наиболее популярного сегодня ассиметричного криптоалгоритма RSA лежит сложность факторизации больших целых чисел. Метод квадратичного решета является лучшим методом факторизации чисел, размером меньше 110 десятичных знаков. Наиболее затратной по времени частью алгоритма квадратичного решета является процесс просеивания. Размер факторной базы – это один из ключевых параметров, который определяет эффективность алгоритма просеивания. Большой размер факторной базы требует поиска большого количества В–гладких чисел, что увеличивает общее время выполнения алгоритма. Когда размер меньше необходимого, тогда не удастся найти достаточного количества В-гладких чисел. В данной статье предложено метод определения и использования достаточного размера В-гладких чисел, при увеличении размера факторной базы вдвое, в сравнении с базовым алгоритмом квадратичного решета. При расширении факторной базы увеличивается количество чисел N, которые можно разложить на множители методом квадратичного решета. Отмечается также, что её увеличение приводит к росту вычислительной сложности, поскольку целесообразно находить большее количество В–гладких чисел. Но, при проведении численных экспериментов, где размер факторной базы увеличивается вдвое, обнаружено, что с использованием предложенного алгоритма время, необходимое для поиска достаточного количества В–гладких чисел, наоборот уменьшается.uk
dc.description.abstractukВ інформаційно-телекомунікаційних системах для рішення задачі захисту інформації часто використовують RSA алгоритм. В основі криптостійкості найбільш популярного сьогодні асиметричного криптоалгоритму RSA є складність факторизації великих цілих чисел. Метод квадратичного решета є найкращим відомим методом факторизації чисел, розміром менше 110 десяткових знаків. Найбільш затратною за часом частиною алгоритму квадратичного решета є процес просіювання. Розмір факторної бази – це один з ключових параметрів, що визначають ефективність алгоритму просіювання. Надто великий розмір факторної бази потребує пошуку великої кількості В-гладких чисел, що збільшує загальний час виконання алгоритму. Коли розмір менший за необхідний, не вдасться знайти достатню кількість В-гладких чисел. У даній статті запропоновано метод визначення та застосування достатнього розміру В-гладких чисел при збільшенні розміру факторної бази вдвічі в порівнянні з базовим алгоритмом квадратичного решета. При розширенні факторної бази збільшується кількість чисел N, які можна розкласти на множники методом квадратичного решета. Відмічається також, що її збільшення призводить до росту обчислювальної складності, оскільки доцільно знаходити більшу кількість В-гладких чисел. Проте при проведенні чисельних експериментів, де розмір факторної бази збільшувався двічі, виявилося, що з використанням запропонованого алгоритму час, необхідний для пошуку достатньої кількості В-гладких чисел, навпаки зменшувався. За результатами обчислень встановлено, що при використанні вдвічі розширеної факторної бази час, необхідний для формування достатньої кількості елементів факторної бази зменшився на 29%, загальна кількість пробних значень, що досліджуються, із інтервалу просіювання при знаходженні В-гладких чисел зменшилася в 2,85 рази.uk
dc.format.pagerangeС. 67-75uk
dc.identifier.citationВинничук, С. Удосконалення методу квадратичного решета на основі використання розширеної факторної бази та формування достатньої кількості В - гладких чисел / Степан Винничук, Віталій Місько // Information Technology and Security. – 2017. – Vol. 5, Iss. 2 (9). – Pp. 67–75. – Bibliogr.: 8 ref.uk
dc.identifier.doihttps://doi.org/10.20535/2411-1031.2017.5.2.136966
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/23948
dc.language.isoukuk
dc.publisherInstitute of Special Communication and Information Protection of National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”uk
dc.publisher.placeKyivuk
dc.sourceInformation Technology and Security : Ukrainian research papers collection, 2017, Vol. 5, Iss. 2 (9)uk
dc.subjectквадратичне решетоuk
dc.subjectрозширена факторна базаuk
dc.subjectдостатня кількість В-гладкихuk
dc.subjectінтервал просіюванняuk
dc.subjectпрості числаuk
dc.subjectquadratic sieveuk
dc.subjectextended factor baseuk
dc.subjectavailable quantity of B-smoothuk
dc.subjectsieving intervaluk
dc.subjectprime numbersuk
dc.subjectквадратичное решетоuk
dc.subjectрасширенная факторная базаuk
dc.subjectдостаточное количество В-гладкихuk
dc.subjectинтервал просеиванияuk
dc.subjectпростые числаuk
dc.subject.udc003.26:511.337uk
dc.titleУдосконалення методу квадратичного решета на основі використання розширеної факторної бази та формування достатньої кількості В - гладких чиселuk
dc.title.alternativeImprovement of the quadratic sieve method on the basis of the extended factor base and using available quantity of B – smooth numbersuk
dc.title.alternativeУсовершенствование метода квадратичного решета на основе использования розширенной факторной базы и формирования достаточного количества В-гладких чиселuk
dc.typeArticleuk

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
ITS2017.5.2(9)_08.pdf
Розмір:
634.44 KB
Формат:
Adobe Portable Document Format
Опис:
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
7.74 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Information Technology and Security, Vol. 5, Iss. 2 (9)