1.8.模平方根之奇波拉算法Cipolla二次剩余原创

这节课讲。我平方根起步了算法。起不来算歪呀？嗯，它的英文名称是C，也是快速求某平方根的算法，上节课讲的是用同内力千克算法。嗯，他们的时间复杂度都是。都是那个P的平方。这都是二项式的时间算法。为什么要求摸平方根？这类就不用讲了，因为上节课已经讲过了。然后如何求某平方根，也就是X平方等于A2的PA是一个常数？9X。首先是判断某平方根是否存在。我平方根一一。有某平方根的时候，就就2个根，如果没有，那么那肯定就是0个根了，用欧拉判别法去判断。

嗯。如果存在X。然后就就需要求X这个地方就用起步啦算法求X。嗯，注意这个红色的部分。NW是二次飞升鱼。W=B平方减A。然后I平方等于W，因为W它是二次非剩余。所以I是不不能求出来的。所以AA平方就相当于负数。注，注意A平方不等于负一啊，它它只能等于W在这个地方。那后面呢，等是要用到这个结论。

那那么X=B+A。还有就是。你可以理解成负数的虚数。B+A的A的P加一次方就是以其中的一个一个人。这这这个算出来了。虚步的一定是0。注注，注意WP的二次回升语。这这个W是如何求的呢？它自自然就是便秘啊。1从1到P减一遍利总总能找到一个适合的W，我们看一下代码是融合起的。这个是起不拉算法。首首先肯定是判断是否存在，如果存在，进行下一步。然后BW，然后。

一从一开始。这B平方减A。1从一开始，然后W等于。B,平方。减A。然后判断W是不是。那次飞升鱼如果等于0的时候，它自然就W就已经找，B和W都已经找不到了。就是如果。判断出来它不不为0，也就是说W并不是二次分身率，那它自然还需要循环。然后BB+1，然后把W。下一个W就出来，然后一直到W是P到二次回升，雨就退出去了。嗯。然后求XX，它是等于B+A的，它的P减一次方，这个我们看一下结果。

一直就是个虚根。第。No.我们看一下这这个浪是是什么。为X是10步，也就是B。我就是虚部。就是这个IW是什么意思。这个W也就是左边这个W也就等也就是A的平方，因为A平方不能直接等于负一。而且我们也算不出来，所以这个W是必须手动存下来的方面，嗯，做数学运算。我们。我们看看一下代码。这个虚跟求证，BB+I也就虚跟就是I嘛，所以它是唯一的。

W,那自然就是上面W已经求出来了。然后2的P加一次方，也就是这个P2 p2就是等于P+1次方除以2。然后就这个。区根的2的T加一次方。然后求出来X。就是其中的一个根，另外一个根就是P-X。这样就。嗯。2两个根都求出来了。And.这这这红色的部分你是一定要记住的，因为这个这写写代码直接涉及到这红色的部分。然，然后我们再看下面。就是用到的结论这个，这是是什么意思啊，这是因为证明X是不是一个跟会用到上面的三个结论这个证明。

其实。这周我就不不不讲了，因为。你因为你你写代码是用不到的。然后下面就讲这个负数的计算，也就是。B+I的I的P加一次方。因为这个负数。不是，并不是传统意义上的负数，所以IP房是不能等于-1的。这这个我已经强调好几次了。A平方它是等于W，这个地方也做也做了一个提示。然后。负数的计算有两个计算，第一个计算是负数相乘，第二个是负数的快速幂。

首先看两个负数相乘A。A=a.S+a.Y×A。a.a.X就就是实部，a.Y就是虚部。这个你你你们都应该看懂了，然后BB=B的X。再加b.Y×2。b.X自然就是实部b.Y就是虚部的。然后求A×B。A×B，自然就是直接相乘的，就是一个是判。这是mathematic里面就是展开。那如如何展开，就是a.X再乘以b.X然后再加上a.X再乘以以b.M。我也这种尘爱。然后。然后再加a.Y×I，然后再乘以b.X再加a.Y再乘以I，然后再加b.Y再乘以I。

反正分别相乘，然后相加就行，我们看一下结果。稍等一下。我们可以看到这结果已经出来了，我们直接看第第二个结果，它是按。I的顺序排列。我们看这是这一部分就可以了，然后我们再看一下代码是如何写的。代码相乘，那我们自然也需要看到代码相乘的。付出成吧。也就是A浪B浪，然后P就是。叔叔。如何求呢？我们先看10步。

左边的10部有哪些？就是a.X×b.X然后这里还有一个再加个a.Y×b.Y然后再乘以A平方，这个A平方这个上面已经强调过了。A平方等于W，也就是10步就等于这这两个，这两项相加，然后代码是怎样的？我们看一下代码起步就是res.X。L11.x=x.a.X+b.X和。那这这个是对应的。然后a.Y×b.Y再乘以W。就和这个是对应的。a.Y×B的Y，再乘以A平方，这个I平方刚好等于W。所以这这两个已经对上了。

再看虚部，也就是RS.y。i.Y.先看第一项a.Y×b.X。就是这个a.Y×b.X然后a.X×b.Y。a.X×b.Y这样虚部也求出来。10个虚部都求出来，自自然这个负数相乘，那结果也就求出来了。这是复数相乘。负数相乘求出来，然后再再来一个负数，负数的快速幂。负数的快速幂就是意思，A它是一个负数，BB它是一个指数，但是指数它只能是大于等于0的整数。这个快速米，这个之前。已经讲过了，采用二进制拆解法也是把B拆分成二进制的形式，然后求A的。

一次方A的平方A的四次方A的八次方。这个地方就不不讲这个快速密码，这个根据之前的。嗯，快速的方法就可以了。嗯。6语言中用的是Mo SQ rt函数求某平方根，我们来看一下运行的结果。代码里面有。自己写的model X函数，然后系统自带的model X函数，我们看一下结果。我们可以看到。这个系统自带的函数和我们自己写的函数的结果是一样的。

这个是一个非常大的数字。然后第二个。63和63对应97。九七三百零四和304对，这答案是平面的。