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
    +1 for **not** choosing $2^{2011}$ and $2^{2012}$...just kidding: interesting question.2012-07-26
  • 0
    If $n$ is prime ($\neq 2$) then the congruence is always true.2012-07-26
  • 1
    @tomasz: Your statement is correct, however it is not relevant. I have added more info above.2012-07-26
  • 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
    The Prime Number Theorem tells you (roughly) how many primes there are in the range of interest. The estimates that draks cites tell you (roughly) how many composites there are, in the range of interest, satisfying the congruence. Isn't that all you need to know to answer your question?2012-07-26
  • 0
    @user1131467 as Gerry pointed out, you've got enough information and you surely don't want me to do all the work for you, don't you?2012-07-26
  • 0
    The two bounds you give for $P_2$ are not very close to each other, so you won't be able to get a number out of them. Nonetheless, this may be the best possible answer with current knowledge.2012-07-26
  • 0
    I've added calculations of your PouletNumber forumlae above. Can you please verify I have calculated the two bounds correctly?2012-07-27
  • 0
    If my calculations are correct than your answer is useless. The probability has been narrowed down between ~0.0 and 0.9.2012-07-27
  • 0
    There is a transcription error in the upper bound (which is by far the more important one here). The term inside exp should be negative (otherwise it is trivial).2012-07-27
  • 0
    @user1131467 Your calculations are not correct, with or without the typo. Although it's worth mentioning that the stated bounds are only valid for large enough $x$ (when it comes to $\log\log\log x$ terms, this could be very large indeed), in practice the number of pseudoprimes is vastly smaller than the true primes even at relatively small scales. For all practical purposes the answer is $0$.2012-07-27
  • 0
    I have fixed the typo and recalculated. I now get between `3.29e-306 < P_Q < 2.63e-44`, is this correct now?2012-07-27
  • 0
    @ErickWong: In what way are the calculations not correct without the typo ?2012-07-27
  • 0
    @ErickWong: Whether you can round a small number to zero depends on the application.2012-07-27
  • 0
    @user1131467 With the $+$ sign you had written a number of magnitude $10^{308}$, which is close to $2^{1024}$, but the sign error gives a value about $10^{44}$ times larger, which should have made the sign problem obvious.2012-07-27
  • 0
    @ErickWong Thanks for spotting the sign typo2012-07-27