Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Ну если такой алгоритм науке неизвестен, то надо его сочинить - пусть будет знать. 20.12.04 18:01 Число просмотров: 4628
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 23.12.04 12:33 Количество правок: 2
|
> Нет таких алгоритмов.
> Во-во, вычисление по модулю здесь решило бы проблему с
> величиной получаемых чисел, так как
> НОД( N, S! ) = НОД( N, S! mod N )
> Но увы, быстрых алгоритмов вычисления факториала пусть даже
> по модулю науке неизвестно.
Я его тоже пока нигде не нашел, но полагаю, что он может существовать.
Хочу попробовать его вывести. Есть же алгоритм для арифметичесой/геометрической прогрессии.
Здесь почти то же самое, только не складывать, а умножать надо.
Хочу пойти тем же путем. Формулу придумать вряд ли пролучится, хотя может потом как нибудь удастся свернуть алгоритм в формулу.
По аналогии с прогрессиями можно рассмотреть пример:
16! = 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16
16! = (1*16(2*15)*(3*14)*(4*13)*(5*12)*(6*11)*(7*10)8*9)
16! = 16 * 30 * 42 * 52 * 60 * 66 * 70 * 72
Если сравнить последовательность "1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16" с "16*30*42*52*60*66*70*72", то можно вывести общуу закономерность.
Думается мне, что можно свернуть произведение натурального ряда поэтапно до нескольких сомножителей. Ряды на каждом этапе возрастающие. Причем присутствует отрицательная вторая производная. Похоже можно вычислять коэффициенты уравнения что-то типа "x+ky+lz^m" из предыдущей последовательности, заданной той же формулой с предыдущими коэффициентами. И еще запоминать последний множитель, если их количество нечетное.
Итого сложность будет логарифм от N по основанию 2. Для килобитного числа всего тысяча вычислений коэффициентов.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
