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

crypto
Это бинарное возведение в степень (за O(log2(N))) или что-то более крутое?

 

maxdiver
Похоже первое (точно не скажу, под руками сейчас нет), мне код понравился (там одновременно с умножением идет приведение по модулю), я даже сначала и не понял, что там скрывается. К сожалению, битность там мелкая, но я думаю, что посмотреть в любом случае стоит.

 

crypto

это из совсем другой оперы)
Y_Mur

врятли) - отимизировать счёт M! mod N не поможет......

 

UbIvItS
А мы тебя и не спрашиваем )))

 

crypto

правде все равно спрашиваешь ты её али нет) - то, что я сказал выше остаётся в силе

 

UbIvItS
Хочешь побеждать - делай то, что противник ожидает меньше всего!
(с) Ганнибал
Поэтому не торопись с выводами, какое средство пригодится а какое нет
Любой предмет по опрелению многофункционален и есть не один, а уйма способов измерять манометром высоту зданий )

 

Y_Mur
мудрость твоя, конечно, прекрасна, но с фактами поспорить сложно) Начнём:
факториал растёт быстрей чем степень - нам же нужен остаток от точного факториала, а не от его приблежённого значения, впрочем, коли ты смогешь обойти сию преграду - цены тебе не будет, ибо число сих единицы из единиц.............

 

UbIvItS
Кто тут говорит про приближенное значение? Я еще код даже не выложил, а ты начинаешь фантазировать.
И потом, какая нах разница, что в данном случае считать - степень или факториал, программу можно модифицировать.

 

crypto
если эта та самая - за O(log2(N)), то к факториалу ее никаким боком не приткнешь

 

Nouzui
Я имел в виду использование идеи одновременного перемножения и приведения по модулю.

 

crypto
а енто как?

 

Nouzui
Выложу код - посмотришь, постараюсь сегодня вечером это сделать.

 

Nouzui
обычно это делается через montgomery multiplication

 

все, я в ауте

 

Вот, набросал пример:

Код (Text):

1. BigNumber Factorial (BigNumber value, const BigNumber &modulus)
2. {
3.     DWORD mu = BigNumber::PrecalcMontgomeryMU (modulus);
4.     BigNumber res, Rm1, vRm1;
5.  
6.     // Calc normalization
7.     Rm1.setBit(2*modulus.getNumChunks()*BIGNUMBER_CHUNK_BITS);
8.     Rm1.FromURemainder(Rm1,modulus);
9.    
10.     // Multiply first value
11.     res.FromUMulModMontgomery(Rm1,value,modulus,mu);
12.     value.UDecrement (1);
13.  
14.     while (value.UCmp (1))
15.     {
16.         // convert value to montgomery form
17.         vRm1.FromUMulModMontgomery(value,Rm1,modulus,mu);
18.         // Multiply
19.         res.FromUMulModMontgomery(res,vRm1,modulus,mu);
20.         value.UDecrement (1);
21.     }
22.  
23.     // Denormalize
24.     vRm1.UAssign (1);
25.     res.FromUMulModMontgomery(res,vRm1,modulus,mu);
26.  
27.     return res;
28. }

Могу выложить скомпиленный вариант для тестов

 

CreatorCray
выложи лучше сам BigNumber - в первый раз вижу такой класс ))

 

Самописный + он в составе либы, части которой в нем используются.
Может проще выложить FromUMulModMontgomery + PrecalcMontgomeryMU
Остальные функции достаточно стандартные

ЗЫ: Я кстати не уверен что через montgomery будет быстрее - тут 2 умножения на каждое число за счет того что надо преобразовывать их в mongomery form. Щас набросаю тестик.

 

лучше уж тогда просто описание Montgomery. впрочем, сам найду, если интерес пересилит лень \

 

Как показали полевые испытания:

65536! mod prime(2048)

Mont: (4.820776 sec) 13'498'609'194 ticks
Barr: (0.284845 sec) 797'594'224 ticks

Вот этот код выигрывает

Код (Text):

1. BigNumber FactorialBarr (BigNumber value, const BigNumber &modulus)
2. {
3.     BigNumber mu = BigNumber::PrecalcBarretReduction (modulus);
4.     BigNumber res (1);
5.  
6.     while (value.UCmp (1))
7.     {
8.         // Multiply
9.         res.FromUMul (res,value);
10.         res.FromBarrettReduction (res, modulus, mu);
11.         value.UDecrement (1);
12.     }
13.  
14.     return res;
15. }

Так что montgomery multiplication ИМХО следует оставить только для montgomery exponentiation, где он рулит нипадеццки.

 

С английским надеюсь проблем нет

Блин, что за фигня - аттачи не закачиваются.
см тут: http://rapidshare.com/files/39821495/montgomery_barrett.pdf.html