Qual é a maneira mais eficiente de calcular fatoriais modulo a prime?

20

Você conhece algum algoritmo que calcula o fatorial após o módulo de maneira eficiente?

Por exemplo, eu quero programar:

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

Mas, pé um grande número (primo) para a aplicação fatorial diretamente .(p108)

Em Python, essa tarefa é realmente fácil, mas eu realmente quero saber como otimizar.

jonaprieto
fonte
6
Parece que o problema quer que você use o teorema de Wilson. Para prime , . Portanto, sem usar nenhuma linguagem de programação: a resposta é . Talvez você gostaria de generalizar o seu problema? ( p - 1 ) ! = - 1p(p1)!=1modp100
Aryabhata
5
Você pode indicar o problema mais claramente? Deseja calcular (X!) (mod (X+1)), ou o mais geral (X!) (mod Y)? E presumo que factorial(100!)isso realmente não significa que você queira aplicar a função fatorial duas vezes.
Keith Thompson
1
Mesmo se você não tivesse o teorema de Wilson, você tem , o que ajudaria a evitar problemas de estouro. (mn)modp=(mmodp)(nmodp)
25412 Dave Clarke
8
Observe que o teorema de Wilson se aplica somente quando p é primo. Sua pergunta não afirma que p é primo; portanto, o que você escreveu não está correto.
25412 Dave Clarke

Respostas:

11

(Esta resposta foi inicialmente postada pelo autor (a) jonaprieto dentro da pergunta.)

Lembro-me do teorema de Wilson e notei pequenas coisas:

No programa acima, é melhor se eu escrever:

(p1)!1(modp)(p2)!(p1)!(p1)11(modp)(p3)!(p2)!(p2)1(p2)1(modp)(p4)!(p3)!(p3)1(p2)1(p3)1(modp) (p5)!(p4)!(p4)1(p2)1(p3)1(p4)1(modp)

E você pode encontrar porque , portanto, com o algoritmo euclidiano estendido, você pode encontrar o valor de , que é o módulo inverso.(pi)1( p - i ) - 1gcd(p,pi)=1(pi)1

Você também pode ver as mesmas congruências, como: portanto, a soma é igual: e se você fatorar no início os fatoriais, obtém E, voila, o módulo inverso é mais eficiente que os fatoriais. (-24)-1+(6)-1+(

(p5)!(p24)1(modp)(p4)!(p+6)1(modp)(p3)!(p2)1(modp)(p2)!1(modp)(p1)!1(modp)
8 ( - 24 ) - 1
(24)1+(6)1+(2)1
8(24)1(modp)
Gilles
fonte
Então, basicamente . Arrumado! (pk)!(p+(k1)!(1)k)1(modp)
Thomas Ahle
Desculpe, mas quando eu fatorar , recebo:(24)1+61+(2)1
9(24)1=38
1

O exemplo que você está postando está muito relacionado ao problema de Euler # 381. Então, vou postar uma resposta que não resolve o problema de Euler. Vou postar como você pode calcular fatoriais modulo um primo.

Então: Como calcular n! módulo p?

Observação rápida: Se n ≥ p, então n! tem um fator p, então o resultado é 0. Muito rápido. E se ignorarmos o requisito de que p deve ser um primo, então deixe q ser o menor fator primo de p, e n! módulo p é 0 se n ≥ q. Também não há muitas razões para exigir que p seja o principal para responder à sua pergunta.

Agora no seu exemplo (n - i)! para 1 ≤ i ≤ 5 surgiu. Você não precisa calcular cinco fatoriais: você calcula (n - 5) !, multiplica por (n - 4) vai buscar (n - 4) !, multiplica por (n - 3) para obter (n - 3)! etc. Isso reduz o trabalho em quase um fator 5. Não resolva o problema literalmente.

A questão é como calcular n! módulo m. A maneira óbvia é calcular n !, um número com aproximadamente n log n dígitos decimais e calcular o restante módulo p. Isso é trabalho duro. Pergunta: Como podemos obter esse resultado mais rapidamente? Por não fazer a coisa óbvia.

Sabemos que ((a * b * c) módulo p = (((a * b) módulo p) * c) módulo p.

Para calcular n !, normalmente começamos com x = 1 e depois multiplicamos x por 1, 2, 3, ... n. Usando a fórmula do módulo, calculamos n! módulo p sem calcular n !, começando com x = 1 e, em seguida, para i = 1, 2, 3, .., n substituímos x por (x * i) módulo p.

Sempre temos x <pe i <n; portanto, precisamos apenas de precisão suficiente para calcular x * p, e não de uma precisão muito maior para calcular n !. Então, para calcular n! módulo p para p ≥ 2, seguimos os seguintes passos:

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. 

(Algumas respostas mencionam o teorema de Wilson, que apenas responde à pergunta no caso muito especial do exemplo dado, e é muito útil para resolver o problema de Euler # 381, mas em geral não é útil para resolver a pergunta que foi feita).

gnasher729
fonte
-1

Este é meu uso de implementação do teorema de wilson:

A função factMOD é a única a chamar para calcular (n!)% MOD quando MOD-n é pouco contra n.

Alguém conhece outra abordagem eficiente quando não é o caso (por exemplo: n = 1e6 e 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
fonte
1
O código não está realmente no tópico, aqui. Uma descrição do algoritmo é muito mais útil porque não requer que as pessoas entendam o idioma em que você decidiu escrever seu código, e porque as implementações reais geralmente são otimizadas de uma maneira que as torna mais difíceis de entender. E faça suas perguntas como perguntas separadas, e não na sua resposta. O Stack Exchange é um site de perguntas e respostas, não um quadro de discussão, e é difícil encontrar perguntas se estiverem ocultas entre as respostas. Obrigado!
David Richerby