2014 dxdy logo

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

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




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


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

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


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

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


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

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

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


23/10/10
89
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
11057
Россия, Москва
Непонятно что вообще ТС понимает под "быстрым алгоритмом". Может ему хватит простого умножения по модулю и банального цикла. ;-) А может и $m$ недостаточно велико и затраты памяти $O(m)$ не критичны.

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


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

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


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

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


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

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


11/01/06
5660
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
5940
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
89
g______d в сообщении #1363539 писал(а):
Вот ещё нашёл:

Крутяк :!:

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


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

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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