5
$\begingroup$

Select a uniformly random integer $n$ between $2^{1024}$ and $2^{1025}$

(Q) What is the probability that n is composite given that $2^{n-1}$ mod $n = 1$ ?

How did you calculate this?

More info:

One way to calculate this would be if you had the following two variables:

$P_Q(n) = 1 - { P_{prime}(n) \over P_{cong}(n) }$

Where:

  • $P_{prime}(n)$ is the probability n is prime
  • $P_{cong}(n)$ is the probability that $2^{n-1}$ mod $n = 1$

So answering the following two questions would be sufficient to answer the main one:

What is $P_{prime}(n)$ equal to?

What is $P_{cong}(n)$ equal to ?

(This holds because the probability that n is prime if the congruence is false is 0.)

Based on the PouletNumber forumale given below:

exp((ln(2^1025))^(5/14))-exp((ln(2^1024))^(5/14))  = 123 

and

(2^1025)*exp(-ln(2^1025)*ln(ln(ln(2^1025))) / (2*ln(ln(2^1025)))) - (2^1024)*exp(-ln(2^1024)*ln(ln(ln(2^1024))) / (2*ln(ln(2^1024))))  = 9.82e263 

So its between 123 < x < 9.82e263

??

And so $P_Q$ is:

3.29e-306 < P_Q < 2.63e-44 
  • 0
    Technically one should not be subtracting upper bounds, but there's certainly room for grey area here. Neither bound is 100% guaranteed (no one has gone to the trouble of making "large enough $x$" explicit). With this proviso, the "safer" upper bound is to not subtract the $2^{1024}$ term at all.2012-07-27

1 Answers 1

4

Due to Fermat's Little Theorem, $ a^{p-1} \bmod p=1 $ if $a$ and $p$ are coprime. In your case $a=2$ and $p$ are all other primes, as pointed out by tomasz in the comment.

But as I recognized right now you are looking for composite $x$, so you are looking for Fermat Pseudo primes. Their distribution can be found here. A file with pseudo primes up to $10^{15}$ can be found here.

They are also called Poulet numbers, and according to the MathWorld page, for large $x$ their number below $x$ is given by $ \exp((\ln(x))^{5/14})

If $P_2(x)$ is the same as your $P_{\text{cong}(x)}$, you have something to work with. But see my edit below for some other possible meanings of $P_2(x)$.


Concerning your edit: You can approximate $\pi(x)$, the number of primes below $x$ by $x/\log x$. So in the given range there are $ \pi(2^{1025})- \pi(2^{1024})= 2^{1025}/(1025\log 2)- 2^{1024}/(1024\log 2)=3.74\cdot 10^{307} $ primes.


EDIT

Here are some more facts about Poulet numbers:

  • Rotkiewicz Theorem: If $n>19$, there exists a Poulet number between $n$ and $n^2$. The theorem was proved in 1965.
  • Let $p$, $q$, $\ell$ be odd primes, and let $P_2(x)$ be the counting function for odd pseudoprimes with two distinct prime factors, $P_2(x) := \#\{n \leq x : n = pq, p < q, psp(n)\}$ (where $psp(n)$ means $n$ is pseudoprime). Then $P_2(x)\sim C\sqrt{x} / \ln^2(x)$ as $x\to \infty$.

    For more read here. The notation $P_2(x)$ (the counting function for odd pseudoprimes with $2$ distinct prime factors) seems to be a little confusing. In the last link they also state a result by Erdős, saying $c_1\log x\leq P_k(x)\le c_2\frac x{\log^k x}$. Maybe you need to sum the $P_k(x)$ to get to what you need.

  • 0
    @ErickWong Thanks for spotting the sign typo2012-07-27