Факторизация методом больного воображения

как-то примерно год назад мне в голову пришла идея такого алгоритма:



Объявления глобальных переменных:

Текущий_бит = 0

Множитель1 = 1

Множитель2 = 1

Результат = 1

Маска = 1

Произведение

Конец объявления глобальных переменных



Начало выполнения алгоритма:

Произведение = Введённое нечётное число

Вызвать функцию Рекурсивная_Факторизация



Функция Рекурсивная_Факторизация()

СдвигВлево(Маска, 1)

Текущий_бит = Текущий_бит + 1

Если ((Результат И Маска) = (Произведение И Маска)) И (Результат ≤ Произведение)) то

Если (Текущий_бит ≠ (⌈log2 Произведение⌉ – 1)) то

Вызвать функцию Рекурсивная_Факторизация

Иначе

Если ((Множитель1 ≠ 1) И (Множитель2 ≠ 1)) то

Выйти из рекурсии

Конец_Если

Конец_Если

Конец_Если

УстановитьБит(Множитель1, Текущий_бит)

Результат = Результат + СдвигВлево(Множитель2, Текущий_бит)

Если ((Результат И Маска) = (Произведение И Маска)) И (Результат ≤ Произведение)) то

Если (Текущий_бит ≠ (⌈log2 Произведение⌉ – 1)) то

Вызвать функцию Рекурсивная_Факторизация

Иначе

Если ((Множитель1 ≠ 1) И (Множитель2 ≠ 1)) то

Выйти из рекурсии

Конец_Если

Конец_Если

Конец_Если

УстановитьБит(Множитель2, Текущий_бит)

Результат = Результат + СдвигВлево(Множитель1, Текущий_бит)

Если ((Результат И Маска) = (Произведение И Маска)) И (Результат ≤ Произведение)) то

Если (Текущий_бит ≠ (⌈log2 Произведение⌉ – 1)) то

Вызвать функцию Рекурсивная_Факторизация

Иначе

Если ((Множитель1 ≠ 1) И (Множитель2 ≠ 1)) то

Выйти из рекурсии

Конец_Если

Конец_Если

Конец_Если

СброситьБит(Множитель1, Текущий_бит)

Результат = Результат – СдвигВлево(Множитель2, Текущий_бит)

Если ((Результат И Маска) = (Произведение И Маска)) И (Результат ≤ Произведение)) то

Если (Текущий_бит ≠ (⌈log2 Произведение⌉ – 1)) то

Вызвать функцию Рекурсивная_Факторизация

Иначе

Если ((Множитель1 ≠ 1) И (Множитель2 ≠ 1)) то

Выйти из рекурсии

Конец_Если

Конец_Если

Конец_Если

СброситьБит(Множитель2, Текущий_бит)

Результат = Результат – СдвигВлево(Множитель1, Текущий_бит)

Текущий_бит = Текущий_бит – 1

СдвигВправо(Маска, 1)

Конец_Функции



Как это работает:

Факторизуемое число в двоичной записи оканчивается на 1. Значит, первый бит его множителей тоже 1. Тогда попытаемся прикинуть, какими должны быть вторые биты множителей, чтобы второй бит их произведения был таким же, как и второй бит факторизуемого числа. Далее рекурсивно делаем то же самое для всех остальных битов. Фактически, тем самым мы поочерёдно находим решения уравнения

p * q = m (mod 2⁰)

p * q = m (mod 2¹)

p * q = m (mod 2²)

...

p * q = m (mod 2ⁿ), где 2ⁿ>=m

причём решение каждого базируется на решении предыдущего

А чтобы уменьшить сложность алгоритма, используется дополнительное условие

p * q <= m



В чём прикол:

Сложность факторизации зависит лишь от свойств двоичной записи множителей числа. При этом если введённое число можно разложить на два неединичных множителя несколькими способами, то найдено будет разложение, которое требует наименьшего объёма вычислений. Следствие: если мы умножим факторизуемое число на какое-то известное нам простое число, то существует вероятность того, что полученное произведение этим методом будет факторизоваться с меньшими вычислительными затратами, чем исходное, и ни один из найденых множителей не будет равен простому числу, на которое мы умножали. Тогда, разделив один из полученных множителей (какой получится разделить без остатка) на использованное ранее простое число, мы получим множители исходного числа



Вопросы:

Известен ли такой алгоритм? Или я вам открываю Америку?

Насколько практически применим этот алгоритм?



Примечание:

В проге из аттача реализация немного отличается от той, что приведена в этом посте

_2084186474__Factorize.zip

 

Этот алгоритм потребует экспоненциального времени. Дело в том, что сравнение

p * q = m (mod 2^n)

для нечетного m имеет 2^(n-1) решений, и алгоритму придется перебрать их все (рекурсивно или нет - неважно).

 

RElf

чтобы избавиться от экспоненты используется условие p * q <= m

 

Loger



код я не смотрел, опираюсь только на твое описание:

Проблема в том, что твои уравнения

для i>0 не имеют однозначного решения. Каждое такое уравнение решается двумя способами. Что в свою очередь означает, что количество вариантов в рекурсии растет с количеством битов n в геометрической прогресии: 2^n-1 Здесь есть два выхода: или проверять действительно все варианты, но тогда это будет еще медленнее(причем значительно) простого перебора. Или отсекать какие-то(ошибочные) варианты сразу, но определить, какой вариант неперспективен по последним битам невозможно.



Вывод: твой алгоритм в лучшем случае медленнее перебора, в худшем неверен. Практически непременим ни в том ни в другом случае



Добавил: когда писал, сообщения RElfа еще не было

 

Тогда с огромной вероятностью искомое решение будет потеряно.



Насчет времени работы - позапускай его на числах порядка 2^k, и посмотри как растет количество итераций алгоритма с ростом k.

 

Stiver

см. предыдущий ответ + пункт "в чём прикол"



В том, что он верен, можно убедиться на проге из аттача. На некоторых числах он оказывает медленее перебора, но у меня ещё есть несколько идей по улудшению

Можешь также протестить прогу из аттача для произведений чисел Мерсенна

 

RElf

время работы зависит лишь от последовательностей единиц в двоичной записи. например: произведение чисел Мерсенна (2ⁿ - 1)(2^k - 1) будет факторизовываться за log2((2ⁿ - 1)(2^k - 1)) операций вне зависимости от значений k и n, т. к. числа Мерсенна в двоичной записи состоят лишь из единиц



искомое решение потеряно не будет, т. к. если (p (mod 2ⁿ)) * (q (mod 2ⁿ) > m (такие решения отбрасываются), то и (p (mod 2ⁿ⁺¹)) * (q (mod 2ⁿ⁺¹) > m и т. д.

 

Опс. Я немного не так понял.



Условие p * q <= m никак не поможет для решения сравнения

p * q = m (mod 2^k)

где k<n/2, n=log2(m) - длина m. В частности, алгоритму придется перебрать порядка 2^(n/2) решения для k=n/2. Получается как минимум sqrt(m) итераций (как в случае полного перебора) плюс еще накладные расходы на рекурсию и т.п.

 

В первой колонке числа, во второй количество итераций:



11² - 35

101² - 220

1009² - 2624

10009² - 23861



классическая картина полного перебора

 

RElf

На практике минимум получается 32 итерации (для 32-битного факторизуемого числа), максимум - порядка (2^17), но ИМХО максимальную сложность ещё можно снизить хотя бы вдвое. При этом ни умножение, ни деление не используются.



Но речь не об этом. Мне бы хотелось узнать ваше мнение о мыслях, изложенных под пунктом "в чём прикол"

 

Минимум никого не интересует, как правило, интересует среднее время. То, что делений нет - тоже невелика заслуга. В методе Ферма тоже нет делений, и работает он за тот же корень.

"В чем прикол" тоже особо не поможет, так как здесь сложности теоретического плана, а не практического.

 

Loger

У тебя готового примера таких чисел случайно не будет? Или это все пока теория?

 

Ясно. Буду дорабатывать что-нить другое



Всем спасибо за внимание

 

Stiver

97 * 113 = 10961 - 265 итераций

97 * 113 * 3 = 32883 - 234 итерации, найдено разложение 339 (делим на 3 - получаем 113) * 97

 

Loger



Ага, тоже уже нашел:

5*11 = 55 - 61 итерация

3*5*11=165=15*11 - 32 итерации

интересно

 

Быват, что число перед факторизацией умножают на другое маленькое число. Например в факторизации методом цепных дробей. Врядли даже удачный подбор множителя сильно изменит сложность данного алгоритма..

 

в конце концов всё делается просто берется алгос и прокатывается на нумберах, если кодишь на с++ либу gmp я тебе дам.
кстати, порой пашет шиза след. вида m=s=n; s>>=1; m^=s; gcd(m, n); inv=~m; gcd(inv, n);
можно юзать еще одну методу - покажу ее на примере числа 25:
11001

1
+
11
+
110

одним словом на каждой итерации получаем сумму, считывая биты слева( можно и справа), получаем сумму и юзим gcd. (метода пашет далеко не всегда, так что, если RSA нумбер не раскатали, чур в меня камни в мой огород не запускать)))

 

соорудил ещё одну методу (full order) - почитать можно тут: http://xproject-all.narod.ru/factorize_numbers_rus_descrip_ver5.pdf
она сравнительно проста, абсолютно эффективна и в ряде случаев может давать очень быстрый результатат. Коль, у кого будут вопросы - задавайте.

 

Ну, теперь ждем когда наш гениальный математик UbIvItS осилит rsa1024.

 

PageFault
Топик #17