I have not studied the literature on primality testing or prime factorization but still I often wonder about the complexity of the algorithm that keeps the whole world secure.
Consider any interval of length $N$ on the real line. For $N=2$ we know that we would not encounter more than one prime in any interval of length $N$. Now, intuitively I feel that this should be true for any number $N$, eventually i.e. there should exist a limit $L$ such that for all intervals $[n,n+N]$ for every $n>L$ there can exist only one prime in that range. Thus primes should become increasingly sparse (in this strong sense). Even though this result does not guarantee to reduce the complexity of finding prime numbers, it feels that it should make my job easier.
But alas, the twin prime conjecture lays fail to all of the above. Recently a professor proved a weaker version of the twin prime conjecture. He showed that for a given finite number $M$ (~ 7 million ) there are infinitely many prime pairs with difference less than $M$. Now people have improved upon his results and brought down the number $M$ to ~ 600, but it seems unlikely that the twin prime conjecture could be proven using his methods. Nevertheless, even this result re-inforces the difficulty of finding prime numbers.
Consider any interval of length $N$ on the real line. For $N=2$ we know that we would not encounter more than one prime in any interval of length $N$. Now, intuitively I feel that this should be true for any number $N$, eventually i.e. there should exist a limit $L$ such that for all intervals $[n,n+N]$ for every $n>L$ there can exist only one prime in that range. Thus primes should become increasingly sparse (in this strong sense). Even though this result does not guarantee to reduce the complexity of finding prime numbers, it feels that it should make my job easier.
But alas, the twin prime conjecture lays fail to all of the above. Recently a professor proved a weaker version of the twin prime conjecture. He showed that for a given finite number $M$ (~ 7 million ) there are infinitely many prime pairs with difference less than $M$. Now people have improved upon his results and brought down the number $M$ to ~ 600, but it seems unlikely that the twin prime conjecture could be proven using his methods. Nevertheless, even this result re-inforces the difficulty of finding prime numbers.
