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

Mozhet on iskal Stirling's approximation (cm. formuli 17 i 18)? Ih mozhno mod N ochen bistro poschitat, a dalshe pereborom mezhdu granitsami, poka ne naidiosh kotoroye iz nih imeyet obschiye mnozhiteli s N... Hotia ya somnevayus chto eto pomozhet RSA lomat. Tam granici takiye shirokiye, chto uzh prosche reshetom. A voobsche ya lichno bolshe veriu v yego slom cherez razlozheniye modula na mnogo raznih summ neskolkih kvadratov. ;-P

Ruptor

 

Ruptor
Телепатия?
Как раз только что хотел написать про формулу Стирлинга

 

Ruptor
maxdiver
Спасибо за инфу, но сайт что -то не открывается( ==> позже попробую ещё.
Ruptor

я пробую все подходы, кои только можно и нельзя ).
недавно мне стал интересен факт: любое T>N можно представить как сумму p*x+q*y, где x, y >0, p*q==N. одна метода, на основе этого факта, у меня, к сожалению провалилась((
а ещё стал почитывать книгу Диофанта ======> Ферма с полным правом можно назвать его учеником, и впрямь, челюсть часто лежит на полу от этого чтива.
вот скажите, пожалуйста, на основе каких выкладок Горонер пришёл к способу решения системы:
U+V=Z+T
U*V=a*Z*T
известно только a.

 

UbIvItS

Moya ideya bila v tom chto dlia liubogo bolshogo chisla mozhno ochen legko naiti bolshoye kolichestvo summ dopustim iz 8-16 kvadratov, dazhe s zadannimi harakteristikami (naprimer vse kvadrati - smooth chisla ili vse kvadrati - prostiye chisla). Potom chtobi razlozhit na mnozhiteli, dostatochno prosto reshit sistemu lineinih uravneniy dlia vseh par takih summ i naiti celochislennoye resheniye. Yest yeschio odin metod, no on po-slozhneye, cherez RNS.

Ruptor

 

посмотрите урлос: http://neves.suncloud.ru/task/fermat.htm, а ведь у человека и калькулятора не было)

 

ОФФТОП

UbIvItS
Всегда хотел спросить, видя слова типа "урлос" "алгос" и т.п. - ты часом не литовец?
Или грек?

 

CreatorCray
offtop
Русский - просто люблю сокращать слова), а, вообще, мне больше нравиться старый вариант слова алгоритм (алгорифм).
Ты б меня ещё в Испанцы записал бы

 

странное сокращение: урл -> урлос

...впрочем, завязываю с оффтопом.

 

кто -нить ведает как решить a*x-b*y==d && gcd(x mod a, y mod b)==1 && gcd(x mod a, d)==1 && gcd(d, y mod b) ==1???

 

UbIvItS

находишь сначала любое решение a*x0-b*y0==d, затем начинаешь прибавлять к вектору (x0,y0) кратные вектора (b,a) до тех пор, пока не будет найден вектор удовлетворяющий всем остальным условиям.

 

RElf
Я тоже хотел сначала это предложить, но потом до меня дошло (а может, и неправильно дошло? ), что a и b - тоже неизвестны.

 

RElf
у меня другая идея сложилась: обычным расширеным алгосом Евклида ищем a*x-b*y==1, затем x*d mod b & y*d mod a . я никак не пойму почему на основе этой штуки факторизация не пашет(
maxdiver
a, b - известны

 

UbIvItS
Ну раз a и b известны - тогда в чём вопрос? AFAIK кроме алгоритма Евклида никаких других методов не существует.
Может быть, факторизация не работает, потому что уравнение
a*x + b*y = d
решается алгоритмом Евклида, только если d делится на gcd(a,b)?
Хотя, конечно, не зная твоего метода, трудно сказать, почему не работает

 

maxdiver
да, идея до безобразия проста - даже скрывать не буду
любое число >=phi представимо в виде суммы множителей N; берём T>=N+1; получаем (T/2)^2 mod N ==y; теперь решаем T*x mod N== -y mod N..... если получен нетривиальный x, то факторы у нас в кармане.... если этот метод всегда даёт тривиальный x, то вопрос почему???

 

UbIvItS

Что значит "нетривиальный"? Уравнение T*x mod N== -y mod N имеет *единственное* решение mod N.

 

RElf

дело не в том, что оно единственное, а в том, что решение, за очень редким искл., будет тривиальным - почему(???)... это элементарно можно объяснить. в своём блоге я настрокаю другой алгос, вполне возможно, это будет очередным бредом(, но, самое главное, понять почему......

 

короче,2-ая идея следующая: берём уравнение: x^2 + 2*x*k==N*z (x,k,z==???); берём любое k<sqrt(N); решаем: 2*k*A mod N==1; теперь A^2*y mod N==-1; в итоге: x==A*y. всё бы было хорошо, но этот способ ничего кроме тривиальных решений не даст... кстати, maxdiver, не прав, что алгорифм Евклида единственный способ решения a*x== y mod N - есть ещё малая теорема Ферма: x == y*a^(phi-1) mod N, а случай 2*x == y mod N, вообще, решается просто: x == (N+1)/2.... к тому же алгорифм Евклида в чистом виде не всегда даст нужное решение - пример: 11*x==1 mod 9, по Евклиду получим: -4, 5 - что является решением: 9*x== 1 mod 11, т. ч. нужна доп. операция на основе равенства: (-1)^2==1 mod N.

 

выложил методу с бин. поиском факторов, но критерий выбора ветки не полный, т. ч. губу особо катать не приходится)). но идея все же весьма забавна........ вот описание: http://depositfiles.com/files/1952212

 

в мане я не совсем прав: идеальные и нормальные точки тоже могут уводить от решения, причина в том, что ур-ние имеет два корня. но, надо отметить, ситуация нуждается в дальнейшем осмыслении.......

 

любопытную формулу нарыл: S(0)==(1+S(0))*(1+S(1))*.....*(1+S(n-1))*S(n) mod N, где S(i)*(r+i)==1 mod N