Как быстро посчитать M! mod N?

я сейчас рою квадрат. вычеты для состовных чисел возникает много любопытных моментов - всё- таки Ферма не зря юзал формулу X^2-Y^2=N - в частных случаях из тривиального решения можно выуживать факторы: вполне возможно есть общая быстрая метода...

 

X^2-Y^2 = (X-Y)(X+Y) - это наверное и есть факторы? Глубоко...

 

Solo

сомневаешься))??

 

Приветсвую всех!


Spiteful

Мой пост будет именно о применении прототипа описанного алго софта для факторизации.
В моей реализации заложен подобный, но более укороченная по сути алго.

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

И так.
Восстанавливая сомножители из "last digit" исходного BigNum будем иметь набор "Коллизий", те. набор возможных значений сомножителей, произведение которых даст "last digit". (пока я отвлекусь замечаний по поводу выбора системы счисления). Я назвал это множество - Сечением. Мы получили Сечение 1 уровня.
На следующем уровне, те при восстановлении следующего разряда сомножителей, для произвольного элемента из предыдущего Сечения мы получаем очередное Сечение уровня 2. Дальнейшая аналогия понятна.

Таким образом выстаивается Ветвь (набор взаимосвязанных элементов Сечений по всем разрядам сомножителей А и В).

Фактически, "Коллизия" уровня n - значение А1-Аn и B1-Bn, произведение которых совпадает с n-разрядами BigNum.

Пример в dec-системе:

BIgNum 174001

Сечение 1 : 1-1 3-7 7-3 9-9

Сечение 2 для второго элемента Сечения 1

0-0 1-9 2-8 3-7 4-6 5-5 6-4 7-3 8-2 9-1

На третьем уровне будет что-то подобно:
101-3901 = 39 4001
201-3801 = 76 4001

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

Теперь давайте отметим, что на А и В накладываются некоторые ограничения:
одно из самых существенных - разрядность. Она (разрядность) не может быть больше [SQRT(BigNum)].
Очевидно по определению - иначе А и В просто меняются местами. (см. график Y=N/X)

А посему, мы будем иметь суммарное кол-во Ветвей равное 10^^(length[SQRT(BigNum)]).
10 - основание системы счисления

для приведенного примера получаем 10^^3, а для
; rsa-59 ( 196 bit )
; 71641520761751435455133616475667090434063332228247871795429 (59 Dec digits)
; B69C46078271921DC6D033B21C4F97A455EEDB83E399BB0E5 (49 Hex digits)

получаем 10^^30.
в hex-системе получаем 16^^25

Почему все так плохо? Потому что пока мы находимся на любом выше 1 и ДО max , у нас нет условий для прижигания\засушивания произвольных ветвей.

Фактически, элемент самого max по уровню Сечения можно прижечь\засушить только не найдя для него значение Вi, дающего коллизию Сi.

Именно поэтому я позволил себя назвать такое построение\алго "Метод Сi".

Итак, уничтожив некий элемент в Сечении как непригодный, выбирается следующий элемент этого Сечения и для него делается попытка выстроить новое продолжение на max уровень. Если удалось - обследуем элементы Сечения на max уровне. И снова - вниз.
Если - не удалось, прижигаем элемент и если "живых" элементов больше нет - прижигаем элемент из предыдущего Сечения, который породил засушенную часть Ветви.

Такие вот "горки" получаются...

Натурный эксперимент на числе тестовых числах и на числе Ферми
; число Ферми
; 100895598169 (dec) 177DD8A659 (hex)
показал принципиальную работоспособность.

На числе rsa-196 - полный провал.
8 старших разрядов сомножителей можно "перебирать" за вполне вменяемое время.. Возможно, что и для 4-6 младших разрядов можно как-то быстро составить "длинные" коллизии. Даже при этих гипотетических условиях остается еще очень много... Слишком много Ветвей.

Пути повышения производительности:
- первое, что приходит на ум отказаться от использования ПОЛНОГО умножения для нахождения коллизий Сi.
Пробы на сторонних библиотеках ничего хорошего не показали.
Мне пришлось написать эмулятор умножения для Dec-системы с возможностью выполнения неполного умножения. Это дало прибавку в скорости около 25% .
В принципе, можно попробовать применить частичное умножение для элемента Сечения как "базовой точки" с расчетом Сi для пары следующих разрядов.

- выявление и описание граничных условий для сомножителей. Их (граничных условий) не много, но тем не мение это очень важный ресурс в борьбе за время.

- (эта мысль совершенно свежая и пока только озвучена) эвристика сомножителей.
суть вот в чем: ни один из сомножителей не может быть подобного вида "х00000000000000х" или подобного. Здесь выйгрыш не супер-огромный, но.. все же..

Хотя все это ..в песок.. Перебрать даже банальный счетчик на 0х10 разрядов на GHz`вом компе - почти вечность.

ps/

Замечание по поводу выбора системы счисления на примере чиcла rsa-196: 10^^30 против 16^^25 или 2^^98.

 

пока что есть более перспективный эвристический метод: генерим рэндом нумберы X и тестим
X^2 mod N=Y^2. метода довольно старая, реализации могут быть различные, но, надо отметить, что не всякое X^2 mod N=Y^2 будет приводить к нетривиальным факторам. метода, впрочем, мне не нравится, так что едем дальше.............

 

UbIvItS
Ты по-моему изобретаешь велосипед. Посмотри на существующие методы:
Для начала Диксона: http://en.wikipedia.org/wiki/Dixon's_algorithm
А теперь можно квадратичное решето: http://en.wikipedia.org/wiki/Quadratic_sieve

 

maxdiver это ему уже предлагали. Он этот свой велосипед уже давно упорно изобретает.

 

UbIvItS
насчет X^2 mod N = Y^2
Любое число X меньше N^(1/2) по определению устраивает приведенному выше тождеству (т.к. X^2=Y^2).
Любое число X более N-N^(1/2) и меньшее N таким же образом дает точные квадраты при возведении в квадрат по модулю N (т.к. если X меньше корня из N, то -X будет равен по N-X - а т.к. при возведении в квадрат отрицательного значения получается значение положительное).
Вывод - вариантов масса 2*N^(1/2) - однако все они тривиальны.
Конечно можно учитывать
DMD
Можно в этой связи использовать алгоритм Карацубы

 

ECk

А кто мешает рассматривать нетривиальные варианты, когда X и Y > N?

 

В чем? В том, что это факторы или в том, что это оригинальный путь?

Есть еще путь: теорему о количестве разложений на сумму четырех квадратов знаешь? Если да, то можешь поискать целочисленные точки на четырехмерной сфере...

 

мда.. надо признать все методы убогие%)
Solo
ох, блин, думаю - это вообще путешествие в дремучий лес.
ECk

нет не все:
случай pq:
(p+q)^2/4-(p-q)^2/4, (n+1)^2/4-(n-1)^2/4;
случай pqz:
(pz+q)^2/4-(pz-q)^2/4, (p+zq)^2/4-(zq-p)^2/4, (pq+z)^2/4-(pq-z)^2/4, (pqz+1)^2/4-(pqz-1)^2/4.
CreatorCray

если б велосипеды никто не изобретал - их не было б)

 

Молодец !!! - Так держать ))

 

ссылки случайно не найдётся

 

прокомментируйте, пожалуйста, след. вопрос:
в теор. символ Якоби - это произведение символов Лежандра по простым множителям числа, а теперь вот пример:
10^2 mod 91 == 9
10^2 mod 13 == 9
10^2 mod 7 == 2
-------------------------
???????????

 

Можно, но смысла особого нет.. я и так написал быстрое (вроде) "неполное умножение".

Основной довод "против" - слишком много "конечных" элементов/ветвей.
Даже если представить, что для "конечных" элементов заменить ВСЕ проверки одним "NOP" - все равно, перебрать все допустимые комбинации сомножителя как двоичный счетчик - нереально.

Или я что-то не понял?

 

DMD
врятли из этой методы можно выжать больше для разложения нумберов, а вот попытайся её адаптировать для разложения целочисл. квадратов - любопытно какая там скорость будет.

 

t00x

Совсем случайно: http://mathworld.wolfram.com/SumofSquaresFunction.html
См. там формулу (33).

UbIvItS

Вопрос-то в чем?

 

DMD

Я не призываю ничего умножать - я говорю об использовании принципа, лежащего в основе метода Карацубы - (a*10+b)*(c*10+d)= a*c*10^2 + (a*d+b*c)*10 + b*d
Таким образом, если принять а*10 = 10 и c*10 = 10, можно исходное число уменьшить, вычтя 10*10 - получится следующее выражение:
N-(10*10) = (d+b)*10 + b*d = 10*d+10*b+b*d
Таким образом, учитывая априори известное значение последней цифры ([10*d+10*b] - последняя цифра равна 0 в силу того, что каждый множитель умножается на 10), можно найти последнюю цифру множителей выражения b*d (аналогичным твоему методом).
Найдя предполагаемую последнюю цифру b*d, можно найти предполагаемое значение последней цифры выражения b+d (а следовательно, проверить вторую цифру произведения b*d)
... и так далее (имхо, это более эффективно чем предложенный тобой метод).
http://mathworld.wolfram.com/KaratsubaMultiplication.html

 

to ECk

Я понял..
во-первых, мы думали о несколько разных вещах: ты кратко описал и дал ссылку на одно из развитий метода, а я подразумевал "базовый" метод А.А. Карацубы «Divide and Conquer» («Binary Splitting»), на чем, собственно, и основываются все дальнейшие развития "метода Карацубы". Хотя это совершенно не важно потому что сам по себе "метод А.А. Карацубы" не есть метод факторизации, а только реализация "Быстрого умножения" для применения в методах именно факторизации + см. ниже.

во-вторых,

это все здорово, но если кто-то думает что предпологаемых значений сомножителей (для любого разряда кроме первого и последнего) будет один-два-три варианта, он .. гм .. несколько заблуждается. Поэтому на каком-то шаге придется задуматься: Какой набор из "предпологаемых элементов", в моей терминологии - "Ветвь" : корректна?
И, соответственно, возникает вопрос: Как проверять результаты?
Я уже писал, что основная трудность в количестве Ветвей (те. наборов предполагаемых значений) и их финальной проверке.

Это я к

А придется...

Не хочу сказать ничего плохого.. просто хочу предложить заинтересовавшимся взять ручку и лист бумаги и на тривиальном примере 174001 оценить количество возможных значений сомножителей во втором и третьем разрядах с учетом того, что оригинальные сомножители - трех-значные и для "последный цифры" имеем всего 4 варианта/пары.
Верный ответ 191 & 911.
Затем попробуйте экстраполировать результаты для гипотетического BigNum хотя бы в 100 dec-цифр.
Это займет не более четверти часа - но сколько удовольствия получите!

Я дал анализ вполне конкретной реализации, весьма схожей с

Включая основные проблемы ей присущие.

* * *

to UbIvItS

Пожалуй.. Я ответил на просьбу прокомментировать?

* * *

ps/ если у кого-то появятся вопросы, будет что-то не понятно или будет что обсудить - я готов. Пишите или в РМ на cracklab`е.

Успехов всем!

 

RElf

вычислив символ Якоби получается, что 10 не является квадрат. вычетом 91.