Многократное прореживание для ускорения метода факторизации ферма при неравномерных шагах для неизвестной

Скорочена інформація про документ
dc.contributor.authorВинничук, С. Д.
dc.contributor.authorМаксименко, Е. В.
dc.contributor.authorVynnychuk, S.
dc.contributor.authorMaksymenko, E.
dc.date.accessioned2017-08-28T12:46:53Z
dc.date.available2017-08-28T12:46:53Z
dc.date.issued2016
dc.description.abstractenThe way for accelerating Fermat's method of numbers factorization was offered due to the decimation of trial values of unknown X using a set of the bases of the module in which the essential role belongs to the allocated basic basis of the bb module. The basic basis is selected from the condition of maximum bb relationship to the number of those Xmodbb, for which the difference X2 - N is a quadratic residue by mod bb (permissible Xmodbb) and available RAM of computer. Based on bb the list of steps of variable length between the the nearest largest permissible Xmodbb is formed. The algorithm of MR realizing the decimation of trial values is described. For the most frequently performed steps of the algorithm of MR the fragment of a program code in language C is presented. The results of numerical experiments for the decomposition of numbers on the factors which are the product of two primes such that the ratio of highest to lowest does not exceed 4. It is shown that using only the decimation procedure of trial values, the time expenses in solving the problem of decomposition into factors is always proportional to the number (p + q)/2 - N1/2, where N = pq. They significantly depend on the choice of the basic basis of the module and a set of other bases of modules.uk
dc.description.abstractruПредложен способ ускорения метода Ферма факторизации чисел за счет прореживания пробных значений неизвестной Х при использовании множества оснований модуля, в котором существенная роль принадлежит выделяемому базовому основанию модуля bb. Базовое основание выбирается из условия максимума отношения bb к числу тех из Xmodbb, для которых разница X2 – N является квадратичным остатком по модулю bb (допустимые Xmodbb) и доступной оперативной памяти ЭВМ. На основании bb формируется список шагов переменной длины между ближайшими по величине допустимыми Xmodbb. Описан алгоритм МР, реализующий прореживание пробных значений. Для наиболее часто выполняемых шагов алгоритма МР представлен фрагмент программного кода на языке С. Представлены результаты численных экспериментов по разложению чисел на множители, являющихся произведением двух простых таких, что отношение большего к меньшему не превосходит 4. Показано, что при использовании только процедуры прореживания пробных значений временные затраты при решении задачи разложения на множители всегда пропорциональны числу (p+q)/2 – N1/2, где N=pq. Они существенно зависят от выбора базового основания модуля и множества других оснований.uk
dc.format.pagerangeС. 13-24uk
dc.identifier.citationВинничук С. Д. Многократное прореживание для ускорения метода факторизации ферма при неравномерных шагах для неизвестной / Винничук С. Д., Максименко Е. В. // Вісник НТУУ «КПІ». Інформатика, управління та обчислювальна техніка : збірник наукових праць. – 2016. – Вип. 64. – С. 13–24. – Бібліогр.: 6 назв.uk
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/20422
dc.language.isoruuk
dc.publisherВЕК+uk
dc.publisher.placeКиївuk
dc.sourceВісник НТУУ «КПІ». Інформатика, управління та обчислювальна техніка : збірник наукових праць, Вип. 64uk
dc.status.pubpublisheduk
dc.subjectфакторизацияuk
dc.subjectметод Фермаuk
dc.subjectпрореживаниеuk
dc.subjectускорениеuk
dc.subject.udc511:003.26.09uk
dc.titleМногократное прореживание для ускорения метода факторизации ферма при неравномерных шагах для неизвестнойuk
dc.title.alternativeRepeated decimation for accelerating the factorization Fermat's method with uneven steps for the unknownuk
dc.typeArticleuk
thesis.degree.level-uk

Файли

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

Зібрання

Вісник НТУУ «КПІ». Інформатика, управління та обчислювальна техніка: збірник наукових праць, Вип. 64