词汇表

选择左侧的一个关键字...

整除和素数最大公约数

阅读时间: ~5 min

一位建筑师正在为一个18米乘30米的大庭院规划地板,她希望它被正方形瓷砖覆盖,长宽 两个方向没有任何间隙和重叠。她能用正方形的最大尺寸是多少?

瓷砖尺寸:${x}m.

就像之前一样,这个问题不是关于几何的 - 而是关于能否整除的。瓷砖的两个边长必 须同时整除18和30,那么最大可能的数是。这被称为18和30的最大公约数或 简写为gcd。

我们可以再次使用素数因子来计算两个数的最大公约数。记住, 一个数的除数必定包含有这个数的部分素数因子。

18
=
2
×
3
×
3
30
=
2
×
3
×
5

假设X1830的最大公约数.那么X 整除18, 因此X的素数因子也在2, 2_和{span.number-ball.small.l-blue}3_中。同理, X 整除30, 因此X的素数因子也在 2, 3 和 _{span.number-ball.small.l-green}5_中。

要找到X,我们只需要将所有在1830出现的素数相乘:

X  =  2 × 3  =  6.

现在我们有了一个简单的方法来找两个数的最大公约数:

  1. 找到每个数的素数因子。
  2. 将两个数里都出现的素数因子相乘。

素数又一次是特殊的:两个不同质数的最大公约数总是, 因为它们不共有任何素数因子。

密码学

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

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

德国四转子加密机

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

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

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

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