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

CreatorCray
ты хоть комментарии поставь, плззззззз, я лично енту либу, кою ты юзаешь, первый раз вижу)

 

я так понимаю - речь идёт о таком коде(??):
int fact=1, factmod=1, n,factorial, i=0;
cin>>n;
cin>>factorial;
while(i<factorial){
fact++;
factmod*=fact;
factmod%=n;
}

 

UbIvItS
>> ты хоть комментарии поставь, плззззззз, я лично енту либу, кою ты юзаешь, первый раз вижу
Разумеется первый раз видишь - либа то самописная )

Комментарии для людей, которые знают что такое montgomery multiplication практически не нужны. Для тех же кто не знает - надо объяснять всю теорию.
Там дальше я кусок из книги запостил - считай что это и есть комменты.

>> речь идёт о таком коде
Ну не совсем таком, но где то близко.

Вообще, если тебе надо алгоритм факториала, отличный от классического, попробуй воскурить mpz_fac_ui из GMP. Только на мой взгляд ее писали по конкретной укурке.

 

CreatorCray

в топку етот код в топку) - метод тупого перебора и то быстрей факторизировать будет) - аля на порядок.

 

UbIvItS
>> метод тупого перебора и то быстрей факторизировать будет
А как ты собрался факторизовать с помощью вычисления факториала?

Я вообще то набросал код вычисления факториала с применением того самого загадочного

Откуда ты применение его к факторизации вытянул - не понятно.

 

Кстати, ты все еще паришься разработкой собственного алгоритма разложения на множители?
Чем тебя MPQS не устраивает? Быстрее его вроде как нету ничего покуда...

 

CreatorCray
проблемы с английским есть.. )
за ссылку спасибо

 

Nouzui
могу всю книгу выложить
+ еще несколько других

 

CreatorCray

я об этом уже говорил - смотри более рание топики.

об этом я тоже говорил: сита прожорливы по памяти и на 1024 битах они смешней выглядят, чем тупой перебор возможных делителей)

 

UbIvItS
>> сита прожорливы по памяти и на 1024 битах они смешней выглядят, чем тупой перебор возможных делителей

Ну ну...
Был как то в RU.CRYPT такой товарищ: Юрий Решетов, так вот ты мне его напоминаешь. )

 

CreatorCray
считай: 2гб на 512 бит требуется - теперь посчитай на 1024 бит) - неправда ли внушает), а ведь надо матрицу ещё и сформировать

 

UbIvItS
Потребление памяти - плата за использование самого быстрого алгоритма. Впрочем, если уж замахиваешься на факторизацию 1024 битного, то будь добр соответствуй аппаратно.

 

CreatorCray

ну, ты отколол))) - найди мне такие ресурсы)

 

UbIvItS
Неси деньги )

 

CreatorCray

нафиг(??)- эти ресурсы лишь в твоих мечтах), лучше я поищу алгос - могет он есть. к тому же, допустим 512 бит колется за 8 деньков - вопрос на засыпку: скока будет биться 1024 бит. вопрос на засыпку номер два: какой дурак юзает ключ на 1024 вместо 2048 бит?????????)

 

UbIvItS
Ну по приблизительным оценкам RSA Labs для этого понадобится ~6 терабайт памяти - в принципе довольно таки реально хотя и безумно дорого и долго...

Успехов в поисках

 

CreatorCray
спасибо -тебе тоже УДАЧИ!!!!!!!!!!!!

 

М-да, обещал, а нашел только один листок (из двух), хотя никогда их не выкидывал, хранил... Ну да ладно, получается задача с нахождением окончания процедуры (если я, конечно, второй листок не найду), да может и не стоит на этот код смотреть.
ЗЫ
Я уж и не помню, что там и как, думается, профи поймут без труда
Адреса последних меток специально указал, может это облегчит задачу.

Код (Text):

1.     mov edx, dword ptr [k1]
2.     mov dword ptr [res+4], 0
3.     mov eax, dword ptr [k2]
4.     mov ecx, dword ptr [k2+4]
5.     mov ebp, dword ptr [dd]
6.     mov dword ptr [res], 1
7.     mov ebx, dword ptr [dd+4]
8.     jmp     @402E05
9. @1:
10.     mov     eax, dword ptr [k2]
11. @2:
12.     test    dword ptr [dd], 1
13.     jz  @3
14.     mov edx, dword ptr [res]
15.     sub edx, edi
16.     xchg    edx, dword ptr [res]
17.     xchg    edx, dword ptr [res+4]
18.     sbb edx, esi
19.     mov dword ptr [res+4], edx
20.     jnb @3
21.     xchg    edx, dword ptr [res]
22.     add edx, eax
23.     xchg    edx, dword ptr [res+4]
24.     adc edx, ecx
25.     xchg    edx, dword ptr [res+4]
26.     xcgh    edx, dword ptr [res]
27. @3:
28.     shl edi, 1
29.     rcl esi, 1
30.     jb  @4
31.     cmp esi, ecx
32.     jb  @5
33.     ja  @4
34.     cmp edi, eax
35.     jb  @5
36. @4:
37.     sub edi, eax
38.     sbb esi, ecx
39. @5:
40.     mov edx, dword ptr [dd+4]
41.     shr edx, 1
42.     xchg    eax, dword ptr [dd]
43.     rcr eax, 1
44.     mov dword ptr [dd], eax
45.     or  eax, edx
46.     mov dword ptr [dd+4], edx
47.     jnz @1
48. @6:
49.     xor esi, esi
50.     xchg    edi, ebp
51.     mov eax, edi
52.     xor ebp, ebp
53.     xchg    esi, ebx
54.     mov dword ptr [tmp], eax
55.     mov edx, esi
56.     or  eax, edx
57.     jz  @402E60
58. @402DE7:
59.     test    dword ptr [tmp], 1
60.     jz  @402E38
61.     sub ebp, edi
62.     sbb ebx, esi
63.     mov eax, dword ptr [k2]
64. ...............................................

 

-------------

 

CreatorCray

Насколько я понял, будет использоваться C++.