Каков наиболее эффективный способ вычисления факториалов по модулю простого числа?

20

Знаете ли вы какой-либо алгоритм, который эффективно рассчитывает факториал после модуля?

Например, я хочу запрограммировать:

for(i=0; i<5; i++)
  sum += factorial(p-i) % p;

Но pэто большое число (простое число) для непосредственного применения факториала .(п108)

В Python эта задача действительно проста, но я действительно хочу знать, как оптимизировать.

jonaprieto
источник
6
Похоже, что проблема хочет, чтобы вы использовали теорему Уилсона. Для простого , (p-1)! = -1 \ мод р . Так что без использования какого-либо языка программирования: ответ 100 . Возможно, вы хотели бы обобщить вашу проблему? п(п-1)!знак равно-1модификацияп100
Арьябхата
5
Можете ли вы сформулировать проблему более четко? Вы хотите вычислить (X!) (mod (X+1)), или более общий (X!) (mod Y)? И я предполагаю, что на factorial(100!)самом деле это не значит, что вы хотите применить функцию факториала дважды.
Кит Томпсон
1
Даже если у вас не было теоремы Уилсона, у вас есть это (мN)модификацияпзнак равно(ммодификацияп)(Nмодификацияп) , которое, по крайней мере, поможет избежать проблем переполнения.
Дейв Кларк,
8
Обратите внимание, что теорема Вильсона применима только тогда, когда p простое. Ваш вопрос не утверждает, что p простое число, поэтому то, что вы написали, неверно.
Дейв Кларк,

Ответы:

11

(Этот ответ был первоначально опубликован в вопросе аскером jonaprieto .)

Я помню теорему Вильсона и заметил мелочи:

В приведенной выше программе лучше написать:

(п-1)!-1(модификацияп)(п-2)!(п-1)!(п-1)-11(модификацияп)(п-3)!(п-2)!(п-2)-1(п-2)-1(модификацияп)(п-4)!(п-3)!(п-3)-1(п-2)-1(п-3)-1(модификацияп) (п-5)!(п-4)!(п-4)-1(п-2)-1(п-3)-1(п-4)-1(модификацияп)

И вы можете найти потому что , поэтому с помощью расширенного евклидова алгоритма вы можете найти значение , то есть обратный модуль. НОД ( р , р - я ) = 1 ( р - я ) - 1(п-я)-1НОД(п,п-я)знак равно1(п-я)-1

Вы также можете просмотреть те же конгруэнции, например: поэтому сумма равна: и если вы сначала факторизуете факториалы, вы получите И, вуаля, обратный модуль более эффективен, чем факториалы. (-24)-1+(6)-1+(-2)-18(-24)-1

(п-5)!(п-24)-1(модификацияп)(п-4)!(п+6)-1(модификацияп)(п-3)!(п-2)-1(модификацияп)(п-2)!1(модификацияп)(п-1)!-1(модификацияп)
(-24)-1+(6)-1+(-2)-1
8(-24)-1(модификацияп)
Жиль
источник
Так в основном . Ухоженная! (п-К)!(п+(К-1)!(-1)К)-1(модификацияп)
Томас Але
Извините, но когда я разлагаю , я получаю:(-24)-1+6-1+(-2)-1
9(-24)-1знак равно-38
1

Пример, который вы публикуете, очень тесно связан с проблемой Эйлера # 381. Поэтому я опубликую ответ, который не решит проблему Эйлера. Я опубликую, как вы можете вычислить факториалы по модулю простого числа.

Итак: Как рассчитать! по модулю р?

Быстрое наблюдение: если n ≥ p, то n! имеет фактор р, поэтому результат равен 0. Очень быстро. И если мы игнорируем требование, что p должно быть простым, то пусть q будет наименьшим простым фактором p, и n! по модулю p равно 0, если n ≥ q. Также нет особых причин требовать, чтобы p было простым, чтобы ответить на ваш вопрос.

Теперь в вашем примере (п - я)! для 1 ≤ я ≤ 5 подошел. Вам не нужно вычислять пять факториалов: Вы вычисляете (n - 5) !, умножаете на (n - 4), идете, получаете (n - 4) !, умножаете на (n - 3), чтобы получить (n - 3)! и т.д. Это сокращает работу почти в 5 раз. Не решайте проблему буквально.

Вопрос в том, как рассчитать n! по модулю м. Очевидным способом является вычисление n !, числа с примерно n log n десятичными цифрами, и вычисление остатка по модулю p. Это тяжелая работа. Вопрос: Как мы можем получить этот результат быстрее? Не делая очевидных вещей.

Мы знаем, что ((a * b * c) по модулю p = (((a * b) по модулю p) * c) по модулю p.

Чтобы вычислить n !, мы обычно начинаем с x = 1, затем умножаем x на 1, 2, 3, ... n. Используя формулу по модулю, мы вычисляем n! по модулю p без вычисления n !, начиная с x = 1, а затем для i = 1, 2, 3, .., n мы заменяем x на (x * i) по модулю p.

У нас всегда есть x <p и i <n, поэтому нам нужна только достаточная точность для вычисления x * p, а не гораздо более высокая точность для вычисления n !. Так что посчитать! По модулю p для p ≥ 2 предпринимаем следующие шаги:

Step 1: Find the smallest prime factor q of p. If n ≥ q then the result is 0.
Step 2: Let x = 1, then for 1 ≤ i ≤ n replace x with (x * i) modulo p, and x is the result. 

(В некоторых ответах упоминается теорема Уилсона, которая отвечает на вопрос только в очень особом случае из приведенного примера и очень полезна для решения проблемы Эйлера # 381, но в целом бесполезна для решения поставленного вопроса).

gnasher729
источник
-1

Это моя реализация использования теоремы Вильсона:

Функция factMOD вызывается для вычисления (n!)% MOD, когда MOD-n мало против n.

Кто-нибудь знает другой эффективный подход, когда это не так (например, n = 1e6 и MOD = 1e9 + 7)?

ll powmod(ll a, ll b){//a^b % MOD
  ll x=1,y=a;
  while(b){
    if(b&1){
      x*=y; if(x>=MOD)x%=MOD;
    }
    y*=y; if(y>=MOD)y%=MOD;
    b>>=1;
  }
  return x;
} 
ll InverseEuler(ll n){//modular inverse of n
  return powmod(n,MOD-2);
}
ll factMOD(ll n){ //n! % MOD efficient when MOD-n<n
   ll res=1,i;
   for(i=1; i<MOD-n; i++){
     res*=i;
     if(res>=MOD)res%=MOD;
   }
   res=InverseEuler(res);   
    if(!(n&1))
      res= -res +MOD;
  }
  return res%MOD;
}
JeanClaudeDaudin
источник
1
Код не совсем по теме, здесь. Описание алгоритма гораздо полезнее, поскольку оно не требует, чтобы люди понимали язык, на котором вы решили написать свой код, и потому что фактические реализации часто оптимизируются таким образом, что их труднее понять. И, пожалуйста, задавайте свои вопросы как отдельные вопросы, а не как ответ. Stack Exchange - это сайт вопросов и ответов, а не доска объявлений, и трудно найти вопросы, если они скрыты за ответами. Благодарность!
Дэвид Ричерби