English
中文
Deutsch
Română
Türkçe整除和素数最大公约数
一位建筑师正在为一个18米乘30米的大庭院规划地板，她希望它被正方形瓷砖覆盖，长宽 两个方向没有任何间隙和重叠。她能用正方形的最大尺寸是多少？
瓷砖尺寸:
就像之前一样，这个问题不是关于几何的 - 而是关于能否整除的。瓷砖的两个边长必 须同时整除18和30，那么最大可能的数是
我们可以再次使用
18 | = | 2 | × | 3 | × | 3 | ||
30 | = | 2 | × | 3 | × | 5 | ||
假设__{.m-red}X__是__{.m-green}18__和__{.m-blue}30__的最大公约数.那么__{.m-red}X__ 整除__{.m-green}18__, 因此__{.m-red}X__的素数因子也在_{span.number-ball.small.l-blue}2_, 2_和{span.number-ball.small.l-blue}3_中。同理, X 整除__{.m-blue}30__, 因此__{.m-red}X__的素数因子也在 2, 3 和 _{span.number-ball.small.l-green}5_中。
要找到__{.m-red}X__，我们只需要将所有在__{.m-green}18__和__{.m-blue}30__中
X = 2 × 3 = 6.
现在我们有了一个简单的方法来找两个数的最大公约数：
- 找到每个数的素数因子。
- 将两个数里都出现的素数因子相乘。
素数又一次是特殊的：两个不同质数的最大公约数总是
密码学
素数在现代最重要的应用之一是在一个称为__密码学__的数学领域。数千年来，人们一 直试图隐藏信息，以便只有预期的接收者才能读懂它们 —— 这被称为加密。每个人都在 使用加密学，从将军们在战争中交换秘密命令到个人电子邮件或网上银行信息。
人们总是试图想出更好、更安全的加密方法，但一段时间后，他们都被更先进的算法打 破了。在第二次世界大战中，德国军队使用了一种称为“谜”的设备：由键盘、旋转的轮 子和插头组成的复杂机器。它使用了1.58万亿亿(即158后面是18个零!)个可能性中的一 个来加密消息，人们普遍认为密码是不可破解的。但由数学家阿兰·图灵领导的英国特勤 局，制造了首批成功破译密码的计算机。
德国四转子加密机
今天的计算机更先进，每秒能尝试数百万种可能性。为了开发更好的加密算法，你必须 找到一个对强大的计算机来说也很困难的数学运算。计算机在加法、减法、乘法和除法 方面速度惊人。然而，事实证明，计算机将大整数分解成素数的速度非常慢…
敬请期待 – Alice和Bob的RSA示例
这种加密算法被称为__非对称加密算法__，它的三位发明者: Ron Rivest，Adi Shamir和 Leonard Adleman于1977年发表了这一算法，三人名字的缩写__RSA__被用来作为该算法 的名字。事实证明，自1973年以来，英国特勤局就掌握了一种非常相似的方法，但一直保 密到很晚。
今天，世界各地的计算机交在换数据中都使用了素数。每当你发送电子邮件或访问一个 安全的网站，你的手机或笔记本电脑就会默默地生成许多大素数，并与其他计算机交换 公共密钥。