modular arthmetic

87 Views Asked by At

To prove that a number p is prime we use this formula $a^{p-1} \pmod p = 1$

In the case of high powers can we derive a formula to solve higher power orders: $a^{p-1} \pmod p = 1$

$(a^{p-2}) (p-1) \pmod p = 1$

taking log to both sides we get: $\log\left(\left(a^{p-2}\right)(p-1)\pmod p\right) = \log(1)$

From the property $\log(uv) = \log (u ) + \log(v)$, we get:

$\log(a^{p-2})+\log(p-1 \pmod p) = \log 1$

From another property of log : $\log(a^n) = n \log a $

we have $(p-2) \log(a)+\log(p-1)=\log 1 $

wheres the part that has gone wrong here? why is it not mathematically true?

1

There are 1 best solutions below

0
On

The primality tests in regular use (e.g. Miller-Rabin) are different from this Fermat test (which can be fooled, but rarely; practical primality tests use the Fermat test to weed out composites as a first step).

To compute $a^n$ for large $n$ a practical solution is to use repeated squaring:

$\begin{align*} a^{2 k} &= (a^k)^2 \\ a^{2 k + 1} &= (a^k)^2 \cdot a \end{align*}$

Computing $a^n$ is not that expensive.

To use logarithms (you need the exact power!) you'd need to compute $\log a$ and then $10^{n \log a}$ to a lot of significant figures, much more than is practical.