Прискорення методу Ферма методом проріджування з використання декількох баз

Анотація

В основі існуючих методів факторизації (метод решета числового поля, метод квадратичного решета) полягає принцип факторизації методом Ферма. Прискорення методу Ферма розкладання чисел виду N = pq, де p та q прості, на множники можна досягнути за рахунок проріджування пробних значень, шляхом переходу до модульного рівняння 22mod(modmod)modxBNByBB=+, де В деяка основа модуля (база). Ефективність такого підходу збільшується тоді, коли зростає база В. Збільшення бази у свою чергу веде до зростання необхідної кількості пам’яті, для збереження допустимих значень xmodВ та зростання обчислювальної складності. Збільшення обчислювальної складності разом зі збільшенням необхідного об’єму пам’яті перевищує зростання ефективності прискорення. У зв’язку з проблемами, які виникли при використанні основ більшого розміру (B), пропонується використовувати декілька основ меншого розміру. При цьому виникає задача ефективного їх вибору. У даній роботі проведено аналіз ефективності, при використанні просіювання за двома базами b1 та b2, та наведені порівнювальні характеристики з варіантом, коли використовується просіювання за однією базою B=b1*b2. Визначені умови ефективності просіювання для варіантів за однією та за двома базами.