Forma sencilla de calcular el $n! \pmod p$

Question

Tengo el "ejercicio de Calcular el $10! \pmod{13}$".

Tengo los dos métodos siguientes para resolver el ejercicio:

1. Aproximación de fuerza bruta

$$1! \equiv 1 \pmod{13} \\ 2! = 2 \cdot 1! \equiv 2 \cdot 1 \equiv 2 \pmod{13} \\ 3! = 3 \cdot 2! \equiv 3 \cdot 2 \equiv 6 \pmod{13} \\ \cdots \\ 10! = 10 \cdot 9! \equiv 10 \cdot 11 = 110 = 8 \cdot 13 + 6 \equiv 6 \pmod{13}$$

2. Enfoque el uso del teorema de Wilson:

Wilson del teorema de los estados que $$p \in \mathbb{P} \implies (p-1)! \equiv -1 \pmod p$$

Para mi ejercicio: $$13 \in \mathbb{P} \implica \\ (13-1)! = 12! = 10!\cdot 11 \cdot 12 \equiv -1 \pmod{13} \implica \\ 10! \equiv -(11 \cdot 12)^{-1} \pmod{13}$$ El uso de Fermat poco teorema de $$a^p \equiv \pmod p \implica un^{p-2} \cdot a \cdot a \equiv a^{-1} \cdot a \cdot a \pmod p \implica un^{p-2} \equiv a^{-1} \pmod p \\ $$ Para mi ejercicio: $De$10! = -(11 \cdot 12)^{-1} \equiv \\ -(11 \cdot 12)^{13-2} = -(11 \cdot 12)^{11} \equiv \\ -(-2 \cdot -1)^{11} = -2^{11} = \\ -2^6 \cdot 2^5 \equiv 1 \cdot 2^5 = \\ 32 \equiv 6 \pmod{13} \\ $$

Ambos enfoques se ven muy voluminosos.

En el primer método que tengo que hacer la $O(n)$ multiplicaciones.

En el segundo método que tengo que hacer la $O(p-n)$ multiplicaciones que es menor que en el primer método, pero también puede ser enorme número de grandes $p$$n$.

Hay una manera para mejorar mi solución?

Es allí una manera eficiente para calcular el $n! \pmod p$ grande $n$$p$?

Answer 1

Comience con su Wilson del Teorema de enfoque, pero rematar de manera diferente. Tenga en cuenta que$12\equiv -1$$11\equiv -2 \pmod{13}$, y que estos dos números tienen fácil inversos $(-2)(-7) \equiv 1$$(-1)(-1) \equiv 1 \pmod{13}$, por lo que

$$10! \equiv -(11)^{-1}(12)^{-1} \equiv -(-2)^{-1}(-1)^{-1} \equiv -(-7)(-1) \equiv 6 \pmod{13}.$$

Answer 2

Semi fuerza bruta. $14\equiv 1 \mod 13$ , por lo que tirar $2,7$. $27 \equiv 1$ así que tirar $3,9$. $40 \equiv 1$ para lanzar $4,10$$8,5$. ¿Qué nos han dejado.

Sólo $6$. $10! \equiv 6\mod 13$

debido a $10! =(2*7)(3*9)(4*10)6 (5*8)\equiv 6 \mod 13$

Hmm, no es muy satisfactorio, es él.