факториал по модулю

[daniel starodubtsev]

Помогите пожалуйста!
Существует ли быстрый алгоритм вычисления факториала числа n по модулю m? Подразумевается, что m>n и разложение m на простые множители неизвестно.

[Dmitriy40]

Вам поможет например эта статья: https://habr.com/post/149273/

[g______d]

Я бы начал отсюда:

http://www.cecm.sfu.ca/personal/pborwein/PAPERS/P29.pdf

[MetaMorphy]

daniel starodubtsev: Если под "быстрый" понимается "субэкспоненциальный", то вроде пока ещё даже со случаем известного разложения $m$ не разобрались. При простом $m=p$ такой алгоритм действительно есть, но вопрос, можно ли вычислить хотя бы $(p-1)! \bmod p^2$ за полиномиальное (от $\log p$) время, насколько я знаю, до сих пор открыт.

В вашей же общей ситуации... навскидку легко получить алгоритм сложности $O(n^{1/2}\log^{3+\varepsilon}m)$ (сведением к задаче вычисления значений полинома степени $O(n^{1/2})$ в таком же количестве точек), но устроит ли это вас - не знаю. (Кстати, это ключевая идея алгоритма Полларда-Штрассена разложения $N$ на множители, имеющего сложность $O(N^{1/4+\varepsilon})$, который, правда, сегодня нет никакого смысла использовать. И - на всякий случай - если вы пытаетесь через теорему Вильсона изобрести новый алгоритм теста простоты числа ($m$), рекомендую сразу бросить эту затею.)

Dmitriy40: Этот путь в общем случае ведёт к таблице размера $O(m)$. Тогда проще уж сразу таблицу ответов составить ;)

g______d: Эта статья касается точного вычисления $n!$ (не по модулю $m$). Вряд ли автор темы что-то оттуда извлечёт.

[Dmitriy40]

Непонятно что вообще ТС понимает под "быстрым алгоритмом". Может ему хватит простого умножения по модулю и банального цикла. А может и $m$ недостаточно велико и затраты памяти $O(m)$ не критичны.

[MetaMorphy]

Dmitriy40: Он даже разлагать $m$ на множители не хочет. Но вообще, и правда, следует дождаться его реакции.

[daniel starodubtsev]

Вообще я предполагал, что n будет примерно 20-значное, а m вообще очень большое (может быть около пятидесяти знаков). Под быстрым алгоритмом я в данном случае подразумеваю такой, какой это сделает вообще...

[MetaMorphy]

Что-то я уже даже в случае простого $m$ не уверен. Возможно, выше я несколько поторопился на этот счёт.

[maxal]

daniel starodubtsev в сообщении #1363315 писал(а):

Существует ли быстрый алгоритм вычисления факториала числа n по модулю m? Подразумевается, что m>n и разложение m на простые множители неизвестно.

Эта задача не проще факторизации $m$. Например, если $m=pq$ - произведение двух простых $p<q$, то вычисление $\gcd(\lfloor\sqrt{m}\rfloor!\bmod m,m)$ даст $p$.

[g______d]

MetaMorphy в сообщении #1363416 писал(а):

Эта статья касается точного вычисления $n!$ (не по модулю $m$). Вряд ли автор темы что-то оттуда извлечёт.

Да, я что-то не то привёл: там большим параметром, в частности, является количество знаков $n!$, которое в данном случае константа (зависящая от $m$).

maxal в сообщении #1363519 писал(а):

Эта задача не проще факторизации $m$. Действительно, если $m$ - составное, то вычислением $\gcd(\lfloor\sqrt{m}\rfloor!\bmod m,m)$ находится нетривиальный делитель $m$.

Я думаю, что интересен случай, например, $n=m^{1/10}$.

Вот ещё нашёл:

http://www.cs.ou.edu/~qcheng/paper/factorial.pdf

[MetaMorphy]

g______d в сообщении #1363539 писал(а):

Вот ещё нашёл:

Крутяк

[maxal]

Вот еще для полноты картины: https://rjlipton.wordpress.com/2009/02/ ... actorials/