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

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

 

Гамма функция Эйлера

 

ECk, сэнкс.

Вообще, мне интересен даже не факториал как такавой, а M! mod N вот как енту вещь считать быстро я и думаю.

 

UbIvItS

Но тут факториал вычислять и не нужно.

 

ээ а зачем вычислять весь факториал, чтобы предсказать остаток от деления?

 

если m>q, то gcd(m! mod N, N)>1 ----> это очевидно, а вот алгос скоростного подсчёта очевиден далеко не так), впрочем, я не удивлюсь, если его нет. тот, что я знаю имеет оценку O(M) - это полная фигня.

 

M! mod N начиная с некоторого, довольно небольшого, M будет равно нулю (с какого именно, зависит от разложения числа N на простые множители). Так что если N не меняется, то можно предвычислить все в таблицу. Но если M и N у тебя порядка 10^100, то тогда не знаю.

 

Вообще говоря, сильно ускорить вычисление M! mod N при M<N в общем случае не получится.
Если бы это можно было сделать, то было бы можно сломать RSA:
Пусть N=p*q - произведение неизвестных нам простых чисел, для определенности положим p<q. Тогда p<[sqrt(N)]<q и, следовательно, НОД([sqrt(N)]! mod N,N)=p дает нам нетривильный делитель N.

Если же M>=N, то M! mod N просто равен 0. Этот факт можно использовать для такого ускорения:
Пусть нам известно разложение N на простые, тогда можно вычислить M! по модулю каждой степени простого числа, входящей в разложение N (если эта степень меньше M, то результат равен 0), а потом собрать результаты по китайской теореме об остатках.

 

что-то мне подсказывает, что это и было первоначальной целью

 

UbIvItS
Путем одновременного умножения и приведения по модулю.

 

crypto
именно об этом алгосе я и говорил - у него оценка О(M): далеко не уплывешь ----> брут форс, по сравнению с ним, шустрый заяц)

-------------------------------------------------------------------------------
Вообще, мне кажиться, что Ферма обладал методикой решения модульных уравнений, а нам достался огрызок - A^phi(N) mod N==1)

 

UbIvItS
А здесь речь об RSAшных М, N > 1024 бита?
или M, N всё таки имеют "математически разумное" значение к примеру M <= 32 или 64 бита?

 

Y_Mur

я о других числах уже и не думаю, тока xxxxxxx...xxx бит - они стали моим проклятьем) - хочу знать как раскладывать паршивцев

 

Ботай решето числового поля, ибо это самый крутой метод. Или ты хочешь ходить как лох и раскладывать числа перебором делителей (и его вариациями)?

 

halyavin
для числа на 1024 бита твоё любимое сито смотрится ещё лоховей, чем брут - форс ) - так что сакс не предлогать): вот, если б ты мне методы Ферма поведал - другое дело)

 

UbIvItS
из какого носа ты

выковырял?

 

Solo
он раскладывал большие числа и решал системы урав-ний, какие ты и с компом тарахтеть будешь) - вот и вопрос возникает -------->> КАК??!!

-------------------------------------------------------------------------------------------
я вот сейчас смотрю на дискрет. логарифм - первое, что пришло в голову по ускорению его расчёта:
2^t mod N имеет интервалы возрастания и убывания, каждый из них можно довольно быстро вычислить, сложив полученные степени двойки получим искомую степень(например, phi(N)). Но беда в том, что получаемые степени не могут быть > lg2(N), так что это шустрее брута, но для практики не прёт.

 

вот с этого места подробней, плиз. Какие числа он раскладывал?

 

Solo
почитай сам - на эту тему много материалов. Поюзай гугл яндекс и. т. д.

 

По примеру Диофанта, который оперировал числом, имевшим в длину 245 тысяч знаков, Ферма тоже использовал в своей переписке с математиками большие даже для того времени числа. В какой то период его переписки с математиками последние хотели перестать вести с ним отношения, т.к. думали, что давая в качестве примеров большие числа он хочет подшутить над ними, т.к. на первый взгляд его невозможно проверить (он доказал обратное).
При этом, он не имел калькуляторов