数论笔记

垃圾Dawn_whisper的数论学习史

同余

费马小定理

设 $a$ 为整数， $p$ 为质数，则 $a^{p-1}\equiv 1\ (mod\ p)$
可写为 $a^p\equiv a\ (mod\ n)$

可用于求逆元 $a*a^{p-2}\equiv 1\ (mod\ p)$

gcd相关

$gcd(a,b)=gcd(b,a)$
$gcd(a,b)=gcd(a-b,b)\ (a\geq b)$
$gcd(a,b)=gcd(a\ % \ b,b)$
$gcd(a,b,c)=gcd(gcd(a,b),c)$
$gcd(a,0)=a$
$lcm(a,b)=\frac{a\times b}{gcd(a,b)}$

拓展欧几里得

考虑方程 $a\cdot x+b\cdot y=c$ ，a、b、c都是已知正整数

方程有解的充要条件为 $gcd(a,b)|c$

简化问题：考虑方程 $a\cdot x+b\cdot y=gcd(a,b)$ ，它的解为

$$
\begin{cases}
x=x_0+\frac{b}{d}t\\
y=y_0-\frac{a}{d}t
\end{cases}
\ \ \ \ \ \ 其中x_0,y_0是方程a\cdot x+b\cdot y=gcd(a,b)的一组解
$$

中国剩余定理

若
$$
\begin{cases}
x\equiv a_1\ (mod\ m_1) \\
x\equiv a_2\ (mod\ m_2) \\
\cdots \\
x\equiv a_n\ (mod\ m_n)
\end{cases}
$$

则假设上述方程组中 $m_1,m_2,\cdots,m_n$ 两两互质，则方程组的通解为$x=k\prod_{i=1}^n m_i+\sum_{j=1}^n {a_jM_j{M_j}^{-1}}$ ，其中 $M_j=\prod_{j=1\ and\ j\neq i}^n m_j$

from Crypto.Util.number import *
from functools import reduce
from gmpy2 import *
m = [0xb7e3b7c2d1f3182b,0x9f8f50eabf43f511,0xa00f2a37b609777d,0xb30cac6cea2e5c9b,0xc9a99dc0cd599bdf,0xc5eb72a709c3e3d5,0x9ef6c54a8b186819]
a = [0x573d55b36840b74e,0x57a5dba93b170c60,0x7dd225f7f760f993,0x13db30db9029eefa,0x7bce9c0e1fa360d3,0x8f318de4462c31f6,0x31508ba78eac022b]
Num = len(m)
M=reduce(lambda x,y: x*y, m)
Mi=[M//i for i in m]
t=[inverse(Mi[i], m[i]) for i in range(Num)]
x=0
for i in range(Num):
      x+=a[i]*t[i]*Mi[i]
    #   print(a[i]*t[i]*Mi[i])
    #   print(x)
print(long_to_bytes(x%M))

如果模数间不互质，考虑这两个模数不互质的方程，那么有 $x=a_1+m_1x_1=a_2+m_2x_2$ ，我们用拓展欧几里得可以算出 $x_1$ 的最小正整数解，带回至 $a_1+m_1x_1$ 得到 $x$ 的一个特解 $x’$ ，所以 $x=x’+lcm(m_1,m_2)\times k$ ，也就是说，这两个方程被合并成了 $x\equiv x’\ (mod\ lcm(m_1,m_2))$

import hashlib
from functools import reduce
from gmpy2 import gcd
from Crypto.Util.number import *
m = [284461942441737992421992210219060544764, 218436209063777179204189567410606431578, 288673438109933649911276214358963643204, 239232622368515797881077917549177081575, 206264514127207567149705234795160750411, 338915547568169045185589241329271490503, 246545359356590592172327146579550739141, 219686182542160835171493232381209438048]
a = [273520784183505348818648859874365852523, 128223029008039086716133583343107528289, 5111091025406771271167772696866083419, 33462335595116820423587878784664448439, 145377705960376589843356778052388633917, 128158421725856807614557926615949143594, 230664008267846531848877293149791626711, 94549019966480959688919233343793910003]
Num = len(m)
gbs=reduce(lambda x,y: x*y//gcd(x,y), m)#最小公倍数
p = reduce(lambda x,y: x*y, m)
def egcd(a, b):
      if a == 0:
            return (b, 0, 1)
      else:
            g, y, x = egcd(b % a, a)
      return (g, x - (b // a) * y, y)
def china(num):
      m1,a1,lcm=m[0],a[0],m[0]
      for i in range(1,num):
            m2=m[i]
            a2=a[i]
            c=a2-a1
            g,k1,k2=egcd(m1,m2)
            lcm=lcm*m[i]//gcd(lcm,m[i])
            if c%g :
                  print('No Answer!')
                  return 0
            x0=c//g*k1
            t=m2//g
            x0=(x0%t+t)%t
            a1+=m1*x0
            m1=m2//g*m1
      return a1
ans=china(Num)
i=0
x=ans+i*gbs
while x<p:
      flag = "flag{" + hashlib.sha256(str(x).encode()).hexdigest() + "}"
      if ("4b93deeb" in flag):print(flag)
      i+=1
      x=ans+i*gbs