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

UbIvItS
>> слом рса
Опять начинаешь? ))

 

UbIvItS

ты б почитал наконец-то каких-то книжек по алгебре, теории чисел. Научился бы сам отвечать на свои "продвинутые" вопросы...

 

UbIvItS

Мне даже влом понять, что здесь имелось в виду (?? - это новый символ вроде приснопамятного oo?)

Если мне не изменяет память, у Виноградова в "Аналитической теории чисел" целый раздел посвящен исследованию решений уравнения вида
p1*x1+p2*x2+...+pn*xn = N при больших значениях N.

 

crypto
эти уравы хорошо решаются, когда x1, x2,...., xi ---> известны, а в данном случае они неизвестны - я забыл об этом упомянуть.
хотя стоп - я упомянул: разве не ясно, что "??" - это вопрос: вообще, обленился) - жара действует????

CreatorCray
я и не кончал

Solo

какие вопросы??
----------------------------------------------------------------------------
итак, чтоб всё было окончательно ясно: можно получать без труда числа: px1+qx2 (p, q, x1, x2 - неизвестны); pq==N

 

UbIvItS

Вообще-то они и являются неизвестными.
Автора я перепутал, имел в виду известную книгу А.Г.Постникова "Введение в аналитическую теорию чисел". Очень советую тебе ее прочитать (хотя бы формулировки теорем и общую канву, поскольку книга сложная, использует нетривиальные результаты из разных областей математики). А перед ней конечно же нужно проштудировать тонкую брошюрку Виноградова по теории чисел (несмотря на небольшой объем она считается классикой жанра).

 

crypto
За инфу, БОЛЬШОЕ СПАСИБО!!! - найду почитаю.

 

crypto
блин, один добрый чел. слил эту книгу в инет, но файл уже убили, если ведаешь урлос - кинь, плззззззз...ззззз

 

UbIvItS
У меня есть книга, а УРЛ поищи сам...

 

А всё таки можно на пальцах объяснить (не хочу глубоко закапываться в криптографию, но алгоритм интересен сам по себе мне суть задачи:
- RSA считает M! а затем делит на N "в лоб" и требуется найти альтернативный путь?
- или RSA считает M! mod N как нибудь хитро, но нужно ещё хитрее?
- или RSA вообще не считает M! mod N, но если суметь его посчитать, то шифровка чудом расшифруется?

 

Y_Mur
RSA эту формулу не юзает: она генерит два ключа
1. n, е - открытый
2. n, d - закрытый

-----------------------------
K^(ed) mod n==K - вот ето рса вкратце

 

кстати, система урав.
pq==n
2^phi(n) mod n ==1
видимо незамкнута.
2^phi(n) mod n ==1 ==========> n*y+1==2^phi(n)
тоесть 2 уравы и 3 неизвесных)

 

А зачем тогда вычислять M! mod N? и чем является M по отношению к K, e, d?

 

Y_Mur
gcd(M! mod N, N)>1 всегда, если M>q

 

И что из этого следует?
Меня в первую очередь интересует диапазон значений М, ведь он по идее должен иметь какие-то разумные границы? или полное множество значений из ххххх....ххх > 1024 бит?

 

нумбер разбит.
впрочем, из M! mod N выжить несяго не выйдет -слишком тормознуто..... слишком

 

Так всё таки М такое число, что М! вычислить перемножением реально? (пусть час или больше считается) просто этих М нужно много перебрать?
Или М такое, что "слишком тормознуто" подразумевает сотни лет на его вычисление?

ЗЫ: сейчас мне не интересна криптография сама по себе, но есть кое какие соображения по сабжу "Как быстро посчитать M! mod N?", чтобы их проверить нужно понять постановку задачи - "грамотная постановка задачи - половина решения"

 

Y_Mur

это может быть и 90%
так воn q<n^(1/2) ==========> gcd([n^(1/2)]! mod n, n)==q ([] - целая часть числа)
считать ломовым способом - это не сотни лет - это ж..........))

 

Итак необходимо и достаточно взять 1024 битное число, вычислить из него корень и найти остаток от деления факториала на само число?
Есть кое какие соображения - слеплю тестер - поделюсь (даже если результат будет отрицательным

 

Y_Mur
У меня, кстати, есть ассемблерный листинг функции A^N mod M (правда, битность не очень высокая), очень оптимально эту операцию выполняющая. Если хочешь, могу завтра выложить (ее еще с листинга в комп ввести нужно -))

 

crypto
Давай - пригодится