1.9.模立方根之佩拉尔塔算法Peralta三次剩余原创

这节课讲莫力方根之佩拉塔算法。佩拉塔算法英文名称是per尔罗特，是快速球莫力方根的算法。之前讲过，求某平方的算法分别是和内相似算法和起不拉算法。嗯，佩拉的算法跟起波拉算法思路是非常相似的。首先，我们为什么要求往里方呢？就是因为比特币里面s SE c bw ke的椭圆曲线方程。Y平方同于X的立方加7那的P，已知Y求X，嗯，虽然比特B里面没有直接根据Y求A是这种情况，但是跟私钥跟施压的联系是非常大的，所以你必须求回求地方。嗯，Y平方同一X的立方加7末的P可以，因为因为Y是已知的，所以可以简化成X立方统一A的P，这种形式A是一个常数。

然后X。嗯，如果求X，传统方法是直接从1到P点1之间便利。需要的时间不再说是op。既是一个非常大的支数。所以。用这种便利方法肯定是不行的。定制就需要采用现在讲的贝拉尔法算法，讲这个算法之前，我们先看一下三次剩余的规律。闺女的话得。T=11，这种情况A肯定就是1~10。然后把所谓的3次剩余给求出来。

A是1~10。然后我们看到A立方也就是3次，剩余也是1~10之间的数字，并且都只出现了一次。再看第二种情况，P对13 P对13，我们再看一下所谓的乘车剩余。门可以看到A是1~12，然后A立方就不太一样了。一出现了3次。8出现了三次，12出现三次，5出现了三次，也就是说三三次剩余。嗯。相同的三次剩余分别有3个，当然三次剩余的总数肯定只有1/3了。

嗯，这两种情况为什么不一样呢？这是因为P-1，嗯，能够除以3，首先看BP=10这种情况，P-1=10。那10不能被三乘除，不能被3整除断，所以这个三次剩余都存了，并且都只有一个根了。如果。如果P-1。等于12肯定能被3整除，所以三次剩余它就有三个根了，当当然三次剩余数量也就变成1/3。3次剩余的规律找到，然后我们就想摸评判人。M求平方根，也就是X立方同于A，没得P。跟之前的9平方根的方法是一样的。首先是判断是否存在魔力。放开。

嗯，第二步就是写N。就。球磨立方根有三种情况，0个根、1个根、3个根。之前讲到球磨平方根的时候只有两种情况，也就是0个根和2个根两种情况。嗯，因为多了一种情况，所以也多了一个判断，这个判断就是求最大公因数。T-1和3，求最大公因数。如果公约数唯一的时候，那么肯定是存在毛地方，并且只有一个。如果最大公约数为3。那么可能就可能有3个最最可能这两个字，因为也有可能没有电脑。嗯。这这这句就要通过的判别法去判断A的3的减一次方。

和1是否统一？如果等于1，那么就有3个，如果不等于，就没有根。如果有跟这种情况，然后进行第二步。当只有一个根的时候，X=A的3的2P减一次方。这个答案就直接求出来，我们看一下代码。嗯，首先这一步是判断有多少个跟。如果只有一个根的时候，那么就是先把指数给求出来，A-1÷3。然后再就A的。T次方。当只有1个根的时候已经求出来了，当有3个根的时候，就用配法算法。

这个算法的时间复杂度是一个PA的立方。嗯，方法首先是。A的立方等于W。同意B的立方减A，这个跟之前讲的某平方跟它其他的算法是一样的。会非常类似。嗯，如何求B和W来那那只直接用最传统的方式直接便利，从1到P-1之间便利。我们看一下代码。代码就是BB从一开始，嗯，W等于。B的立方，然后再减A，然后判断W是不是3次剩余，如果是3次剩余就直接退出去了。如果不是，如果不是，如果是3次非剩余，你就只能直接退出去了，如果是3次剩余，那嗯，继续下一次循环。

嗯，1和W都求出来，然后就求直接求结果了。这个是一个B-A的3的P平方加P+1，这个就是求负数的快速幂，这个负数的快速率有点区别，区别在于负数。这个有实部，有虚部，对虚部，还有一个，还有一个A平方的虚部。嗯，我们看一下代码。这个。论。

我们能看代码里面也是有10部I的序部，A平方的序部。A的立方跟之前跟A平方其实跟某平方根是差不多吧，某平方根就是A平方等于W2立方。这个地方就是按立方等于W。嗯，看这个直接求快速率。快速幂求完了，然后需要要求10步，这个10步就是其中的一个根在平方根里面。不，不太一样。这是因为这个付出的快速面。只有实部、虚部是为0的。所以被就直接给请出来了。这个去10部。

求出了其中一个S，但是另外的你是不知道的。我平方根里面是非常容易求的，因为另外一个根就是负的X。嗯，这个地方。有另外有另外的两个是你不太好求，你只要需要通过这一步球。3g=K的3的P减一次方。这个K等于多少啊，你是不知道的，只能从1到P点1这电力我们看看一下代码，求周期circle。然后。3到P-1，然后再求便利。KK从一开始。变便利到12g≠1的时候就退出循环，12g求出来了，然后另外两个边也就求出来，另外两个人就是分别是X×3g和X×3g的平方。

这个大体步骤就是这样了，但是负数怎么计算呢？这个负数的形式就是x.a再加x.B×A再加x.C×A×A。嗯，怎么求，肯定是分别按向展开。直接看结果。然后根据A的顺序排列。然后我们看一下代码怎么写的。看辅助香肠。

这是9西部啊，叶叶是点。实我们看一下。这个是x.a×y.a。这个地方也出来了，就是点A×Y的A，但是还有还有是部还有一些。也就是黑的地方。A的立方等于W，所以就是x.C×y.B。a.C×y.B然后再乘以W。s.B×y.C。点B×y.C×W。这个实部求出来了，然后再看虚部。区部。也就是按。

x.B×Y点。x.B×y.a然后x.a×y.B。x.a×y.B然后区部还有一个就是A的四次方。它立方等于W，所以就是x.C×y.C再乘以W这个。0点Z×y.Z×W。这个区部切除来，然后还有还有个区部，就是A平方的区部，A平方的区部。就就是这一坨，但是点申请外而已。有一个乘Y。

a.B×y.B。点B×y.b.a×y.C。就是改了1×Y点3，这样付出。两个负数相乘，就求出来了。还有一个就是复苏的快速，复苏的快速跟之前讲的快速是一样的，也就是采用是拆解法，把B根拆解乘二进制，分别计算A的一次方，A的二次方，分到4次方，一次计算即可。嗯，我们直接看一下五立方根的。运行结果。我们看看一下代码。

嗯，首先是看P=11这种情况。我们之之前也讲过皮特十遗症。这只只有一个人。就是因为T减一等10 10不能被三整除，所以某立方根那肯定只有一个。先看一下结果。我们可以看到，这个答案就出来了。我们可以看到。A=8的时候，答案就是2，因为2的三次方就等于8，并且只有一个圆。这是这是一个根的情况，我们再看另外一种情况，也就是三个根的情况，997。我们我们可以看到这个答案，要么有3个根的答案，要么答案就是悟空。这这是因为。

九百九百九十七减一九百九十六两百三出，所以可能有。有根的时候就已经是3个根，没有根的时候就没有根了。这算法就讲到这里了。