2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 факториал по модулю
Сообщение23.12.2018, 20:57 


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

 Профиль  
                  
 
 Re: факториал по модулю
Сообщение24.12.2018, 02:12 
Заслуженный участник


20/08/14
5740
Россия, Москва
Вам поможет например эта статья: https://habr.com/post/149273/

 Профиль  
                  
 
 Re: факториал по модулю
Сообщение24.12.2018, 08:54 
Заслуженный участник
Аватара пользователя


08/11/11
5540
Я бы начал отсюда:

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

 Профиль  
                  
 
 Re: факториал по модулю
Сообщение24.12.2018, 11:14 


23/10/10
86
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$). Вряд ли автор темы что-то оттуда извлечёт.

 Профиль  
                  
 
 Re: факториал по модулю
Сообщение24.12.2018, 11:50 
Заслуженный участник


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

 Профиль  
                  
 
 Re: факториал по модулю
Сообщение24.12.2018, 11:53 


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

 Профиль  
                  
 
 Re: факториал по модулю
Сообщение24.12.2018, 17:12 


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

 Профиль  
                  
 
 Re: факториал по модулю
Сообщение24.12.2018, 18:26 


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

 Профиль  
                  
 
 Re: факториал по модулю
Сообщение24.12.2018, 19:09 
Модератор
Аватара пользователя


11/01/06
5397
daniel starodubtsev в сообщении #1363315 писал(а):
Существует ли быстрый алгоритм вычисления факториала числа n по модулю m? Подразумевается, что m>n и разложение m на простые множители неизвестно.

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

 Профиль  
                  
 
 Re: факториал по модулю
Сообщение24.12.2018, 21:34 
Заслуженный участник
Аватара пользователя


08/11/11
5540
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

 Профиль  
                  
 
 Re: факториал по модулю
Сообщение24.12.2018, 23:17 


23/10/10
86
g______d в сообщении #1363539 писал(а):
Вот ещё нашёл:

Крутяк :!:

 Профиль  
                  
 
 Re: факториал по модулю
Сообщение06.01.2019, 15:04 
Модератор
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 12 ] 

Модераторы: Toucan, maxal, PAV, Karan, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Google [Bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group