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

Тема в разделе "WASM.A&O", создана пользователем Loger, 12 май 2005.

  1. Loger

    Loger New Member

    Публикаций:
    0
    Регистрация:
    28 авг 2003
    Сообщения:
    71
    Адрес:
    Minsk
    как-то примерно год назад мне в голову пришла идея такого алгоритма:



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

    Текущий_бит = 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<sup>0</sup>)

    p * q = m (mod 2<sup>1</sup>)

    p * q = m (mod 2<sup>2</sup>)

    ...

    p * q = m (mod 2<sup>n</sup>), где 2<sup>n</sup>>=m

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

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

    p * q <= m



    В чём прикол:

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



    Вопросы:

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

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



    Примечание:

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

    [​IMG] _2084186474__Factorize.zip
     
  2. RElf

    RElf New Member

    Публикаций:
    0
    Регистрация:
    25 дек 2004
    Сообщения:
    159
    Этот алгоритм потребует экспоненциального времени. Дело в том, что сравнение

    p * q = m (mod 2^n)

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

    Loger New Member

    Публикаций:
    0
    Регистрация:
    28 авг 2003
    Сообщения:
    71
    Адрес:
    Minsk
    RElf

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

    Stiver Партизан дзена

    Публикаций:
    0
    Регистрация:
    18 дек 2004
    Сообщения:
    812
    Адрес:
    Germany
    Loger



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







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



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



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



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

    RElf New Member

    Публикаций:
    0
    Регистрация:
    25 дек 2004
    Сообщения:
    159


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



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

    Loger New Member

    Публикаций:
    0
    Регистрация:
    28 авг 2003
    Сообщения:
    71
    Адрес:
    Minsk
    Stiver

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



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

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

    Loger New Member

    Публикаций:
    0
    Регистрация:
    28 авг 2003
    Сообщения:
    71
    Адрес:
    Minsk
    RElf

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



    искомое решение потеряно не будет, т. к. если (p (mod 2<sup>n</sup>)) * (q (mod 2<sup>n</sup>) > m (такие решения отбрасываются), то и (p (mod 2<sup>n+1</sup>)) * (q (mod 2<sup>n+1</sup>) > m и т. д.
     
  8. RElf

    RElf New Member

    Публикаций:
    0
    Регистрация:
    25 дек 2004
    Сообщения:
    159
    Опс. Я немного не так понял.



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

    p * q = m (mod 2^k)

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

    Stiver Партизан дзена

    Публикаций:
    0
    Регистрация:
    18 дек 2004
    Сообщения:
    812
    Адрес:
    Germany
    В первой колонке числа, во второй количество итераций:



    11<sup>2</sup> - 35

    101<sup>2</sup> - 220

    1009<sup>2</sup> - 2624

    10009<sup>2</sup> - 23861



    классическая картина полного перебора :)
     
  10. Loger

    Loger New Member

    Публикаций:
    0
    Регистрация:
    28 авг 2003
    Сообщения:
    71
    Адрес:
    Minsk
    RElf

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



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

    RElf New Member

    Публикаций:
    0
    Регистрация:
    25 дек 2004
    Сообщения:
    159




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







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

    Stiver Партизан дзена

    Публикаций:
    0
    Регистрация:
    18 дек 2004
    Сообщения:
    812
    Адрес:
    Germany
    Loger





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

    Loger New Member

    Публикаций:
    0
    Регистрация:
    28 авг 2003
    Сообщения:
    71
    Адрес:
    Minsk


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



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

    Loger New Member

    Публикаций:
    0
    Регистрация:
    28 авг 2003
    Сообщения:
    71
    Адрес:
    Minsk
    Stiver

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

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

    Stiver Партизан дзена

    Публикаций:
    0
    Регистрация:
    18 дек 2004
    Сообщения:
    812
    Адрес:
    Germany
    Loger



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

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

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

    интересно
     
  16. blood

    blood New Member

    Публикаций:
    0
    Регистрация:
    21 ноя 2004
    Сообщения:
    56
    Адрес:
    Russia
    Быват, что число перед факторизацией умножают на другое маленькое число. Например в факторизации методом цепных дробей. Врядли даже удачный подбор множителя сильно изменит сложность данного алгоритма..
     
  17. UbIvItS

    UbIvItS Well-Known Member

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

    1
    +
    11
    +
    110

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

    UbIvItS Well-Known Member

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

    PageFault New Member

    Публикаций:
    0
    Регистрация:
    5 мар 2007
    Сообщения:
    31
    Ну, теперь ждем когда наш гениальный математик UbIvItS осилит rsa1024.
     
  20. crypto

    crypto Active Member

    Публикаций:
    0
    Регистрация:
    13 дек 2005
    Сообщения:
    2.533
    PageFault
    Топик #17