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

t00x
с точки зрения оптимальности асм рулит, но пока алгос найти надо) - оптимайзить пока нечего

 

на непрерывные дроби имеет смысл посмотреть повнимательней)

 

Предлогаю следующую систему.
Быстро считаем факториал. Факториал считается быстро через лагорифмы. Логорифмы считаем по быстрым формулам.
Находим остаток через Алгоритм Евклида, который считается тоже быстрым.

Я так думаю можно формулу вывести, найти для расчета этого дела.

А так вообщето хотелось бы знать порядок M и N.

 

Pavia
ну давай для начала 1024 бит, ну или хотя бы 512.

вот тут поподробней, плзззззззз

 

забавно если N/A представить в виде непрерывной дроби, то из полученых чисел можно получить сумму имеющую общий нетривиальный делитель с N. надо отметить, что невсякая А даёт такую возможность, но таких плохих А, по всей видимости, немного. основная проблема: слишком много вариантов возможных сумм, кои надо проверять.
-------------------------------------
хотя, насчёт "немного" - это я зря)

 

интересную гипотезу увидел в книге Девенпорта: "для каждого m найдётся такой m1, что phi(m)==phi(m1)".
ответьте, пожалуйста, на след. вопросы:
A. утв. уже доказали?
B. какие - нить работы есть по алгосам поиска чисел с подобной родственностью???

 

UbIvItS

Вот тебе соратника нашел, хотя и с немного другой "специализацией":
http://a-konst.livejournal.com/145618.html
Можешь не благодарить

 

UbIvItS
Займись гипотезой Эйлера: каждое четное число > 2, можно представить в виде суммы двух простых чисел.
ЗЫ
Простые числа могут быть равными, число представлений может быть > 1.

 

Stiver
фиговый урлос - спасибо не скажу, даже если попросишь)
crypto

разве это не гипотеза Гольдбаха?
к тому же, не вижу особой её ценности, в свете факторизации.

 

UbIvItS
Гипотеза Гольдбаха относится к нечетным числам и следует из гипотезы Эйлера.

 

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

 

прокомментируйте, сей труд, плзззз (http://www.enmash.ru/fact2sat.pdf). у меня он вызывает сомнения, но могет быть.....

 

UbIvItS
У меня нет сомнений в том, что к задаче эффективной факторизации числа он никакого отношения не имеет
Ведь там строится логическая формула f(Z,X,Y), которая истинна тогда и только тогда, когда Z=X*Y. Чтобы факторизовать число Z с помощью этой формулы, потребуется просто уйма времени

 

Нужно написать программу для быстрого расчета гамма функции Эйлера.
Так как Г(n+1) = n!.

А сама функция равна.
Г(n) = интеграл от 0 до бесконечности t^(n-1)*exp(t) dt
Google рулит.

 

S_Alex
Тонкость в том, что здесь нужна арифметическая точность, а не приближенное значение.

 

UbIvItS
расписано в нём умножение в столбик в двоичной системе исчисления.

По теме (не путать с темой топика) одинако придётся составлять файл с простыми числами до 1024 бит.

 

t00x

Прикольно

 

в инете посмотрел инфу по поводу этой доки - возникло устойчивое ощущение реальной шняшки), а на мой вопрос о каком - либо софте на тему этого алгоса =====> молчание)

 

вряд ли при O(n^1.5) кто-то будет реализовывать софт на данном алгоритме для факторизации больших чисел
насколько я понял суть документа - можно поискать программы на тему минимизации ФАЛ

 

UbIvItS

Вот тут можно найти готовую реализацию алгоритма сведения задачи факторизации к задаче выполнимости (SAT). Там же есть и некий эвристический SAT-solver, только вряд ли он сможет решить задачу факторизации для сколь-либо большого числа.