西丰新闻网
国际新闻
当前位置: 首页 >> 国际新闻 >> 正文

你所想知道密码背后的数学——同余运算 Part II


文章作者:www.ipssc.com.cn 发布时间:2020-02-15 点击:1458



本文作者[会见数学创作团队]:蘑菇长颈鹿

在前面的文章中,我们主要介绍了同余运算的来源和模的加减运算。乘法和除法在实数运算中也起着非常重要的作用。在这篇文章中,我们将介绍模的乘法和除法,模的乘法和除法,以及模的求逆。

module

module的乘法运算是

同样,我们将通过一个实例来理解它。

让我们假设A=4,B=5,C=3。如果上述等式成立,等式的左侧等于(4*5)mod 3=20 mod 3=2,等式的右侧是

((4 mod 3)*(5 mod 3))=(1 * 2)mod 3=2 mod 3。

因此,我们可以从实际计算中看出这个等式成立。我们不妨看看下面的实际图例,看看这个操作是如何工作的。

如果我们把(4×5) mod 3看作是以步长4绕一个圆顺时针旋转5次,那么我们可以得到上图中的图(1)。如同加法和减法一样,在模运算中,围绕圆的完整环不影响端点的位置。因此,从上图中的(2)和(3)可以看出,加厚部分是对终点有实际影响的运动。图(3)帮助我们节省了额外的步骤。如果这个问题中的次数是3的整数倍,那么无论采取多少步,模块的最终结果都是,所以图(2)帮助我们节省了额外的移动次数。

module

的幂运算因为模幂运算实际上是一个重复的乘法运算,所以在我们通常的计算过程中,a b通常会得到一个非常大的数。例如,以下两个例子:

2 { 90 }= { 256 }=.

这会在我们的计算过程和计算机的工作过程中造成大量的工作量。即使我们找到了答案,也很难直接计算出它的模型。

那么你如何减少计算?下一步是使用模幂运算。

假设我们现在想计算2^90 mod 13。如果我们先计算2 90,我们需要完整准确的数字来计算其余的,但是我们的计算器只能显示2 50以内的完整数字。这时,我们需?鲆桓鲂〔鸱郑?2 90=2 50× 2 40,然后再用模乘问题来解决它。

在第二个问题中,对于7的幂数,普通计算器只能完全显示7 ^ 10。我们如何使用计算器计算7^256 mod 13?显然,把7 256分成25 7 10和1 7 6不是很有效。

事实上,模幂运算还有另一个表达式。也就是说,

这个表达可以帮助我们更快地解决问题。

当用例子对7求幂时,让我们看看前几个余数的规律。

在表的最后两行,我们发现结果是1和?1、当我们把它变成原始形式时,我们会得到预期的结果,用?以1为例(以同样的方式引入1),意思是

因此,我们可以使用1和?1是帮助我们简化模幂运算的特殊数,但是在我们的计算过程中,我们会发现并非所有的运算最终都会得到1或?例如,这个问题:计算2^40(mod10).就像前面的主题一样,当对7求幂时,遵守前几个余数的规律。

从上面的计算,我们可以看到,虽然我们没有得到1或?1,但结果是四组一个周期,所以我们有

因此,在实际操作中,我们经常选择以上三种方法根据不同的题目进行计算。

module

的除法运算我们考虑4≡8(mod4),因为2?4(mod4),所以我们不能简单地将等式两边的2除。这表明模的除法一般是无效的。然而,如果我们加上k和c是互质的条件,那么模除法成立,如下式所示:

模逆运算

说到逆运算,我们可以回忆起什么样的数叫做逆)。

一个数乘以它的倒数等于1。我们从一些基本运算中知道:

数A的倒数是1/A,因为A?(1/A)=1 .(例如,5的倒数是1/5)除0之外的所有实数都有倒数。数乘以a的倒数等于除以a(例如,10/5和10?1/5相同)

虽然在模块的运算中没有除法运算,但我们仍然有逆运算。对于模拟数的逆运算,我们可以得到:

在了解了模的逆之后,如何找到逆就成了我们现在的主要问题。找到一个(modC)的简单方法是:

放一个?B在B模式C中,从0到C?1依次计算。什么时候?当B模C=1时,得到的B就是需求。

注意这里的B模C只存在于0到C的整体中,所以在测试过程中没有必要给B一个更大的值。让我们看看下面的例子:

下一条: 魅族科技12月13日会揭晓一按成诗OMA,已有网友收到珠海小厂快递