<p>I think what are important in cryptography are not primes itself, but it is the <strong>difficulty</strong> of <em>prime factorization problem</em></p>

<p>Suppose you have very very large integer which is known to be product of two primes m and n, it is not easy to find what are m and n. Algorithm such as RSA depends on this fact.</p>

<p>By the way, there is a <a href="http://arxiv.org/abs/quant-ph/9508027" rel="nofollow noreferrer">published paper</a> on algorithm which can "solve" this prime factorization problem in acceptable time using quantum computer. So newer algorithms in cryptography may not rely on this "difficulty" of prime factorization anymore when quantum computer comes to town :)</p>
Why are primes important in cryptography?
<p>One thing that always strikes me as a non-cryptographer: Why is it so important to use prime numbers? What makes them so special in cryptography?</p>
<p>Does anyone have a <em>simple</em> short explanation? (I am aware that there are many primers and that Applied Cryptography is the Bible, but as said: I am not looking to implement my own cryptographic algorithm, and the stuff that I found just made my brain explode - no ten pages of math formulas please).</p>