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

Тема в разделе "WASM.A&O", создана пользователем UbIvItS, 16 май 2007.

  1. Ruptor

    Ruptor Marcos el Ruptor

    Публикаций:
    0
    Регистрация:
    9 янв 2005
    Сообщения:
    167
    Адрес:
    Australia
    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
     
  2. maxdiver

    maxdiver Max

    Публикаций:
    0
    Регистрация:
    18 июл 2006
    Сообщения:
    308
    Адрес:
    Саратов
    Ruptor
    Телепатия? :)
    Как раз только что хотел написать про формулу Стирлинга :)
     
  3. UbIvItS

    UbIvItS Well-Known Member

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

    Ruptor Marcos el Ruptor

    Публикаций:
    0
    Регистрация:
    9 янв 2005
    Сообщения:
    167
    Адрес:
    Australia
    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
     
  5. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.074
    посмотрите урлос: http://neves.suncloud.ru/task/fermat.htm, а ведь у человека и калькулятора не было:))
     
  6. CreatorCray

    CreatorCray Member

    Публикаций:
    0
    Регистрация:
    5 авг 2006
    Сообщения:
    201
    ОФФТОП

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

    UbIvItS Well-Known Member

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

    CreatorCray Member

    Публикаций:
    0
    Регистрация:
    5 авг 2006
    Сообщения:
    201
    странное сокращение: урл -> урлос

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

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.074
    кто -нить ведает как решить 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???
     
  10. RElf

    RElf New Member

    Публикаций:
    0
    Регистрация:
    25 дек 2004
    Сообщения:
    159
    UbIvItS
    находишь сначала любое решение a*x0-b*y0==d, затем начинаешь прибавлять к вектору (x0,y0) кратные вектора (b,a) до тех пор, пока не будет найден вектор удовлетворяющий всем остальным условиям.
     
  11. maxdiver

    maxdiver Max

    Публикаций:
    0
    Регистрация:
    18 июл 2006
    Сообщения:
    308
    Адрес:
    Саратов
    RElf
    Я тоже хотел сначала это предложить, но потом до меня дошло (а может, и неправильно дошло? :) ), что a и b - тоже неизвестны.
     
  12. UbIvItS

    UbIvItS Well-Known Member

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

    maxdiver Max

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

    UbIvItS Well-Known Member

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

    RElf New Member

    Публикаций:
    0
    Регистрация:
    25 дек 2004
    Сообщения:
    159
    UbIvItS
    Что значит "нетривиальный"? Уравнение T*x mod N== -y mod N имеет *единственное* решение mod N.
     
  16. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.074
    RElf
    дело не в том, что оно единственное, а в том, что решение, за очень редким искл., будет тривиальным - почему(???)... это элементарно можно объяснить. в своём блоге я настрокаю другой алгос, вполне возможно, это будет очередным бредом:dntknw:(, но, самое главное, понять почему......
     
  17. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.074
    короче,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.
     
  18. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.074
    выложил методу с бин. поиском факторов, но критерий выбора ветки не полный, т. ч. губу особо катать не приходится:))). но идея все же весьма забавна........ вот описание: http://depositfiles.com/files/1952212
     
  19. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.074
    в мане я не совсем прав: идеальные и нормальные точки тоже могут уводить от решения, причина в том, что ур-ние имеет два корня. но, надо отметить, ситуация нуждается в дальнейшем осмыслении.......
     
  20. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.074
    любопытную формулу нарыл: S(0)==(1+S(0))*(1+S(1))*.....*(1+S(n-1))*S(n) mod N, где S(i)*(r+i)==1 mod N