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