Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Help! Быстрое умножение по модулю... 13.02.03 19:54 Число просмотров: 6784
Автор: Persicum Статус: Незарегистрированный пользователь
|
Памажите люди добрые!
Те из вас, кто имеет теоретическую подготовку
и большой опыт работы с большими числами...
Я написал две прекрасные проги (persicum.front.ru)
но они страдают от тормознутости,
из-за того, что я не умею быстро
вычислять x*y mod z ( и x^2 mod z).
где x,y = большие целые, которые лежат в массиве
по кусочкам на 32-bit.
То есть, я их умножаю в столбик и делю в столбик.
Это просто, но требует N^2 операций.
И вдруг меня осенило - умножать
можно, скажем, через FFT, за N log N операций!
Если дополнить x и y слева нулями,
то свертка даст как раз произведение.
В общем - кто просекает проблему -
киньте ссылочек про быстрый алгоритм
(готовые библиотеки лучше не предлагать,
но тоже можно)
|
|
|
подробно о проекте
Анализ криптографических сетевых...
