1
$\begingroup$

I am trying to check if a very big number ($>10^{10,000,000}$) is possibly prime. I have written a computer program to check if the number has any smallish (less than like $600,000,000$) factors... it doesn't. I know that the chance of a random number $p$ being prime is $\dfrac{1}{\ln p}$, but what if it doesn't have any factors less than $600,000,000$? Or more generally, what is the probability that $p$ is prime if it doesn't have any factors less than $x$?

I thought that it might be $\dfrac{\ln(x)}{\ln p}$ but since you only have to check up to the square root of the number to confirm it's prime that didn't make since. I would guess it might be $\dfrac{\ln(x)^2}{\ln p}$ but that's just a guess.

Any help is appreciated. Thanks in advance!

$\endgroup$
  • $\begingroup$ Possibly useful: Dickman function $\endgroup$ – Brian Tung Aug 28 at 16:48
  • 1
    $\begingroup$ @BrianTung To the best of my understanding, that is the chance that all of a number's factors are less than $x$ rather than if all of the factors are bigger than $x$. $\endgroup$ – Houston Aug 28 at 17:13
  • $\begingroup$ Oh, sorry, you don't want any factors smaller than a given threshold; I misread you. $\endgroup$ – Brian Tung Aug 28 at 19:58
  • $\begingroup$ In fact, the chance is of the magnitude you expected, just about $1.781$ times larger. See the below answer. $\endgroup$ – Peter Aug 29 at 11:41
3
$\begingroup$

If a huge number has no prime factor below $n$ and $n$ itself is large (lets say $10^4$ or larger) , then the chance that the number is prime increases approximately by the factor $$e^{\gamma}\cdot \ln(n)$$ , so if the trial factor limit is $\ 10^k\ $ , the factor is about $\ 4.1\cdot k\ $.

So, the chance for the huge number $N$ to be prime is $$\frac{e^{\gamma}\cdot \ln(n)}{\ln(N)}$$

So, even if you check the prime factors upto $\ 10^{10}\ $ , the chance increases only by a factor $\ 41\ $. That means that a number with millions of digits still has a very low chance to be prime. This is the reason for the difficulty to find huge primes, trial factoring has a much smaller effect than one would expect.

A bit higher is the chance if you search for prime numbers of a special form, for example mersenne primes because of the form the prime factors must have, but I do not know how large this additional effect is.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you! The number is of a special form but I just wanted to know if there is a decent chance that it's prime before I did a big computation to actually see if it was, since it you wouldn't know until the computation is complete and you have an answer. $\endgroup$ – Houston Aug 29 at 19:16

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.