NAU Harvester System
Acceleration of Fermat's factorization method by decimation method with use of several bases
Наукові журнали Національного Авіаційного Університету
View Archive Info| Field | Value | |
| Title |
Acceleration of Fermat's factorization method by decimation method with use of several bases
Ускорение метода Ферма методом прореживания с использованием нескольких баз Прискорення методу Ферма методом проріджування з використання декількох баз |
|
| Creator |
Місько, Віталій Миколайович; Институт проблем моделирования в энергетике им. Г.Е. Пухова НАН Украины
|
|
| Subject |
Information Security
public key cryptography; factorization; Fermat's factorization method; decimation; acceleration UDC 511:003.26.09(045) Информационная безопасность ассиметричная криптография; факторизация; метод Ферма; прореживание; ускорение УДК 511:003.26.09(045) Інформаційна безпека асиметрична криптографія; факторизація; метод Ферма; проріджування; прискорення УДК 511:003.26.09(045) |
|
| Description |
Fermat's factorization method is the basis of the existing methods of factorization (General number field sieve, Quadratic sieve). We can achieve acceleration of Fermat's factorization method, by moving to modular equation 22mod(modmod)modxBNByBB=+ where B some module (base). The effectiveness of this approach increases when increasing base B. When you increased base, you must to increase the required amount of memory to store permissible values xmodB and increase computational complexity. The increase in computational complexity with increasing the required memory bigger than growth of the efficiency of acceleration. We have many problems arising when using larger bases (B), that is why we propose to use multiple small bases. We have a problem, of effective choice of the bases. This paper analyzes the efficiency, the use of screening on two bases b1 and b2, and give comparable characteristics of the option, when used for screening one base Bb1*b2=. Described conditions for the effectiveness of screening options for one and two bases.
В основах существующих методов факторизации (метод решета числового поля, метод квадратичного решета) лежит принцип факторизации методом Ферма. Ускорение метода Ферма разложения чисел вида N =p*q, где p и q простые, на множители можно достичь за счет прореживания пробных значений, путем перехода к модульному уравнению 22mod(modmod)modxBNByBB=+, где B некоторый модуль (база). Эффективность такого подхода увеличивается с увеличением базы B. Рост базы в свою очередь ведет к росту требуемого объема памяти, для хранения допустимых значений xmodB и росту вычислительной сложности. Рост вычислительной сложности в дополнении с ростом требуемого объёма памяти превышает рост эффективности ускорения. В связи трудностями, возникающими при использовании модулей большого размера (B), предлагается использовать несколько модулей меньшего размера. При этом возникает задача эффективного их выбора. В данной работе проведен анализ эффективности, при использовании просеивания по двум базам b1 и b2, и даны сравнительные характеристики со случаем, когда используются просеивание по одной Bb1*b2=. Определены условия эффективности просеивания для вариантов по одной и по двум базам. В основі існуючих методів факторизації (метод решета числового поля, метод квадратичного решета) полягає принцип факторизації методом Ферма. Прискорення методу Ферма розкладання чисел виду N = pq, де p та q прості, на множники можна досягнути за рахунок проріджування пробних значень, шляхом переходу до модульного рівняння 22mod(modmod)modxBNByBB=+, де В деяка основа модуля (база). Ефективність такого підходу збільшується тоді, коли зростає база В. Збільшення бази у свою чергу веде до зростання необхідної кількості пам’яті, для збереження допустимих значень xmodВ та зростання обчислювальної складності. Збільшення обчислювальної складності разом зі збільшенням необхідного об’єму пам’яті перевищує зростання ефективності прискорення. У зв’язку з проблемами, які виникли при використанні основ більшого розміру (B), пропонується використовувати декілька основ меншого розміру. При цьому виникає задача ефективного їх вибору. У даній роботі проведено аналіз ефективності, при використанні просіювання за двома базами b1 та b2, та наведені порівнювальні характеристики з варіантом, коли використовується просіювання за однією базою B=b1*b2. Визначені умови ефективності просіювання для варіантів за однією та за двома базами. |
|
| Publisher |
National Aviation University
|
|
| Contributor |
—
— — |
|
| Date |
2015-04-20
|
|
| Type |
—
— — |
|
| Format |
application/pdf
|
|
| Identifier |
http://jrnl.nau.edu.ua/index.php/Infosecurity/article/view/8310
10.18372/2225-5036.21.8310 |
|
| Source |
Безпека інформації; Том 21, № 1 (2015); 64-68
Безопасность информации; Том 21, № 1 (2015); 64-68 Ukrainian Scientific Journal of Information Security; Том 21, № 1 (2015); 64-68 |
|
| Language |
uk
|
|