7
$\begingroup$

I was reading somewhere that it's hard to determine if a number is prime or not if it gets too large.

If I understand correctly, all numbers can be broken into prime factors. And numbers which can't be broken down to any factors beside $1$ and themselves are prime.

So to check if $N$ is prime, you need to

calculate prime numbers upto $N/2$, (as any number bigger than $N/2$ can't be a factor for $N$ since multiplying it with the minimum number that will have effect, which is $2$, will make it more than $N$).

and check if any of these are factors of $N$.

I want to know if I am right, and what I am missing in terms of it being hard to compute.

$\endgroup$
  • 15
    $\begingroup$ Actually, you need only test divisors up to $\left\lfloor\sqrt{n}\right\rfloor$. What you’re missing is the amount of time required to do this when $n$ is large. $\endgroup$ – Brian M. Scott Apr 10 '16 at 4:36
  • $\begingroup$ can you explain Sqrt(N) part $\endgroup$ – Muhammad Umer Apr 10 '16 at 4:38
  • 5
    $\begingroup$ If $n=ab$ with $a\le b$, then we must have $a\le\sqrt{n}$, since otherwise $ab>(\sqrt{n})^2>n$. $\endgroup$ – Brian M. Scott Apr 10 '16 at 4:39
  • $\begingroup$ oh i see, thanks $\endgroup$ – Muhammad Umer Apr 10 '16 at 4:41
  • 2
    $\begingroup$ It is hard to check for a large number's primality, yes, but at least that is a comparatively easier task than attempting to factor a large number. (As an aside, most of the efficient probabilistic tests should be properly called "compositeness tests", since they can show compositeness with certainty, but not primality.) $\endgroup$ – J. M. is a poor mathematician Apr 10 '16 at 10:14
16
$\begingroup$

The most brute force procedure that is not inefficient for completely naive reasons is trial division up to $\lfloor \sqrt{n} \rfloor$, because if $n$ has a factor greater than or equal to $\sqrt{n}$ then it must also have a factor less than or equal to $\sqrt{n}$. (For example, $\lfloor \sqrt{91} \rfloor = 9$. Although $91$ has a factor of $13$ which is larger than $9$, it also has a factor of $7$, and dividing by this factor reveals the factor of $13$.)

The difficulty is that if $n$ has 100 digits then $\sqrt{n}$ is like $10^{50}$, so if you try a trillion numbers per second then it will take you more than $10^{30}$ years to finish trying all the factors less than $\sqrt{n}$.

There are much better algorithms out there, though, especially for the problem of primality testing (as opposed to factorization of a number which is known to be composite).

$\endgroup$
  • 4
    $\begingroup$ @manshu, determining the primality of possible factors can be much more expensive that doing directly the trial division. $\endgroup$ – Martín-Blas Pérez Pinilla Apr 10 '16 at 8:18
  • 2
    $\begingroup$ @manshu, the list of all the prime numbers? The list of prime numbers up to $\lfloor\sqrt{n}\rfloor$? $\endgroup$ – Martín-Blas Pérez Pinilla Apr 10 '16 at 8:25
  • 3
    $\begingroup$ @manshu There are infinitely many prime numbers, so of course your computer doesn't have a list of all of them. Even with the most compact representation we could come up with, there isn't enough storage capacity in the world to store all the primes up to 25 digits. $\endgroup$ – kasperd Apr 10 '16 at 9:57
  • 4
    $\begingroup$ @manshu it is not a lot less, it's less by a factor of $50\ln(10)$ by the prime number theorem, so you get all the way down to about $10^{48}$. And this ignores all issues with constructing this list of primes. $\endgroup$ – Sasho Nikolov Apr 10 '16 at 13:52
  • 1
    $\begingroup$ ok. ok . I get it $\endgroup$ – manshu Apr 10 '16 at 13:54
4
$\begingroup$

Probably what you have read (in the context of public key encryption) is that it is hard to factor a large integer in its prime divisors if each of these divisors is large. In essence, factoring a number consisting of $n$ bits into prime components, requires trial divisions using numbers containing up to $\frac12n$ bits. As there are $2^{n/2}$ such numbers, this computational effort scales exponentially. More specifically, every two additional bits in the number to be factored, doubles the computational effort.

One can improve upon this scaling by using more advanced algorithms, but there is no known algorithm that one could run on present-day computers that would make the computational effort scaling as a polynomial in the number of bits.

Checking for a number being prime or composite (rather than explicitly finding the composites) can actually been done in polynomial time. In highly optimized algorithms the computational effort scales with the sixth power of the number of bits ($n^6$).

$\endgroup$
  • 2
    $\begingroup$ The AKS primality test runs in polynomial time in the number of digits. $\endgroup$ – Ramchandra Apte Apr 10 '16 at 8:11
  • 1
    $\begingroup$ However, for practically interesting cases of large numbers (e.g. of the order of those employed as moduli for RSA encryption), AKS is nonetheless not a practically favourable method, for it would take too much computing time, despite some later improvements of it, if I don't err. One commonly employs the probabilistic method of Miller-Rabin, which doesn't prove the primality, in case it fails to find that the number is composite. (I read somewhere a suggestion to additionally do the Lucas test.) $\endgroup$ – Mok-Kong Shen Apr 10 '16 at 9:39
  • $\begingroup$ @RamchandraApte - good point, have modified my answer to clarify this. $\endgroup$ – Johannes Apr 10 '16 at 11:11
  • 1
    $\begingroup$ @Mok-KongShen It's well known. In case of Fermat test you have the bad property that a composite n can pass the test for all possible basis, but in the case of Euler pseudoprimes (Solovay Strassen primality test) or Strong pseudoprimes (Miller Rabin) this is not true. I.e. you can do the test for all basis between 2 and n-1 (prime with n) and if none fail you are sure that the number is prime. In fact for solovay strassen only half the tests are required and for miller rabin only one fourth. That's way we say that after k trials the chances of false positive is 4^(-k) or 2^(-k) $\endgroup$ – Bakuriu Apr 10 '16 at 13:59
  • 2
    $\begingroup$ @Mok-KongShen In other words we use the tests in a probabilistic way because a result with 2^(-100) probability of error is already good enough for us and only require a fixed number of trials. If you go on you can prove primality but this requires O(n) tests, i.e. more than plain trial and division. If Riemann hypothesis is true then it was already proved that you need only O(log^2 n) trials to prove primality, and you obtain a deterministic algorithm with complexity comparable to AKS or maybe a bit less (and surely with smaller constants). $\endgroup$ – Bakuriu Apr 10 '16 at 14:01
2
$\begingroup$

It sounds like you've got the gist. You actually only need to check up to $\sqrt{N}$. The reason for this is that if $N$ is divisible by $a$, with $a\geq \sqrt{N}$, then $N=ab$, where $b\leq\sqrt{N}$. So if you check up to $a$, you would have checked $b$ already. And even then there are better and faster methods that mathematicians have come up with. But however you do it, you have to make a lot of calculations.

And I mean a lot of calculations. big numbers here are numbers with hundreds of digits. Even if you only check up to $\sqrt{N}$, that is still over $10^{50}$ calculations, one hundred trillion trillion trillion trillion. Doing these calculations can be done quickly, but to do so many of them takes a while.

$\endgroup$
2
$\begingroup$

What I am missing in terms of it being hard to compute?

Let $k$ denote the length of your input.

If your input number is $N$, then $k\approx\log_2N$, and therefore $N\approx2^k$.

The runtime complexity of an algorithm is measured as a function of the input-length.

Since the runtime complexity of your algorithm is $O(N)$, it is also $O(2^k)$, hence exponential.

$\endgroup$
1
$\begingroup$

I would like to choose somewhat different perspective than in the other answers and say something about the topic in question. For me, it is hard to determine whether some (big enough) number is prime because prime numbers tend to exhibit strange enough behavior which still is not understood. See for example this conjecture. If this conjecture is correct then, in a certain sense, its correctness reveals why it is hard to determine when we will stumble upon a prime in the sequence of natural numbers because sometimes from the prime $p$ to the next prime $q$ we will have only to add $2$ to $p$ to obtain $q$, sometimes $4$, sometimes $80$, sometimes $222$, just choose even numbers which you like at the moment, any should do the work, should it?

Another reason, closely related to the above written thoughts, is that it is not easy to determine whether (big enough) number is prime because we do not have (correct me if we have) general enough and efficient enough methods that would settle whether some number is prime or not. To clarify this suppose that we investigate sequence $a_n=\sum_{i=0}^n 10^i$. This is just the sequence of numbers such that $n$-th term has $n+1$ ones in the base $10$ representation. Even for this sequence (which is simple to describe) we still do not have necessary and sufficient condition for primality of the terms in the sequence, so you can imagine how hard could it be to find the theorem of the form "$n$ is prime if and only if "this hols"" which is such that gives testing for primality in a straightforward easy-to-calculate way.

$\endgroup$

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.