我认为在密码学中重要的不是质数本身，而是质因数分解问题的难点

假设你有一个非常非常大的整数，已知是两个质数m和n的乘积，要找出m和n是什么并不容易。RSA等算法就是基于这个事实。

顺便说一下，有一篇发表的算法论文可以在可接受的时间内使用量子计算机“解决”这个质因数分解问题。因此，当量子计算机问世时，新的密码学算法可能不再依赖质因数分解的“困难”:)

因为没有人知道一个快速的算法把一个整数分解成质因数。然而，检查一组质因数是否乘以某个整数是非常容易的。

有一些很好的资源可以加强加密。这里有一个:

http://research.microsoft.com/en-us/groups/crypto/firstcrypto.aspx

从那一页开始:

In the most commonly used public-key cryptography system, invented by Ron Rivest, Adi Shamir, and Len Adleman in 1977, both the public and the private keys are derived from a pair of large prime numbers according to a relatively simple mathematical formula. In theory, it might be possible to derive the private key from the public key by working the formula backwards. But only the product of the large prime numbers is public, and factoring numbers of that size into primes is so hard that even the most powerful supercomputers in the world cant break an ordinary public key.

布鲁斯·施奈尔的《应用密码学》是另一本。我强烈推荐这本书;读起来很有趣。

为了更具体地说明RSA如何使用素数的性质，RSA算法主要依赖于欧拉定理，该定理指出，对于相对素数“a”和“N”，a^e等于1模N，其中e是N的欧拉totient函数。

质数是怎么进来的?为了有效地计算N的欧拉totient函数，需要知道N的质因数分解。在RSA算法中，对于一些质数“p”和“q”，N = pq，那么e = (p - 1)(q - 1) = N - p - q + 1。但是如果不知道p和q, e的计算是非常困难的。

更抽象地说，许多密码学协议使用各种活板门函数，这些函数易于计算但难以反演。数论是这类活板门函数的丰富来源(例如大素数的乘法)，而素数是数论的绝对中心。

质数本身并不重要，重要的是处理质数的算法。特别是求一个数(任何一个数)的因式。

如你所知，任何数字至少有两个因数。质数有一个独特的性质，它只有两个因数:1和质数本身。

The reason factoring is so important is mathematicians and computer scientists don't know how to factor a number without simply trying every possible combination. That is, first try dividing by 2, then by 3, then by 4, and so forth. If you try to factor a prime number--especially a very large one--you'll have to try (essentially) every possible number between 2 and that large prime number. Even on the fastest computers, it will take years (even centuries) to factor the kinds of prime numbers used in cryptography.

事实上，我们不知道如何有效地分解一个大数字，这赋予了密码算法的优势。如果有一天，有人想出了如何做到这一点，我们目前使用的所有加密算法都将过时。这仍然是一个开放的研究领域。

我建议你读《代码中的数学之旅》这本书。这本书有一种很好的接地气的感觉，这是令人惊讶的，因为它是关于密码学的。这本书总结了Sarah Flannery从一个孩子学习谜题到在16岁时创建Cayley-Purser (CP)算法的旅程。它对单向函数、数论、质数以及它们与密码学的关系给出了令人惊讶的详细解释。

让这本书更具体地回答你的问题的是Sarah试图使用矩阵实现一个新的公钥算法。它比使用质数要快得多，但发现了一个可以利用它的循环漏洞。事实证明她的算法更适合作为私人加密机制。这本书是使用质数进行加密的一个很好的证明，因为它经受住了时间的考验和非常聪明的人的挑战。