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

Скорочена інформація про документ
dc.contributor.authorВинничук, Степан
dc.contributor.authorМаксименко, Евгений
dc.contributor.authorVynnychuk, Stepan
dc.contributor.authorMaksymenko, Yevhen
dc.date.accessioned2017-12-01T14:45:29Z
dc.date.available2017-12-01T14:45:29Z
dc.date.issued2016
dc.description.abstractenOne way to ensure the specified level of information security is the use of asymmetric encryption algorithms. The cryptographic durability of such algorithms is based on the difficulty of execution the factorization problem. Modern methods of decomposition of multiple-bit sequences at factors are based on the fundamental concepts of classical Fermat's factoring algorithm. Some of the possible directions of the acceleration Fermat’s method include reducing the number of arithmetically complex operations extracting the square root. The modular division procedure using several module bases (the sieve method) allows you to exclude from consideration the options of acceptable values of X, which do not satisfy the condition Х^2 = N + Y^2. In the process of research the modification Fermat's factorization method it has been determined that it is possible to use not the pre-sieved high values of X during the search for a solution of equation Y^2 = X^2 – N, but increments to them that are the small numbers. A method of forming a non-uniform incremental data for the valid values of X relation to the basic module base during the factorization of numbers with Fermat's method is offered. It can significantly reduce the number of scanned values. Furthermore, the use of this algorithm provide not more than one addition operation of multi-bit numbers. All other operations are carried out with small numbers usually not exceeding 2^15.uk
dc.description.abstractruОдним из способов обеспечения заданного уровня защиты информации является применение алгоритмов асимметричного шифрования, криптографическая стойкость которых основана на трудности выполнения задачи факторизации. Современные методы разложения больших чисел на множители базируются на фундаментальных представлениях классического алгоритма факторизации Ферма. К числу возможных направлений ускорения метода Ферма можно отнести уменьшение количества арифметически сложных операций извлечения квадратного корня за счет реализации процедуры модульного деления с использованием нескольких оснований модуля (метод решета). Данная модификация метода позволяет исключать из рассмотрения варианты допустимых значений Х, которые не удовлетворяют условию X^2 = N + Y^2. В процессе проведенных исследований модифицированного метода факторизации Ферма было определено, что при поиске решения уравнения Y^2 = X^2 – N возможно использование не предварительно просеянных больших значений Х, а приращений к ним, являющихся малыми числами. Предложен способ формирования данных о неравномерных приращениях для допустимых значений Х относительно базового основания модуля при факторизации чисел методом Ферма, позволяющий существенно уменьшить количество проверяемых значений. Кроме того, применение данного алгоритма обеспечивает не более одной операции сложения многоразрядных чисел. Все же другие операции проводятся с малыми числами, как правило, не превышающими 2^15.uk
dc.description.abstractukОдним із способів забезпечення заданого рівня захисту інформації є застосування алгоритмів асиметричного шифрування, криптографічна стійкість яких ґрунтуэться на трудності виконання завдання факторизації. Сучасні методи розкладання великих чисел на множники базуються на фундаментальних засадах класичного алгоритму факторизації Ферма. До числа можливих напрямів прискорення методу Ферма можна віднести зменшення кількості арифметично складних операцій обчислення квадратного кореня за рахунок реалізації процедури модульного ділення з використанням декількох основ модуля (метод решета). Ця модифікація методу дозволяє виключати з розгляду варіанти допустимих значень Х, які не задовольняють умові Х^2 = N + Y^2. В процесі проведених досліджень модифікованого методу факторизації Ферма було визначено, що при пошуку рішення рівняння Y^2= X^2 – N можливе використання не самих великих значень Х, що отримано на етапі попереднього просіювання, а приростів до них, що є малими числами. Запропонований спосіб формування даних про нерівномірні прирости для допустимих значень Х відносно базової основи модуля при факторизації чисел методом Ферма, що дозволяє істотно зменшити кількість значень, що перевіряються. Крім того, застосування цього алгоритму забезпечує не більше однієї операції додавання багаторозрядних чисел. Всі інші операції проводяться з малими числами, які як правило, не перевищують 2^15.uk
dc.format.pagerangePp. 244-254uk
dc.identifier.citationВинничук С. Формирование неравномерных приращений для базового основания модуля в задаче факторизации методом Ферма / Винничук С., Максименко Е. // Information Technology and Security. – 2016. – Vol. 4, Iss. 2 (7). – Pp. 244-254. – Bibliogr.: 8 ref.uk
dc.identifier.doihttps://doi.org/10.20535/2411-1031.2016.4.2.110001
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/21311
dc.language.isoruuk
dc.publisherInstitute of special communication and information security of National technical university of Ukraine «Kyiv polytechnic institute»uk
dc.publisher.placeКиївuk
dc.sourceInformation Technology and Security : Ukrainian research papers collection, 2016, Vol. 4, Iss. 2 (7)uk
dc.subjectфакторизацияuk
dc.subjectразложение на множителиuk
dc.subjectметод Фермаuk
dc.subjectпрореживаниеuk
dc.subjectметод решетаuk
dc.subjectускорениеuk
dc.subjectфакторизаціяuk
dc.subjectрозкладання на множникиuk
dc.subjectметод Фермаuk
dc.subjectпроріджуванняuk
dc.subjectметод решетаuk
dc.subjectприскоренняuk
dc.subjectfactorizationuk
dc.subjectFermat’s factorization methoduk
dc.subjectthinninguk
dc.subjectsieve methoduk
dc.subjectaccelerationuk
dc.subject.udc003.26.09:511.1uk
dc.titleФормирование неравномерных приращений для базового основания модуля в задаче факторизации методом Фермаuk
dc.title.alternativeФормування нерівномірних приростів для базової основи модуля в задачі факторизації методом Фермаuk
dc.title.alternativeFormation of non-uniformity increment for the basic module base in the problem of Fermat’s factorization methoduk
dc.typeArticleuk

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
ITS2016.4.2(7)-12.pdf
Розмір:
561.56 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. 4, Iss. 2 (7)