Модифікований алгоритм факторизації великих чисел методом Ферма з використанням базової основи модуля

Скорочена інформація про документ
dc.contributor.authorВиничук, Степан Дмитрович
dc.contributor.authorМаксименко, Євген Васильович
dc.date.accessioned2020-05-28T17:05:02Z
dc.date.available2020-05-28T17:05:02Z
dc.date.issued2018
dc.description.abstractМетод факторизації Ферма вважається кращим при факторизації чисел виду N = p • q у випадках коли множники p і q близькі за значенням. Обчислювальна складність базового алгоритму методу факторизації Ферма визначається кількістю пробних значень Х при вирішенні рівняння Y² = X² – N, а також складністю виконання арифметичних операцій з великими числами: зведення в квадрат, складання, обчислення квадратного кореня. Зниження обчислювальної складності зазначеного методу забезпечується за рахунок використання безлічі основ модулів в рівнянні Y²modb = (X²-N)modb, що в свою чергу дозволяє знехтувати складністю операцій обчислення квадратного кореня. Для зменшення числа пробних значень Х розглядалася можливість використання базової (первинної) основи модуля bb. Оптимальний вибір базової основи модуля bb дозволяє зменшити число пробних Х на величину, близьку за значенням до величини коефіцієнта прискорення z(N, bb) = bb/bb*, де bb* – число елементів множини коренів рівняння (Ymodb)²modb = ((Xmodb)²modb - Nmodb)modb. Показано, що в загальному випадку базова основа модуля bb є добутком ступенів простих чисел р, коефіцієнт прискорення для якого z(N, bb) є функцією Nmodp і показників ступенів р. Визначено ступінь впливу значення залишків Nmodp (в разі р=2 використовуються залишки Nmod8) і показників ступенів простих р на величину коефіцієнта прискорення z(N, bb)). Запропоновано постановку задачі пошуку оптимального значення базової основи модуля bb при обмеженнях на обсяг пам'яті ЕОМ і спосіб її вирішення. Наведено оцінку ефективності запропонованого модифікованого алгоритму методу факторизації Ферма. Встановлено, що запропонований алгоритм для чисел 2¹⁰²⁴ забезпечує зниження обчислювальної складності в порівнянні з базовим алгоритмом в середньому в 10⁷ разів. Використання запропонованого методу дозволить проектувати більш ефективні, з точки зору швидкодії, апаратно-програмні засоби проведення криптоаналізу асиметричних криптографічних алгоритмів та, як наслідок, підвищити якість оцінки криптостійкості алгоритму RSA.uk
dc.description.abstractenFermat's factorization method is considered the best at factorization the numbers N = p • q, when p and q are close in value. The computational complexity of Fermat's base factorization method is defined by the number of trial X's when solving the equation Y²=X²-N, and the complexity of arithmetic operations with large numbers: quadrating, addition, square root calculation. The decrease in computing complexity of this method is provided due to use of a set of bases of modules in Y²modb = (X²-N)modbb that in turn allows to neglect complexity of calculation square root. Allocation of primary basis of the bb module allows to reduce number of the trial X in number times close to z(N, bb) =bb/bb*, where bb* - number of roots of an equation (Ymodb)²modb=((Xmodb)² modb-Nmodb)modb. It is shown that in the general case the primary base of the module bb is the product of the degrees of prime numbers p, the acceleration factor for which z(N, bb) is the Nmodp and exponents of p. It is determined that the values of the Nmodp residues influence the value of z(N, bb) (for p=2, the Nmod8 residues are used) and exponents of simple p by the value of the acceleration coefficient z(N, bb)). It is offered problem formulation of search optimal bb with restrictions for the memory size of PC and way of it decision. An estimate of the effectiveness proposed a modified algorithm of the Fermat's factorization method is given. It is shown that offered algorithm in the case of numbers 2¹⁰²⁴ provides a decrease in computational complexity in comparing with the basic algorithm of the Fermat’s method on average of 10⁷ times. Use of the proposed method will allow developing more efficient, in terms of speed, hardware and software cryptanalysis tools for asymmetric cryptographic algorithms and, as a result, improve quality the evaluation of strong cryptography of asymmetric RSA cryptographic algorithms.en
dc.description.abstractruМетод факторизации Ферма считается лучшим при факторизации чисел вида N = p • q в случаях когда множители p и q близки по значению. Вычислительная сложность базового алгоритма метода факторизации Ферма определяется количеством пробных значений Х при решении уравнения Y² = X² – N, а также сложностью выполнения арифметических операций с большими числами: возведения в квадрат, сложения, вычисления квадратного корня. Снижение вычислительной сложности указанного метода обеспечивается за счет использования множества оснований модулей в уравнении Y²modb = (X²-N)modb, что в свою очередь позволяет пренебрегать сложностью операций вычисления квадратного корня. Для уменьшения числа пробных значений Х рассматривается возможность использования базового (первичного) основания модуля bb. Оптимальный выбор базового основания bb позволяет уменьшить число пробных Х на величину, близкую по значению к величине коэффициента ускорения z(N, bb) =bb/bb*, где bb* - число элементов множества корней уравнения (Ymodb)²modb = ((Xmodb)²modb - Nmodb)modb. Показано, что в общем случае первичное основание модуля bb является произведением степеней простых чисел р, коэффициент ускорения для которого z(N,bb) является функцией Nmodp и показателей степеней р. Определено степень влияния значения остатков Nmodp (в случае р=2 используются остатки Nmod8) и показателей степеней простых р на величину коэффициента ускорения z(N,bb)). Предложено постановку задачи поиска оптимального значения первичного основания модуля bb при ограничениях на объем памяти ЕВМ и способ ее решения. Приведена оценка эффективности предложенного модифицированного алгоритма метода факторизации Ферма. Установлено, что предложенный алгоритм для чисел 2¹⁰²⁴ обеспечивает снижение вычислительной сложности по сравнению с базовым алгоритмом в среднем в 10⁷ раз. Использование предложенного метода позволит проектировать более эффективные, с точки зрения быстродействия, аппаратно-программные средства проведения криптоанализа асимметричных криптографических алгоритмов и, как следствие, повысить качество оценки криптостойкости алгоритма RSA.ru
dc.format.extentС. 79-93uk
dc.identifier.citationВинничук, С. Модифікований алгоритм факторизації великих чисел методом Ферма з використанням базової основи модуля / Степан Винничук, Євген Максименко // Information Technology and Security. – 2018. – Vol. 6, Iss. 2 (11). – Pp. 79–93. – Bibliogr.: 10 ref.uk
dc.identifier.doihttps://doi.org/10.20535/2411-1031.2018.6.2.153492
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/33838
dc.language.isouken
dc.publisherInstitute of Special Communication and Information Protection of National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”en
dc.publisher.placeKyiven
dc.relation.ispartofInformation Technology and Security : Ukrainian research papers collection, 2018, Vol. 6, Iss. 2 (11)en
dc.subjectфакторизаціяuk
dc.subjectметод Фермаuk
dc.subjectпроріджуванняuk
dc.subjectбазова основаuk
dc.subjectобчислювальна складністьuk
dc.subjectfactorizationen
dc.subjectFermat methoden
dc.subjectthinningen
dc.subjectbase foundationen
dc.subjectcomputational complexityen
dc.subjectфакторизацияru
dc.subjectпрореживаниеru
dc.subjectбазовое основаниеru
dc.subjectвычислительная сложностьru
dc.subject.udc004.056.53::003.26.09en
dc.titleМодифікований алгоритм факторизації великих чисел методом Ферма з використанням базової основи модуляuk
dc.title.alternativeThe modified algorithm of fermat’s factorization method with base foundation of moduleen
dc.title.alternativeМодифицированный алгоритм метода факторизации Ферма с применением базового основания модуляru
dc.typeArticleen

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
ITS2018-6-2_07.pdf
Розмір:
768.52 KB
Формат:
Adobe Portable Document Format
Опис:
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
9.06 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Information Technology and Security, Vol. 6, Iss. 2 (11)