Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Быстрый алгоритм факторизации, возможна ли реализация? 20.12.04 12:00 Число просмотров: 6296
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 20.12.04 12:03 Количество правок: 1
|
Дано число N.
Пусть S будет квадратным корнем из N.
Тогда, если N является произведением двух простых, наименьшее находится вычислением НОД( N, S! ), поскольку второй множитель будет больше S и в факториал не попадет.
Если более двух простых, то надо проверить на простоту и повторить вычисления для частного и результата НОД.
Понятно, что проблема только в том, как быстро вычислить факториал. Может есть подобный алгоритм как и для возведения в степень по модулю?
Мало того, факториал от большого числа очень большой получится. Может есть методы вычисления факториала, точнее не факториала, а произведения только простых, меньших заданного? А так же факториала по модулю.
|
- Быстрый алгоритм факторизации, возможна ли реализация? - DPP 20.12.04 12:00 [6296]
|
|
|
подробно о проекте
Анализ криптографических сетевых...
