####二次残差

Quadratic Residues

a^2^ $\equiv$ x mod p

即,a^2^>p时, (a^2^-x)是p的倍数 (当a^2^<p时, x = a^2^)

$\therefore$x= a^2^-mp (a^2^ > p)

例如：

1
2
3
4
5
6
7
8
9
10
p=7
a += 1 
1^2 = 1 (mod 7) # 1<7, x=a^2=1
2^2 = 4 (mod 7) # 4<7, x=a^2=4
3^2 = 2 (mod 7) # 9>7, x=a^2-p*1=2
4^2 = 2 (mod 7) # 16>7, x=a^2-p*2=2
5^2 = 4 (mod 7) # 25>7, x=a^2-p*3=4
6^2 = 1 (mod 7) # 36>7, x=a^2-p*5=1
# 1,2,4 are Quadratic Residue of 7
    # 3,5,6 are Quadratic Non-Residue of 7

Legendre Symbol

Euler 判别准则

对于奇素数p

a^(p-1)//2^ $\equiv$ (a/p) $\equiv$ 1 mod p(此时有解) or -1 mod q (此时无解)

当已知条件p= 3 mod 4 时，可求解特殊化：

(a^(p+1)/4^)^2^=a^(p+1)/2^ mod p

(a^(p+1)/4^)^2^=x^(p-1)^x^2^ mod p(由费马小定理可知)

所以(a^(p+1)/4^)^2^=x^2^ mod p

所以a^(p+1)/4^mod p是一个解

####中国剩余定理

一般地，一次同余式组可以表示为：

​ x $\equiv$ b1 (modm1)

​ x $\equiv$ b2 (mod m2)

​ ……

​ x $\equiv$ bk (mod mk)

设 m1 , m2 , …. , mk两两互素，则上面的同余式组有唯一的解：

x $\equiv$ M1^-1^M1b1+M2^-1^M2b2+…..+Mk^-1^Mkbk(mod m)

m=m1 m2 …mk , Mi=m/mi ，Mi^-1^=(也就是Mi与mi的逆元)

例子：

x $\equiv$ 2 (mod 3)

x $\equiv$ 3(mod 5)

x$\equiv$ 2(mod 7)

m1=3,m2=5, m3=7，m=m1m2m3= 3 $\times$ 5 $\times$7

M1=m/m1,M2=m/m2,M3=m/m3

M1^-1^=M1(mod m1)

M2^-1^=M2(mod m2)

M3^-1^=M3(mod m3)

所以x$\equiv$M1^1^M1b1+M2^1^M2b2+M3^1^M3b3

参考文献：SageMath简明教程 | tl2cents blog

基本数论函数

  • 求逆：e模n的逆�模�的逆

    定义在Zmod(N)上的元素e，直接e^-1或者1/e

    否则直接使用inverse_mod(e,n)函数获得e模n的逆

  • 最大公因数：（a,b)的最大公因数

    gcd(a,b)

  • 最大公倍数：(a,b)的最大公倍数

    lcm(a,b)

  • 模幂：e^m^ mod n

    定义在Zmod(N)上的元素e，直接e^x

    否则直接使用pow(e,x,n)

  • 素数判断

    1
    2
    3
    sage: x=123721984710347123123
    sage: x.is_prime()
    False

  • 阶乘：

    factorial(x)

  • 欧拉函数：

    1
    2
    euler_phi(n) 							
    #  求n的欧拉函数 phi = n*prod([1 - 1/p for p in prime divisors(n)])

  • 中国剩余定理求解

    x≡m1 mod n1

    x≡m2 mod n2

    解为：

    1
    2
    3
    crt([m1,m2],[n1,n2])
    sage: crt([1,2],[3,5])
    7

  • 扩展欧几里得算法：

    d=gcd(a,b)=u∗a+v∗b

    1
    d,u,v=xgcd(a,b)

  • 素数分解

    1
    2
    3
    factor(1024) -> 2^10
    prime_divisors(1024) -> [2]
    divisors() #所有因子

  • 开根(有限域开根)

    整数域开根

    x^m^ = y 已知m，y求x

    1
    2
    3
    sage: y=87^8
    sage: y.nth_root(8)
    87

    有限域开根：

    x^m^ ≡ y mod N 已知m，y，N求x

    1
    2
    3
    4
    5
    6
    7
    sage: y=pow(78,888,65537)
    # 此时已经定义在有限域Zmod(65537)上
    sage: y.nth_root(888)
    65459
    sage: x=y.nth_root(888)
    sage: x+78
    0

    注意：开根有多解，nth_root只会返回一个解，如果需要得到所有解，可以加一个参数：

    1
    sage: x=y.nth_root(888,all=True)