NAU Harvester System
Оценка вычислительных затрат p-метода Полларда в зависимости от выбора отображения и начального приближения для малых факторизуемых чисел
Наукові журнали Національного Авіаційного Університету
View Archive Info| Field | Value | |
| Title |
Оценка вычислительных затрат p-метода Полларда в зависимости от выбора отображения и начального приближения для малых факторизуемых чисел
Inequality of computational effort of Pollard p-method according to dispaly selection and initial estimate for small-scale factorizable amounts Оцінка обчислювальних затрат p-методу Поларда в залежності від вибору відображення та початкового наближення для малих факторизованих чисел |
|
| Creator |
Винничук, Степан Дмитриевич; Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України.
Максименко, Евгений Васильевич; аспірант Інституту проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Мисько, Виталий Николаевич; аспірант Інституту проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
|
| Subject |
Інформаційна безпека
факторизація; p-метод Полларда; початкове наближення; відображення в кільці відрахувань; обчислювальна складність УДК 511:003.26.09 факторизация; p-метод Полларда; начальное приближение; отображение в кольце вычетов; вычислительная сложность УДК 511:003.26.09 factorizatio; Pollard p factorization method, initial estimate; presentation in the residue ring; computational complexity UDK 511:003.26.09 |
|
| Description |
Для ряда задач защиты информации криптостойкость используемых алгоритмов связана с решением вычислитель-ной задачи разложения на множители (факторизации) многоразрядных чисел. Алгоритмы современных методовфакторизации могут использовать, как составляющую часть, известные алгоритмы. Поэтому исследование свойствизвестных методов и разработка способов ускорения их работы представляется актуальной задачей. Для -метода Полларда факторизации известны общие оценки для числа итераций, но не представлены результаты исследованийпо влиянию на него начального приближения. Для оценки такого влияния предложено определять среднее число итера-ций для -метода Полларда на примере 2*107 вариантов чисел, не превышающих 231, вида N=p∙q, где p и q прос-тые. При определении средних значений числа итераций рассчитывалось суммарное число итераций по всем исследуе-мым вариантам чисел N и делилось на количество этих вариантов. Для обеспечения разложения чисел на множите-ли каждый раз, когда итерационный процесс зацикливался, константа с в полиноме увеличивалась на единицу. Прове-дены исследования по оценке среднего значения числа итераций в зависимости от выбора константы с в полиноме, реализующем итерационный процесс вида 21 ( )mod k k x x c N , а также от выбора начального приближения. Определе-но, что для исследуемых вариантов чисел среднее значение количества итераций ниже известных оценок, а за счет вы-бора начального приближения оно может быть уменьшено более чем на треть.
For a range of information security tasks the cryptostrengthof algorithms applied is linked to solving acomputational problem of multi-digit numbers factorization.Algorithms of modern factorization methods canuse existing algorithms as integral part. That is why aresearch of existing methods and development of the wayto accelerate their work is considered to be a highly topicalproblem. For Pollard p factorization method generalevaluation of iterations number is known, but the resultsof initial approximation influence study have not beenpresented. To evaluate such influence it is suggested todefine the average number of iterations for Pollard factorization method in the context of numbersoptions of 2*107 not exceeding 231, of the N=p*q type,where p and q are prime factors. While defining the averageiterations number the total iterations count for alloptions of N under study was calculated and divided bythe number of these options. To provide factoring constantc in the polynomial was increased by one wheneveriteration process ran into a cyclic path. Studies are conductedto evaluate the average iterations number dependingon the choice of constant c in the polynomial, representingiteration process 21 ( )mod k k x x c N , as well ason initial estimate. It has been defined that for the numberoptions under study the average iterations number islower than existing evaluations, and it can be decreased byone third, due to the initial estimate. Для ряду задач захисту інформації криптостійкістьвикористовуваних алгоритмів пов’язана з вирішенням обчислювальної задачі розкладання на множники (факторизації) багаторозрядних чисел. Алгоритми сучасних методів факторизації можуть використовувати, якскладову, інші відомі алгоритми. Тому дослідженнявластивостей відомих методів та розробка способівприскорення їх роботи є актуальною задачею. Для -методу Поларда факторизації відомі загальні оцінкидля числа ітерацій, але не представлені результати досліджень щодо впливу на нього початкового наближен-ня. Для оцінки такого впливу запропоновано визнача-ти середнє число ітерацій для p-метода Поларда наприкладі 2*107 варіантів чисел, що не перевищують 231,виду N=p∙q, де p и q прості. При визначенні середніхзначень числа ітерацій розраховувалось сумарне числоітерацій для всіх досліджуваних варіантів чисел N, якеділилось на число цих варіантів. Для забезпеченнярозкладання чисел на множники кожен раз, коли іте-раційний процес зациклювався, константа с в поліномі,що реалізує ітераційний процес 21 ( )mod k k x x c N ,збільшувалась на одиницю. Проведені дослідження зоцінки середнього значення числа ітерацій в заледностівід вибору константи с в поліномі, а також від виборупочаткового наближення. Визначено, що для дослі-джуваних варіантів чисел середнє значення числа іте-рацій менше ніж відомі оцінки, а за рахунок виборупочаткового наближення воно може бути зменшенебільш ніж на третину. |
|
| Publisher |
National Aviation University
|
|
| Contributor |
—
— — |
|
| Date |
2014-03-09
|
|
| Type |
—
— — |
|
| Format |
application/pdf
|
|
| Identifier |
http://jrnl.nau.edu.ua/index.php/ZI/article/view/263
10.18372/2410-7840.16.7609 |
|
| Source |
Ukrainian Information Security Research Journal; Том 16, № 4 (2014); 268
Защита информации; Том 16, № 4 (2014); 268 Захист інформації; Том 16, № 4 (2014); 268 |
|
| Language |
ru
|
|
| Rights |
Authors who publish with this journal agree to the following terms: Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
Авторы, публикующие в данном журнале, соглашаются со следующим: Авторы сохраняют за собой авторские права на работу и предоставляют журналу право первой публикации работы на условиях лицензии Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным сохранением ссылок на авторов оригинальной работы и оригинальную публикацию в этом журнале.Авторы сохраняют право заключать отдельные контрактные договоронности, касающиеся не-эксклюзивного распространения версии работы в опубликованном здесь виде (например, размещение ее в институтском хранилище, публикацию в книге), со ссылкой на ее оригинальную публикацию в этом журнале.Авторы имеют право размещать их работу в сети Интернет (например в институтском хранилище или персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу (См. The Effect of Open Access). Автори, які публікуються у цьому журналі, погоджуються з наступними умовами: Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису роботи, як до подання цього рукопису до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access). |
|