1

Fermat's little theorem states that for $2$ integers $a$ and $n$ such that $n$ is a prime that doesn't divide $a$, $a^{n-1}\equiv 1\pmod{n}$. So in Miller-Rabin test, if we want to test the primality of an integer $p$ (assuming $p>2$, $p$ is odd, $q$ is an odd integer, and $k$ is a positive integer where $p-1=2^{k}q$), we know that this must hold: $a^{p-1}\equiv 1\pmod{p}$ for any integer $a$ not divisible by $p$.

$\because\, \sqrt{1}$ has $2$ solutions $\bmod p$ ($1$ and $-1$)

$\therefore$ either $a^q\equiv 1\pmod{p}$ or $a^{2^{j}q}\equiv p-1\pmod{p}$ (for some $j$ where $0\leq j<k$). So that when this element is squared further, it will always give 1 up to $a^{p-1}$.

My question is why don't we just calculate $a^{p-1}$ directly and check if it is congruent to $1\pmod{p}$? Knowing that if $a^{p-1}\equiv 1\pmod{p}$, then for sure either $a^q\equiv 1\pmod{p}$ or $a^{2^{j}q}\equiv p-1\pmod{p}$ (for some $0\leq j<k$).

metamorphy
  • 39,111
Mohamed EL Tair
  • 205
  • $\sqrt{1}$ only has two solutions if we know $p$ is prime. In general this is not the case - $1$ has four square roots modulo $15$, for instance. – Wojowu Nov 22 '19 at 14:45
  • 1
    The real challenge is composite numbers $p$ that pass this "Fermat's test". – metamorphy Nov 22 '19 at 14:47
  • Thank you all for your responses.

    This means that:

    $\because$ Any prime number $p$ satisfies the following: $(1)$ $a^{p-1}\equiv 1\pmod{p}$ (for any $a$ not divisible by $p$), $(2)$ $\sqrt{1}\equiv 1$ and $-1\pmod{p}$

    $\therefore$ In Miller-Rabin test, we show that for some integer $n$, if it satisfies $(1)$ for many values of $a$, and satisfies $(2)$, the probability that it is prime is very high.

    Is this correct?

     – Mohamed EL Tair Nov 22 '19 at 15:26
  • A Carmichael number $n$ passes the weak Fermat test for every base $a$ coprime to $n$ although it is composite. A weak Fermat pseudoprime to base $a$ need not be a strong Fermat pseudoprime to base $a$. – Peter Nov 23 '19 at 17:45

0 Answers0