模開方演算法

㈠ 開方的計算方法

開平方運算也即是開平方後所得的數的平方即原數，也就是說開平方是平方的逆運算。
例：求256的平方根

第一步：將被開方數的整數個位起向左每隔兩位劃為一段，用逗號分開，分成幾段，表示所求平方根是幾位數。
例，第一步：將256，分成兩段：
2，56
表示平方根是兩位數（XY，X表是平方根十位上數，Y表示個位數）。

第二步：根據左邊第一段里的數，取該數的平方根的整數部分，作為所要求的平方根求最高位上的數。
例：左邊第一段數值是2，2的平方根是大約等於1.414（這些盡量要記得，100以內的，尤其是能開整數的），由於2的平方根1.414大於1和小於2，所以取整數部分是1作為所要求的平方根求最高位上的數，即所要求的平方根最高位X是1。

第三步：從第一段的數減去最高位上數的平方，在它們的差的右邊寫上第二段數組成第一個余數。
例：第一段數里的數是2.第二步計算出最高數是1
2減去1的平方=1
將1與第二段數（56）組成一個第一個余數：156

第四步：把第二步求得的最高位數（1）乘以20去試除第一個余數（156），取所得結果的整數部分作為第一個試商。
例： 156除以（1乘20）=7.8
第一個試商就是7

第五步：第二步求得的的最高位數（1）乘以20再加上第一個試商(7)再乘以第一個試商(7)。
（1*20+7）*7
如果：（1*20+7）*7小於等於156，則7就是平方根的第二位數.
如果：（1*20+7）*7大於156，將第一個試商7減1，即用6再計算。
由於：（1*20+6）*6=156所以，6就是第平方根的第二位數。

例：求55225的平方根
第一步：將被開方數的整數個位起向左每隔兩位劃為一段，用逗號分開，分成幾段，表示所求平方根是幾位數。
例，第一步：將55225，分成三段：
5，52，25
表示平方根是三位數（XYZ）。

第二步：根據左邊第一段里的數，取該數的平方根的整數部分，作為所要求的平方根求最高位上的數。
例：左邊第一段數值是5，5的平方根是（2點幾）大於2和小於3，所以取整數部分是2作為所要求的平方根求最高位上的數，即所要求的平方根最高位X是2。

第三步：從第一段的數減去最高位上數的平方，在它們的差的右邊寫上第二段數組成第一個余數。
例：第一段數里的數是5.第二步計算出最高數是2
5減去2的平方=1
將1與第二段數（52）組成一個第一個余數：152
第四步：把第二步求得的最高位數（2）乘以20去試除第一個余數（152），取所得結果的整數部分作為第一個試商。
例： 152除以（2乘20）=3.8
第一個試商就是3

第五步：第二步求得的的最高位數（2）乘以20再加上第一個試商(3)再乘以第一個試商(3)。
（2*20+3）*3
如果：（2*20+3）*3小於等於152，則3就是平方根的第二位數.
如果：（2*20+3）*3大於152，將第一個試商3減1，即用2再計算。
由於：（2*20+3）*3小於152所以，3就是第平方根的第二位數。

第六步：用同樣的方法，繼續求平方根的其他各位上的數。用上一個余數減去上法中所求的積（即152－129＝23），與第三段數組成新的余數（即2325）。這時再求試商，要用前面所得到的平方根的前兩位數（即23）乘以20去試除新的余數（2325），所得的最大整數為新的試商。（2325/(23×20)的整數部分為5。）
7．對新試商的檢驗如前法。（右例中最後的余數為0，剛好開盡，則235為所求的平方根。）

㈡ 開方怎麼算

舉個例子，1156是四位數，所以它的算術平方根的整數部分是兩位數，且易觀察出其中的十位數是3。於是問題的關鍵在於：如何求出它的個位數a？為此，我們從a所滿足的關系式來入手。

根據兩數和的平方公式，可以得到

1156=(30+a)^2=30^2+2×30a+a^2，

所以1156－30^2=2×30a+a^2，

即256=(30×2+a)a，

也就是說， a是這樣一個正整數，它與30×2的和，再乘以它本身，等於256。

為便於求得a，可用下面的豎式來進行計算：

根號上面的數3是平方根的十位數。將 256試除以30×2，得4(如果未除盡則取整數位).由於4與30×2的和64，與4的積等於256，4就是所求的個位數a。豎式中的余數是0，表示開方正好開盡。於是得到 1156=34^2， 或√1156=34.上述求平方根的方法，稱為筆算開平方法，用這個方法可以求出任何正數的算術平方根，它的計算步驟如下：

開方的計算步驟

1．將被開方數的整數部分從個位起向左每隔兩位劃為一段，用「 ' 」這個符號分開（豎式中的11』56），分成幾段，表示所求平方根是幾位數；

2．根據左邊第一段里的數，求得平方根的最高位上的數（豎式中的3）；

3．從第一段的數減去最高位上數的平方，在它們的差的右邊寫上第二段數組成第一個余數（豎式中的256）；

4．把求得的最高位數乘以20去試除第一個余數，所得的最大整數作為試商（20×3除256，所得的最大整數是 4，所以試商是4）；

5．用商的最高位數的20倍加上這個試商再乘以試商，如果所得的積小於或等於余數，試商就是平方根的第二位數；如果所得的積大於余數，就把試商減小之後再試（豎式中（20×3+4）×4=256，說明試商4就是平方根的第二位數）；

6．用相同的方法，繼續求平方根的其餘各位上的數。

如碰到開不盡的情況，可根據所要求的精確度求出它的近似值。例如求其近似值（精確到0.01），可列出上面右邊的豎式，並根據這個豎式得到。

筆算開平方運算較復雜，在實際中直接應用較少，但用這個方法可求出一個數的平方根的具有任意精確度的近似值。

㈢ 求解模平方根的演算法(答得完整我會再追加分數)

※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※
#!/usr/bin/python
#coding=gbk
import math
def quick_algorithm(a,b,c): #y=a^b%c,a的b次冪余除c
a = a % c
ans = 1
#這里我們不需要考慮b<0，因為分數沒有取模運算
while b != 0: #費馬小定理
if b & 1:
ans = (ans * a) % c
b>>=1
a = (a * a) % c
return ans
def IsHaveMoSqrt(x,P):#是否有模平方根y*y=x mod p，已知x，p，判斷是否存在y
ret = quick_algorithm(x,(P-1)//2,P)
if ret==1:
return True
else:
return False
def GetMoSqrt(x,P):#求模平方根y*y=x mod p，已知x，p求y
if(IsHaveMoSqrt(x,P)==1):
t=0
s=P-1#P-1=(2^t)*s //s是奇數
while s%2==0:
s=s//2
t=t+1
if(t==1):
ret = quick_algorithm(x,(s+1)//2,P)
return (ret,P-ret)
elif (t>=2):
x_=quick_algorithm(x,P-2,P)
n=1
while(IsHaveMoSqrt(n,P)==1):
n=n+1
b=quick_algorithm(n,s,P)
print(b)
ret = quick_algorithm(x,(s+1)//2,P)#t-1
t_=0
while(t-1>0):
if(quick_algorithm(x_*ret*ret,2**(t-2),P)==1):
ret=ret
else:
ret=ret*(b**(2**t_))%P
t=t-1
t_=t_+1
return (ret,P-ret)
else:
return (-2,-2)
else:
return (-1,-1)
def Secp256k1GetYByX(x):#y^2=x^3+7 (mod p)根據x求y
a=(x*x*x+7)%
ret = GetMoSqrt(a,)
return ret
if __name__ == "__main__":
if True:
x=#私鑰為1,對應的公鑰x
ret = Secp256k1GetYByX(x)#secp256k1，根據x求y
print("x=%x" % (x))
print("y=%x" % (ret[0]))
print("y=%x" % (ret[1]))
print("")
x=1#x最小值
ret = Secp256k1GetYByX(x)#secp256k1，根據x求y
print("x=%x" % (x))
print("y=%x" % (ret[0]))
print("y=%x" % (ret[1]))
print("")
x=-3#x最大值
ret = Secp256k1GetYByX(x)#secp256k1，根據x求y
print("x=%x" % (x))
print("y=%x" % (ret[0]))
print("y=%x" % (ret[1]))
print("")
input()
※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※

㈣ 開方的簡便演算法

一、開平方的手動演算法
此方法是在高一學萬有引力和航天時，因需要大量開平方運算又不能用計算器，而被逼無奈研發的。
開平方的整個過程分為以下幾步：
（一）分位
分位，意即將一個較長的被開方數分成幾段。具體法則是：
1、分位的方向是從低位到高位；
2、每兩個數字為一段；
3、分到最後，最高位上可以不滿兩個數字，但不能沒有數字。
如：43046721分位後是43｜04｜67｜21
12321分位後是1｜23｜21
其中，每段中間的豎線在熟練了以後可不必寫。
分位以後，其實就能看出開方後的結果是幾位數了，如43046721分位後是四段，那麼開方結果就是四位數。
（二）開方
開方的運算過程其實與做除法很類似，都有一個相乘以後再相減的過程。
這里以43046721為例。
分位後是43｜04｜67｜21
運算時從高位到低位，先看前兩位43，由於62最接近43而不超過43，因而商（這里找不到合適的字眼，因而沿用除法時的字眼）6，然後做減法（如下圖）：
6
———————————————
4
3｜0
4｜6
7｜2
1
3
6
————————
7
0
4
這里一次落兩位，與除法不同。
下面的過程是整個演算法中最復雜的部分，稱為造數，之所以用這個詞是因為算出最後要減掉的數的過程較為麻煩。
首先，將已商數6乘以2：6×2=12
這里的12不是真正的12，實際上是120，個位上的0之所以空出來是為了寫下一個要商的數。
我們不妨假設下一個要商的數為A，我們下面要考慮的問題就是：從0-9中找一個A，使得：
12A×A最接近但不超過上面餘下的數704。注意，A在這里代表一個數位，若A=6，那麼12A的含義不是12×6，而是126。
以上過程與除法中的試商的過程很類似。
經驗證，125×5=625符合要求，因此下一個要商的數就是5。（如下圖）
往下依此類推：
65
×2
———
130
1306
×
6
————
7836
656
×2
———
1312
13121
×
1
————
13121
所以，43046721的算術平方根為6561
從開方的過程中我們可以看出，越到後面，計算量越大，因此，憑我們的計算量，再算一些開不盡的數時，如7的算術平方根，其精確程度是非常有限的。
以上就是開平方的一般方法，請列位指教。
二、開立方的手動演算法
此方法是昨天剛剛研發成功的，為了應付在由體積求分子半徑時產生的開立方的運算。
開立方的方法與開平方的方法很類似，但要復雜很多，如果不能熟練掌握，倒不如按大臉貓說的方法：湊！當然，熟練掌握以後，比湊的方法是快多了。
開立方的過程分以下幾步：
（一）分位
與開平方基本一致，只有一點：這次是每三位為一段
（二）開方
這里以41063625為例
第一個要商的數的確定與開平方是類似，只是變成了要找一個數的立方（如下圖）：
3
——————————————
4
1｜0
6
3｜6
2
5
2
7
————————
1
4
0
6
3
一次落三位！
下面的造數過程是最麻煩的，流程如下：
1、將已商數乘以3。3×3=9
2、將要商的數乘以3後，向後錯一位加在第1步算出的數上：
4×3=12
9
+
12
———
102
3、將第2步得出的數乘以已商數：102×3=306
4、將要商的數平方以後，向後錯一位加在第3步算出的數上
42=16
306
+
16
————
3076
5、將第4步中算出的數乘以要商的數，使它最接近又不超過餘下來的數：
3076×4=12304
12304就是我們要造的數，將這個數代回原來的開方式減掉就可以了。
3
4
——————————————
4
1｜0
6
3｜6
2
5
2
7
————————
1
4
0
6
3
1
2
3
0
4
—————————————
1
7
5
9
6
2
5
有人肯定會問，你怎麼知道要商的數就是4？的確，我一開始也不知道，確定要商的數的過程實際上就是類似開平方中的試商的過程，但這個過程比開平方是要繁瑣得多。
當做完造數過程的第1步以後，得出了9這個數，由於不知道應該商幾，所以，我們可以先假設商0，那麼依據第2步，90×3=270。270錯位加一個數，等於擴大了10倍還多，由於我們假設商0，由第3步，270變成了2700。這是我們就要看一看2700乘以一個什麼數最接近且不超過14063，這個數可能（這里說「可能」的原因從下文可以看到）就是我們要商的數。乍一看5非常合適，但你要考慮到我們在假設商0時少加了多少東西，所以商5可能就超了。經驗告訴我們，4和5都有可能，此時我們可先取5為要商的數，然後進行1-5各步，結果發現的數已經超過了14063，因此4就是我們要商的數。
註：這個試商的過程在熟練了以後是一眼就能看出來的。
下面的步驟可依此類推：
34
×3
————
102
+
15
（3×5）
————
1035
×
34
————
4140
3105
————
35190
+
25
52
————
351925
×
5
————
1759625
這里的5是怎麼商出來的不用我再說一遍了吧？
整個流程相當繁瑣，丟其中任何一步都可能導致前功盡棄，因此必須要求計算準確。熟練了以後，速度是可以保證的。我曾經把手動開方法和湊數法比較過，前者比後者至少快一倍。
另外，值得注意的是：如果已知結果是整數，那麼結果最後一位的確定可不必用以上方式，直接根據立方數末位的特異性就可確定，但前提是對1-9的立方表非常熟悉。1-5的立方表同志們應該都很熟悉，以下幾個是不常用的：
63=216
73=343
83=512
93=729
結語：這兩種方法可用來准確地進行開平方及開立方的運算，只要有耐心，想算幾位就算幾位。但開立方的過程實在是很復雜，很可能還存在優化方案，但由於時間緊迫，我沒有再考慮其他的方法。同志們誰要是有興趣，可以使這優化這兩個演算法，我的方法僅供參考。