Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Нет таких алгоритмов. 20.12.04 15:06 Число просмотров: 4329
Автор: RElf <M> Статус: Member
|
> Дано число N. Пусть S будет квадратным корнем из N.
> Тогда, если N является произведением двух простых,
> наименьшее находится вычислением НОД( N, S! ), поскольку
> второй множитель будет больше S и в факториал не попадет.
> Если более двух простых, то надо проверить на простоту и
> повторить вычисления для частного и результата НОД.
> Понятно, что проблема только в том, как быстро вычислить
> факториал. Может есть подобный алгоритм как и для
> возведения в степень по модулю?
Нет таких алгоритмов.
> Мало того, факториал от большого числа очень большой
> получится. Может есть методы вычисления факториала, точнее
> не факториала, а произведения только простых, меньших
> заданного? А так же факториала по модулю.
Во-во, вычисление по модулю здесь решило бы проблему с величиной получаемых чисел, так как
НОД( N, S! ) = НОД( N, S! mod N )
Но увы, быстрых алгоритмов вычисления факториала пусть даже по модулю науке неизвестно.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
