詞彙表

Select one of the keywords on the left…

整除和素数实际应用

揭示所有步驟

北美是各种各样的蝉群的家园。这些蝉有一种奇特的特性,即它们每隔多年的夏季才出 来繁殖——剩余时间它们在地下度过。

例如,佛罗里达州和密西西比州的蝉每13年出现一次。伊利诺斯州和爱荷华州的蝉只每 17年出现一次。但是没有一种蝉有12年、14年、15年或16年的出现周期。

13和17都是质数 - 这是有充分理由的。想象一下森林里有捕食者杀死了蝉。这些捕食者 也会定期出现,比如每6年出现一次。

现在想象下蝉的出现间隔是每${n}年(${isPrime(n) ? '素数' : '非素数'})。 这两种动物每${lcm(n,6)}年会相遇一次,这就是6和${n}最小公倍数最大公约数乘积

4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

不同的蝉出现周期长度, 决定了蝉和捕食者相遇的时间。

如果蝉的间隔周期是像13和17这样的质数,这个数字看起来就要大得多。这是因为素数 不与6共有任何因子,所以在计算最小公倍数时,我们不会消去任何重复因子。

当然,蝉不知道素数是什么,但在数百万年的时间里,进化证明了素数周期是最安全的。 捕食者似乎已经随着时间的推移而灭绝,但素数周期仍然存在。

密码学

素数在现代最重要的应用之一是在一个称为密码学的数学领域。数千年来,人们一 直试图隐藏信息,以便只有预期的接收者才能读懂它们 —— 这被称为加密。每个人都在 使用加密学,从将军们在战争中交换秘密命令到个人电子邮件或网上银行信息。

人们总是试图想出更好、更安全的加密方法,但一段时间后,他们都被更先进的算法打 破了。在第二次世界大战中,德国军队使用了一种称为“谜”的设备:由键盘、旋转的轮 子和插头组成的复杂机器。它使用了1.58万亿亿(即158后面是18个零!)个可能性中的一 个来加密消息,人们普遍认为密码是不可破解的。但由数学家阿兰·图灵领导的英国特勤 局,制造了首批成功破译密码的计算机。

德国四转子加密机

今天的计算机更先进,每秒能尝试数百万种可能性。为了开发更好的加密算法,你必须 找到一个对强大的计算机来说也很困难的数学运算。计算机在加法、减法、乘法和除法 方面速度惊人。然而,事实证明,计算机将大整数分解成素数的速度非常慢…

敬请期待 – Alice和Bob的RSA示例

这种加密算法被称为非对称加密算法,它的三位发明者: Ron Rivest,Adi Shamir和 Leonard Adleman于1977年发表了这一算法,三人名字的缩写RSA被用来作为该算法 的名字。事实证明,自1973年以来,英国特勤局就掌握了一种非常相似的方法,但一直保 密到很晚。

今天,世界各地的计算机交在换数据中都使用了素数。每当你发送电子邮件或访问一个 安全的网站,你的手机或笔记本电脑就会默默地生成许多大素数,并与其他计算机交换 公共密钥。