逆元
注：由于hexo默认渲染引擎是marked但是marked不支持mathjax,所以这些LaTex公式在网页上表示不出来，可以复制LaTex代码在Typora上进行显示，后续我在进行设置。
a*x $\equiv$ 1(mod b)
x = gmpy2.invert(a,b)
费马小定理
第一种形式：若p是素数，a是正整数且不能被p整除，则：
a**(p-1) $\equiv$ 1 mod p
a**(p-1) % p = 1 % p
第二种形式若p是素数且a是任意的整数。则；
a^p $\equiv$ a mod p
a^p % p = a % p
威尔逊定理
定义
当且仅当p是素数时
（p-1）！ $\equiv$ -1(mod p)
例题
题目
import sympy
import random
def myGetPrime():
A= getPrime(513)
print(A)
B=A-random.randint(1e3,1e5)
print(B)
return sympy.nextPrime((B!)%A)
p=myGetPrime()
A1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
B1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596
q=myGetPrime()
A2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
B2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026
r=myGetPrime()
n=p*q*r
n=85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
c=pow(flag,e,n)
e=0x1001
c=75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428
so,what is the flag?python脚本
最终是求出B! %A 想起威尔逊定理
补全为
（A-1)(A-2)…. (B!) $\equiv$ -1 (mod A)
(A-2)*(A-3)……(B!) $\equiv$ 1 (mod A)
(A-2)*(A-3)……(B!) %A = 1
(((((A-2)%A)(A-3))%A……)(B!))%A =1
(((((A-2)%A)(A-3))%A……)(B!) $\equiv$ 1 （mod A) //利用逆元求B！
import gmpy2
import libnum
A1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
B1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596
A2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
B2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026
n=85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
e=0x1001
c=75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428
def encrypt(A,B):
tmp = 1
for i in range(B + 1, A - 1):
tmp *= i
tmp %= A
tmp_inv = gmpy2.invert(tmp, A)
result = gmpy2.next_prime(tmp_inv%A)
return result
p = encrypt(A1,B1)
q = encrypt(A2,B2)
r = n//p//q
phi = (p-1)*(q-1)*(r-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(libnum.n2s(int(m)))
