- #1
evinda
Gold Member
MHB
- 3,836
- 0
Hello! (Wave)
I am reading about Carmichael numbers, and I have some questions about it.
First of all, in my notes it says the following.
If a Carmichael number is fed into the Fermat test, the probability that the wrong answer is given is
$$\frac{\phi(n)-2}{n-3}> \prod_{p \mid n, p \text{ prime} } \left( 1-\frac{1}{p} \right)$$
This bound is annoyingly close to $1$ if $n$ has only few and large prime factors.
The repetition trick does not help here either, since if the smallest prime factor of a Carmichael number $n$ is $p_0$, and $n$ has only $3$ or $4$ factors,then $\Omega(p_0)$ repetitions are necessary to make the error probability smaller than $\frac{1}{2}$. This is unfeasible as soon as $p_0$ has more than $20$ decimal digits, say.My first question is about this part: This is unfeasible as soon as $p_0$ has more than $20$ decimal digits, say.
Why is it unfeasible, given that the size of $p_0$ will be smaller than this of $n$ ?
My second question is about the proof of the lemma that a Carmichael number $n$ is a product of at least $3$ distinct prime factors. We suppose that $n=p^k \cdot m$, for some $k \geq 2$ and $(m,p)=1$. And, according to my notes, for $m \geq 3$ we may choose some $a, 1 \leq a<p^2 \cdot m\leq n$, with
$$a \equiv 1+p \pmod{p^2} \\ a \equiv 1 \pmod{m}$$
So does this mean that if we have some $n=c^i\cdot b^j$ where $(c,b)=1$ that we can choose the interval at which some $a$ that we get from the Chinese remainder theorem, belongs ? i.e. we choose some $k_1$ and $k_2$ so that $1 \leq a< c^{k_1} b^{k_2} $ and
$$a \equiv \text{ something } \pmod{c^{k_1}} \\
a \equiv \text{ something else } \pmod{b^{k_2}}$$
?
I am reading about Carmichael numbers, and I have some questions about it.
First of all, in my notes it says the following.
If a Carmichael number is fed into the Fermat test, the probability that the wrong answer is given is
$$\frac{\phi(n)-2}{n-3}> \prod_{p \mid n, p \text{ prime} } \left( 1-\frac{1}{p} \right)$$
This bound is annoyingly close to $1$ if $n$ has only few and large prime factors.
The repetition trick does not help here either, since if the smallest prime factor of a Carmichael number $n$ is $p_0$, and $n$ has only $3$ or $4$ factors,then $\Omega(p_0)$ repetitions are necessary to make the error probability smaller than $\frac{1}{2}$. This is unfeasible as soon as $p_0$ has more than $20$ decimal digits, say.My first question is about this part: This is unfeasible as soon as $p_0$ has more than $20$ decimal digits, say.
Why is it unfeasible, given that the size of $p_0$ will be smaller than this of $n$ ?
My second question is about the proof of the lemma that a Carmichael number $n$ is a product of at least $3$ distinct prime factors. We suppose that $n=p^k \cdot m$, for some $k \geq 2$ and $(m,p)=1$. And, according to my notes, for $m \geq 3$ we may choose some $a, 1 \leq a<p^2 \cdot m\leq n$, with
$$a \equiv 1+p \pmod{p^2} \\ a \equiv 1 \pmod{m}$$
So does this mean that if we have some $n=c^i\cdot b^j$ where $(c,b)=1$ that we can choose the interval at which some $a$ that we get from the Chinese remainder theorem, belongs ? i.e. we choose some $k_1$ and $k_2$ so that $1 \leq a< c^{k_1} b^{k_2} $ and
$$a \equiv \text{ something } \pmod{c^{k_1}} \\
a \equiv \text{ something else } \pmod{b^{k_2}}$$
?