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

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

 

UbIvItS
Оффтоп
Я тебе нарыл ссылочку одну, почитай, интересно.
http://www.nsu.ru/materials/ssl/text/metodics/levin.html

 

crypto

спасибо.
а вот ещё один урлос, мне дал ECk, тоже любопытный: http://golovolomka.hobby.ru/books/gardner/bornnum.shtml

 

Кто-нить могет доказать, что 2X мин. сумма из всех возможных сумм множителей X^2?? И ещё: знает ли кто квадрат 2a+1, IsPrime(a)==true???

 

впрочем, судя по всему таких 2a+1 ====> нет

 

UbIvItS

Наверное потому, что квадрат вторника не равен 5.

 

crypto

поясни, плзззз...

 

UbIvItS
Дык, очевидно же

 

crypto
что такое вторник?

 

UbIvItS
А что такое

и что такое

 

crypto
X ==sqrt(X^2)
2X==2*X ===========> пример: 36=6^2. возможные суммы множителей: 18+2; 9+4.......
-------------------------
ещё хотелось бы получить квадрат 2*a+1, a - простое число.

ЗЫ
sqrt - функция квадратного корня из числа; IsPrime - тест на простоту числа в Maple.

 

UbIvItS
Т.е. первое утверждение состоит в том, что если N = a*a, то минимальное значение суммы a+b при условии a*b=N, равно 2*N?
Дык, это очевидно.
Я тебе даже больше скажу, можно найти экстремум суммы x+y при условии x*y=N.
Кстати, утверждение видимо относится только к представлению в виде суммы двух множителей..

Второе утверждение по-прежнему туманно.
ЗЫ
Спасибо про sqrt, не знал

 

crypto

не сочти за излишний педантизм), но всё-таки a1*b==N.

честно говоря, док-ва не самая моя сильная сторона - я в основном сермяжный практик)

ну, вот, например, квадрат: 2*x+1=25=2*12+1, а мне нужен квадрат, где x - простое число и порыть вопрос есть ли такие квадраты - если есть, то как их много.

я просто перестраховался - привычка: многих раздражает, но на деле очень полезная)

а+а, итак экстремум - нижний, а верхний мне не нужен.

 

мысли в слух):
довольно легко доказать, что любой нечёт. квадрат принадлежит классу чисел 8*x+1, исходя из этого замечательного факта можно быстро узнать является ли X, в X^2-Y^2, нечётом. для этого достаточно условия: 2*N mod 8 == 2. доказывать не буду, впрочем, докво весьма простое........

 

это глупость - таких чисел быть не может). впрочем, речь не об этом, а вот о чём: разность квадатов может приводиться к виду: x-4^t*y или 4^t*x-y, дальше можно приводить к полиному второй степени и пременить методику вот отсюда: http://www.alpertron.com.ar/METHODS.HTM. хотя на эту бы связку я и копейки бы ставить бы не стал..........
я придумал более быстрый способ по вычленению x, но способ слишком узкополосный по видам чисел.
Зы
x, y - треугольные числа.

 

число на сайте RSA в 704 бит содержит один множитель не сейфпрайм..... интересно почему???)

 

итак, имеем сис. ур-ий:

2^x mod N
3^x mod N
............................

t^x mod N
как можно вытянуть x более/менее оптимально???

 

UbIvItS
Эээ, а где уравнения-то?
2^x mod N = ???
Если я всё-таки правильно тебя понял, то простейшим методом решения будет китайская теорема об остатках. Есть также более быстрый алгоритм Гарнера.

 

maxdiver
чему равно каждое из t^x mod N известно: нужно x вытянуть.

 

мне стала интересна одна идея (как её реализовать более/менее оптимально пока непонятно, к сожалению(), но сама по себе интересна - заставить рса работать против себя самого: основная задача рса - это зная число e, найти незвестное d, но самое интересное, что задачу можно расширить: мы можем взять любое e1 и сломаем N, если найдём такое d1, что e1*d1 mod Phi(N)==1.