00:05
这节课讲某平方个字类的相似算法。妥内利相斯算法又叫托雷利上克斯算法，其英文名称是托利相思。是快速求平方根的算法。为什么要求某平方根呢？这是因为比特币里面的压缩功用是已知X。但Y是不知道的。因此，必须求外。Y平方同1X的立方加7没得PP是非常大的质数。X是已知的，Y是未知的，所以简化出X的平方同一A的P。X1到P-1 1之间的整数常数X自然也是1到P-1的整数。
01:01
用穷句发，直接从1到P之间变离。需要的时间复杂度是op。但是批非常大，所以，所以穷句法是不行的。因此，我们需要用另外一种算法。本能里相字算法。这个算法的时间复杂都是。那个屁。6个P的平方，这是一个多项式的实验算法。这个算法是非踌的。在讲这个算法之前，我们先讲一个概念。二次生育和二次非生育。你们看一下这个概念是什么意思。X剩余的概念是X平方同1A的P。如果能求出X。那么A就是P的X剩余。
02:02
注注意啊，这这这个X生于4数的次数的A和P的关系。如果不能求出X，那么A就是P的X非剩余。当然这个P是大于等于3的。鸡叔叔。这个概念讲完了，我们还有一个。结论。二次剩余和二次非剩余的个数各占一半，这是什么意思？T它是一个数数，T-1就是一个偶数。嗯，二次剩余和二次非剩余各占以外，意思就是二次剩余的个数是。P-1÷2，但是非剩余的个数也是P-1÷2。我们看第一个T=11。嗯，那么这次剩余和非剩余的个数都是5个。
03:06
我们先看一下。嗯，我们看到A=A=1，那么A平方M的P等于。A=2 a平方等于4 a=3 a平方等于9。A=4 a平方等于5，这是因为余，余出了11 16，余出11，所以剩下的就就是5。A=5，那么A平方就等于3，所以A1~5就是14953。我们可以看到6~10就是35941刚好关于中间这个位置对称的。214953刚好也是不一样的，所以二次剩余呢，它是五个。
04:04
那是剩下的二次非剩余了，就是就是剩下5个了，就是10.5=5。我们再看P=13的时候。A1是1~12。我们看一下结果。我们可以看到A1~6A平方一四九三十二十。然后再看7~12，我们从下往上看一、四、九、三十，二十。同样也是关于中间这个位置对称的。然后，然后一四九三十，二十也是，嗯，这六个数字是不一样的，因此这个二次剩余的个数它是六个。剩下的。真下了6个数字，自然就是二次回春雨了。
05:02
因此。爱生宇和爱肥春雨的高数各占一半。然后下一步就开始就磨平方根了。嗯，看这个X平方同于A的P。求X。这个A可能是P的二次剩余，也有可能是P的二次非剩余。如果A是存在，就是A就是P的X剩余，如果不存在啊，那么A就是P的X非剩余，所以。所以求某平方根需要分为两步，第一步是判断是否存在某平方根，第二步如果存在了，就自然就求X。如何判断是否存在某平方案使用欧拉判别法？A也就是A，这个A就是常数。
06:04
A的A的P减一次方。唯一同于，那么X就是存在的。如果，如果可以。不不同意的话。嗯，那那肯定是不存在的。No.A的A的P减一次方，这个可以根据快速幂求出来。如，如果只要等于1，那么X就存在。如果存在，我们就进行第二波。第二步。这个算法就是可能相似算法，时间复杂度就是那个P的平方。融合起来。我们看到这红色的字体，这是非常重要的。
07:01
这个。首先把P-1拆分成S×2的T次方。这个S它是一个基数。可能这。可能是非常大的。就是普通的32位整数啊，64位整数都不够用了，因此只能用大整形。而2的T次方，这个T往往是非常小的。嗯。首，首先拆分成S×2的T次方。然后。然后就求一个二次回升语，这个二次回升语随便选一个可以就直接从2到P减一次方一次便利。
08:01
然后如何判断出来是非生鱼呢？就根据第一点里面欧拉判别法去判断。只要判断A的。C的A的P减一次方。唯一不不同于，那么C就是X回升1。然后C找到了，那么C=C的X次方，负的P。所以CE。也求出来了。下一步就是求X0，这个X0的就是我们需要求的跟。我们可以看到有A的2的X减一次方，这个肯定都是知道的，C也知道。但是C后面止住这么一大坨。这个T是已知的，G是G0 G1GT-2。
09:04
这些，这些数字都是未知的。这个指数相加，这个可能不太好看，所以等于后面这一坨。后面这一套是连成的形式。就是A的2的X+1次方再乘以C1的G0次方，再乘以C1的G1×2。然后再一直连连续乘这乘以C1的T减二次方，再乘以2的T减二次方。其中。G1 G0 1GT-2，它们的取值是只有0和1，没没有其他任何值，但是G0 G1阶梯减2这些值是如何计算的呢？就根据下面这个红色的字体这个这个公式计算。分裂。
10:01
这个A是那个上面上面这个。X平方同一A这这个值。然后用酒力。然后再乘以XT-1，再乘以XT-1，这这是什么意思啊？你可以忽略了这个角标。这个X就是。这这个角标我们看到是从大往小的，也就是说这个是大号的X。然后。A×X再乘以X，然后再乘以2的T1减二次方。看这个是否同意意。如，如果和1同于，那么这个阶梯减T。那么就就等于如果和1不同于。这个阶就等于0了。如果J=0，那么C1的J×2。
11:05
这这这整个是就等于一了。我们再看下面的这个。这这也是，这是上面这个这个X0直接求出来了，下面这个是一个递推式。这个对，地推式这个后面这个PI-1，这个是大号的S。然后求出小号的X。C.CC1这个就是那个非剩余的。其实C的S次幂。这个是需要求J的，这这个递推，只有当J=1的时候。嗯，才能用这个地推式，否则。
12:02
否则就是直接那个小号的X就等于大号的X。注，注意这个红色的字体。然后。这个红色的字体讲完了，然后。这个代码是如何写的？我们可以直接看代码第一步，P-1拆分的S×2的T次方的形式，我们看代码。就是这个地方。S等于。体减1次方。这里面就是S，它是又一位，也就是除以2。除二，然后T加加。就是。就是T2的T次方。当S是。奇数的时候就就退出来了，这个时候S=2的T次方就求出来了。
13:03
第二步。当T=1的时候，也就是T。余初一，没的是。这个网上很多地方是直接用了这个结结论去。P和1同于M4，然后X=A的4的P减一次方，这个网上还最喜欢用这个结论，其实这个步骤可以不用的。你看这个地方我都直接注释掉了。为什么我不需要这一步呢？这是因为这一步已经计算出来了。我们再看下一步找一个二次飞鱼，它这个是怎么找的呢？我们可以看到。所以从2开始。
14:01
然后磨的。如果，如果是不，不等于0。不，不等于0，就是1这一次二次剩余，如果是二次剩余，那直接还还要去吗。一直一直找到C不是二次剩余的时候，那么就就是二次非剩余。这个回声鱼就是编译出来了，这个编译速度是很快的。然后。下一步。XT-1。等于A的A的X加一次方，这个是把这个大号的X给求出来了。如，如果当，当T=1的时候，这个时候就已经是X0了，这个X0不，不就是。
15:01
根嘛，就就已经求出来了。但是我们也需要判断X。大于等于2的情况。那么就需要用这这个便利了。遍历的时机就从ti，因为TT已经是一个常数了，所以我就用ti这这个变量来遍历，从T到2变利，然后不长是负一，我们看代码。这个X，这个是大号的X已经求出来，也就是A的A的X加一次方，然后便利从T到2之间。然后先求底数，A是底数就是A，然后乘以大号的X，再乘以大号的X。我们看代码。这个A这个。这个写的有点长，这就好看嘛，就是N1×X，再乘以X，然后B。
16:06
第一就是指数。也就也就是上面的这个2的PI减二次方，这个这这里也是2的T减二次方。啊，BB.这个地方。同样也是2T-A次方。然后判断A1的BB次方是否和11同于。就是AA的BB次方。没得皮。然后会。是是否同一，如果同鱼了，那那么就用这个递推式。这个小号的X。写代码是需要忽略国标的。
17:00
这个T是这个代码里面T。是什么意思啊？就是C1的A的T-T次方。然后。在X乘以这个T1。然后我们可以看到这个坐标是可以忽略的，否则，否则XT-2=XT-1，也就是小号的X等于大号的X。反正代码里面直接不写了。因为因为并没有做任何操作的。然后下一步就。嗯，下一步又是便利。然后又求这个AA。然后这这这个时候，小号的X又变成了大号的X，然后。
18:03
然后求A，求BB，然后。然后如果J=1的时候，因为是小号的X等于大号的X，再乘以X11~2的T-TX次方。一直循环。学到什么时候结束了，也就是PI=2的时候。这个就。就求出了X，这个ti=2 X就等于0了，这个时候X0就求出来了。S0就是。就是我们需要的根，当然还有一个就是负的X0，负的X0。再加上一个P，就是P+X0。我们可以看啊，另外一个X。首先负那个X就是负X，然后P减。
19:01
就是P-X。这样。这样两个根都求出来了。我们可以看到根，根源里面本身有一个Mo SQ rt函数。也就是说有现场的求平方根的方法，我们看一下。这个第一个一处里面是用了我们自己写的平方根的方法。呃，第二个里面是系统自带的模平方根函数。我们运行一下。稍等一下，速度有点慢。
20:03
我们可以看到。这是第一个一处里面的结果。这个当P非常大的时候，求出的结果也是非常大的。那再看第二个系统自带的。求平方根的方法。我们看这两个方案它是一样的。那看第二个。X平方等于55，然后一四百零三。求出就是643。然后系统自带的也是60人，我们自己算出来的有两个人，系统自带的只有一个人。是，所以如果用系统自带的函数这个另一个根需要还需要你自己算出来。
21:03
我们再看第二个。186。A这个是X平方。等于186，然后摸的401。然后求出来X就是304。然后系统自带的算出也是304，这说明我们自己写的方法是没有问题的。注意注意，这里有一个地址。这这个地址看一下。这里面介介绍了是如何求某平方根的问题。我也是参考这篇文章来。写代码了。你们自己看一下吧。
我来说两句