1
$\begingroup$

Let $$\text{F}_{91}:=\left\{\overline{a}\in\left(\mathbb{Z}/n\mathbb{Z}\right)^\times:91\text { passes the Fermat primality test to base }a\right\}$$ and $$\text{MF}_{91}:=\left\{\overline{a}\in\left(\mathbb{Z}/n\mathbb{Z}\right)^\times:91\text { passes the Miller-Rabin primality test to base }a\right\}$$ How do we calculate $|\text{F}_{91}|$ and $|\text{MF}_{91}|$? Starting with the Fermat primality test: As described in the Wikipedia article, the algorithm depends on a parameter $k$. In each iteration (there are at most $k$ iterations), a random variable $a\in\left(\mathbb{Z}/n\mathbb{Z}\right)^\times$ is chosen and testet for $$a^{91-1}\equiv1\text{ mod }91$$ If this test fails, the algorithm stops and yields that $91=7\cdot 13$ is not prime. However, I'm not sure how to calculate $|\text{F}_{91}|$ since the test depends on some randomness.

$\endgroup$
2
$\begingroup$

The randomness (or more likely pseudo-randomness) that one uses in the application of the tests shall be ignored here.

"The Fermat test to base $a$" is specifically whether $a^{n-1} \equiv 1 \pmod{n}$, like the "Miller-Rabin test to base $a$" (also called strong Fermat test) is whether $a^m\equiv 1 \pmod{n}$ or $a^{2^j\cdot m} \equiv -1 \pmod{n}$ for one $j \in \{0,\dotsc,k-1\}$, where $n-1 = 2^k\cdot m$ with $m\equiv 1 \pmod{2}$.

So the question is, for how many $\overline{a} \in (\mathbb{Z}/91\mathbb{Z})^\times$ do we have

  • $a^{90} \equiv 1 \pmod{91}$, resp.
  • $a^{45} \equiv \pm 1 \pmod{91}$.

Since $91 = 7\cdot 13$, the numbers are not hard to find.

$\endgroup$
  • $\begingroup$ Use the Chinese remainder theorem. You look at each prime factor separately (generally, the prime powers dividing $n$), and glue the things together with the CRT. $\endgroup$ – Daniel Fischer Jun 23 '14 at 20:11
  • $\begingroup$ Let's do it with Fermat's theorem: $$a^{90}\equiv \left(a^6\right)^{15}\equiv 1\mod 7$$ and $$a^{90}=\left(a^{12}\right)^7a^6\equiv a^6\mod 13$$ But that's still not that easy to write down, which $1\le a\le 91$ fulfill this property. $\endgroup$ – 0xbadf00d Jun 23 '14 at 21:32
  • $\begingroup$ You don't need to find which, only how many. How many residues modulo $13$ satisfy $a^6 \equiv 1 \pmod{13}$? $\endgroup$ – Daniel Fischer Jun 23 '14 at 21:33
  • $\begingroup$ You have $k$ residues modulo $7$ that satisfy $a^{90}\equiv 1 \pmod{7}$. and $m$ residues modulo $13$ with $a^{90} \equiv 1 \pmod{13}$. Then you have $k\cdot m$ residues modulo $7\cdot 13$ with $a^{90} \equiv 1 \pmod{91}$. $\endgroup$ – Daniel Fischer Jun 23 '14 at 21:47
  • $\begingroup$ You are only looking at the remainders modulo $7$ there. There are only $7$ such, one of them has $a^{90}\equiv 0 \pmod{7}$. $\endgroup$ – Daniel Fischer Jun 23 '14 at 22:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.