Tonelli-Shanks算法_python

2021-09-08 17:57:56

Tonelli-Shanks算法_python

该算法应用于求二次剩余

也就是形如 x 2 ≡ n ( m o d p ) x^2\equiv n\pmod p x2≡n(modp)的同余式，已知 n , p n,p n,p求 x x x

判断二次（非）剩余

为了执行这个算法，需要知道如何判断二次（非）剩余

所谓二次（非）剩余也就是上面提到的同余式有无解的另一个说法

而判断二次剩余我们可以使用欧拉准则

n p − 1 2 ≡ 1 ( m o d p ) n^{\frac{p-1}{2}}\equiv 1\pmod p n2p−1≡1(modp)；此情况为有解

n p − 1 2 ≡ − 1 ( m o d p ) n^{\frac{p-1}{2}}\equiv -1\pmod p n2p−1≡−1(modp)；此情况为无解

python表示为

if pow(n,(p-1)//2,p) == 1:
	print("二次剩余")
if pow(n,(p-1)//2,p) == p - 1:
	print("二次非剩余")

这里二次非剩余的判断条件不是 − 1 -1 −1而是 p − 1 p-1 p−1，是因为在pow()函数计算的结果不会为负数，那么在模 p p p的世界中 p − 1 p-1 p−1等价于 − 1 -1 −1

A l g o r i t h m p r o c e s s Algorithm~process Algorithm process

同余式 x 2 ≡ n ( m o d p ) x^2\equiv n\pmod p x2≡n(modp)；其中 p p p为奇素数

首先确保 n n n是 p p p的二次剩余，有个性质可以简单地判断，就是 n n n是否为平方数
如果 p p p满足 p ≡ 3 ( m o d 4 ) p\equiv 3\pmod 4 p≡3(mod4)，那么直接返回算法结果 r = n p + 1 4 ( m o d p ) r=n^{\frac{p+1}{4}}\pmod p r=n4p+1(modp)
令 q = p − 1 q=p-1 q=p−1，然后不断地让 p p p除 2 2 2，直到 p p p成为一个奇数，整除的次数记作 s s s
选择一个整数 z z z使得 z z z是 p p p的二次非剩余，并计算 c ≡ z q ( m o d p ) c\equiv z^q\pmod p c≡zq(modp)
r ≡ n q + 1 2 ( m o d p ) r\equiv n^{\frac{q+1}{2}}\pmod p r≡n2q+1(modp)， t ≡ n q ( m o d p ) t\equiv n^q\pmod p t≡nq(modp)， m = s m=s m=s
进行外层循环

若 t t t满足 t ≡ 1 ( m o d p ) t\equiv 1\pmod p t≡1(modp)，返回算法结果 r r r

否则，进行内层循环

令中间值 t e m p ≡ t 2 i ( m o d p ) temp\equiv t^{2^{i}}\pmod p temp≡t2i(modp)，当 t e m p temp temp满足 t e m p ≡ 1 ( m o d p ) temp\equiv 1\pmod p temp≡1(modp)时进行以下计算

b ≡ c 2 m − i − 1 ( m o d p ) b\equiv c^{2^{m-i-1}}\pmod p b≡c2m−i−1(modp)；注意，这里的 i i i也就是 t e m p ≡ t 2 i ( m o d p ) temp\equiv t^{2^i}\pmod p temp≡t2i(modp)的 i i i值

r ≡ r ∗ b ( m o d p ) r\equiv r*b\pmod p r≡r∗b(modp)

c ≡ b ∗ b ( m o d p ) c \equiv b*b\pmod p c≡b∗b(modp)

t ≡ t ∗ c ( m o d p ) t\equiv t*c\pmod p t≡t∗c(modp)；这里重新赋值了 t t t，也就是外层循环的 t t t，若满足外层循环的条件则返回算法结果，若不满足则继续内层循环

m = i m=i m=i

到这里算法就结束了，返回结果 r r r即是二次剩余的解

P y t h o n a p p l i c a t i o n Python~application Python application

def Legendre(n,p): # 这里用勒让德符号来表示判断二次（非）剩余的过程
    return pow(n,(p - 1) // 2,p)
def Tonelli_Shanks(n,p):
    assert Legendre(n,p) == 1
    if p % 4 == 3:
        return pow(n,(p + 1) // 4,p)
    q = p - 1
    s = 0
    while q % 2 == 0:
        q = q // 2
        s += 1
    for z in range(2,p):
        if Legendre(z,p) == p - 1:
            c = pow(z,q,p)
            break
    r = pow(n,(q + 1) // 2,p)
    t = pow(n,q,p)
    m = s
    if t % p == 1:
        return r
    else:
        i = 0
        while t % p != 1: # 外层循环的判断条件
            temp = pow(t,2**(i+1),p) # 这里写作i+1是为了确保之后内层循环用到i值是与这里的i+1的值是相等的
            i += 1
            if temp % p == 1: # 内层循环的判断条件
                b = pow(c,2**(m - i - 1),p)
                r = r * b % p
                c = b * b % p
                t = t * c % p
                m = i
                i = 0 # 注意每次内层循环结束后i值要更新为0
        return r

C a l l m o d u l e Call~module Call module

sympy模块内有封装好了的函数可以计算二次剩余

nthroot_mod()用于求解于 n i n d e x ≡ x ( m o d p ) n^{index}\equiv x\pmod p nindex≡x(modp)的同余式

from sympy.ntheory.residue_ntheory import nthroot_mod
x=nthroot_mod(n,index,p)

E x a m p l e Example Example

V&N2020的一道Crypto：Easy RSA

题目算到最后已知 m 2 ≡ c ( m o d r ) m^2\equiv c\pmod r m2≡c(modr)，已知 c , r c,r c,r求 m m m

直接代入定义好了的Tonelli_Shanks()函数即可

代码实现

from Crypto.Util.number import *

c = 8081092455112516397361105816900490085355315574087538340788309885334106796325593823678787887569920404814986643819898763828872716522338864714182757065213683
r = 10269028767754306217563721664976261924407940883784193817786660413744866184645984238866463711873380072803747092361041245422348883639933712733051005791543841
def Legendre(n,p):
    return pow(n,(p - 1) // 2,p)
def Tonelli_Shanks(n,p):
    assert Legendre(n,p) == 1
    if p % 4 == 3:
        return pow(n,(p + 1) // 4,p)
    q = p - 1
    s = 0
    while q % 2 == 0:
        q = q // 2
        s += 1
    for z in range(2,p):
        if Legendre(z,p) == p - 1:
            c = pow(z,q,p)
            break
    r = pow(n,(q + 1) // 2,p)
    t = pow(n,q,p)
    m = s
    if t % p == 1:
        return r
    else:
        i = 0
        while t % p != 1:
            temp = pow(t,2**(i+1),p)
            i += 1
            if temp % p == 1:
                b = pow(c,2**(m - i - 1),p)
                r = r * b % p
                c = b * b % p
                t = t * c % p
                m = i
                i = 0
        return r
    
result = Tonelli_Shanks(c,r)
print(result)
print(long_to_bytes(result))

p e f e r e n c e peference peference

Tonelli-Shanks algorithm - Rosetta Code

(11条消息) BUUCTF Crypto V&N2020 公开赛]easy_RSA wp_hsqGOD’s blog-CSDN博客

码农公寓