7
$\begingroup$

Let $\pi(n)$ be the prime counting function. And let $\varphi(n)$ be the count of Carmichael pseudo-primes for $1$ to $n$. Is the ratio,

$$\frac{\varphi(n)}{\pi(n)}$$

is known, as $n \to \infty$? I am asking this because of i want to know how much safe is the Fermat Primality Test (the one which only uses Fermat's Little Theorem).

I recently wrote a Python script (initially for RSA) and produced more than 10, random 1024 bit primes with the help of this test. After i used the powerful mathematical software PARI/GP to check if they are really primes or pseudo-primes. In conclusion none of them were pseudo-primes. So, if know this rate, i will know the probability that this test will encounter a pseudo-prime and fail.

$\endgroup$
2
$\begingroup$

We have the following result (Knödel, $1953$) :- $$\varphi(n)<n\exp\big(-k(\log n \log\log n)^\frac{1}{2}\big)$$ By strengthened version of PNT, we will have for sufficiently large $n$: $$\pi(n)>\frac{n}{\log n}$$ Thus $\forall$ sufficiently large $n$, we have:- $$\frac{\varphi(n)}{\pi(n)}<\log n \exp\big(-k(\log n \log\log n)^\frac{1}{2}\big)=\exp \big(\log \log n -k(\log n \log\log n)^\frac{1}{2}\big)$$ Note that:- $$\lim_{n \to \infty} \log \log n -k(\log n \log\log n)^\frac{1}{2}=- \infty \implies \lim_{n \to \infty} \exp \big(\log \log n -k(\log n \log\log n)^\frac{1}{2}\big)=0$$ Hence, we have:- $$\lim_{n \to \infty}\frac{\varphi(n)}{\pi(n)}=0$$

$\endgroup$
  • 2
    $\begingroup$ Hence we can say Fermat's primality test is pretty safe since there is almost no possibility to a randomly selected 1024 bit (in other words, 128 digit in base 10) number to be a pseudo prime. $\endgroup$ – İbrahim İpek Jul 16 at 14:46
  • 1
    $\begingroup$ More than 128 digits indeed... So it is even safer for this case. $\endgroup$ – İbrahim İpek Jul 16 at 17:37

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.