第一题

手动解以下同余方程，求出x，写过程

(a)

$25x \equiv 15 \pmod{9}$

$易知25在模29下的逆元25^{-1}$

已知egcd(25,29) = 1

$由 Bézout 定理 ， 存在整数 r 和 s 使得 ：gcd(25,29) =25r+29s =1(a 和 b 为非零整数 )$

解得r=7,s=−6

同时模29,25∗7≡1(mod 29)

$所以，25^{−1}=7$

得，$x \equiv 18 * \pmod{29}$

(b)

$5x \equiv 2 \pmod{26}$

$先算5在模26下的逆元5^{-1}$

使用egcd算法 ， 即 egcd(5,26) = 1

$由 Bézout 定理 ， 存在整数 r 和 s 使得 ：gcd(5,26) =5r+26s =1(a 和 b 为非零整数 )$

得出，r=21，s=−4

$同时模26,5∗(21) ≡1(mod 26),所以5^{-1}=21$

$所以,x \equiv 16 \pmod{26}$

(c)

$6x \equiv 15 \pmod{21}$

$易知同余方程等价于2x \equiv 5 \pmod{7}$

$先算出 2 在模 7 下的逆元 2^{−1}$

使用 egcd 算法 ， 即 egcd(2,7) = 1

$由 Bézout 定理 ， 存在整数 r 和 s 使得 ：gcd(2,7) =2r+7s =1(a 和 b 为非零整数 )$

r=4，s=−1

对等式两边同时模 7

$2∗(4) ≡1(mod 7),所以2^{-1} = 4$

$所以,x \equiv 6 \pmod{7}$

第二题

证明

1.

$要证53^{103} + 103^{53}被39整除$

因为39=3*13，可以分两步走

先证明被3整除：

$因为53 \equiv -1 \pmod{3}$

$由模乘法,53^{103} \equiv -1 \pmod{3}$

$同理，103^{53} \equiv 1 \pmod{3}$

$由模加法，53^{103} + 103^{53} \equiv 0 \pmod{3}$

得证

再证明被13整除：

$因为53 \equiv 1 \pmod{13}$

$由模乘法,53^{103} \equiv 1 \pmod{33}$

$同理，103^{53} \equiv -1 \pmod{13}$

$由模加法，53^{103} + 103^{53} \equiv 0 \pmod{13}$

$所以得证，53^{103} + 103^{53},既被 3 整除 ， 也被 13 整除$

所以得证

2.

$要证明111^{333} + 333^{111}被7整除：$

$因为111 \equiv -1 \pmod{7}$

$由模乘法，111^{333} \equiv -1 \pmod{7}$

$易知，333^{111} \equiv 4^{111} \pmod{7}$

$所以333^{111} \equiv 4^{111} \equiv 64^{37} \equiv 1 \pmod{7}$

$由模加法，111^{333} + 333^{111} \equiv 0 \pmod{7}$

所以得证明

第三题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import math
N = 14905562257842714057932724129575002825405393502650869767115942606408600343380327866258982402447992564988466588305174271674657844352454543958847568190372446723549627752274442789184236490768272313187410077124234699854724907039770193680822495470532218905083459730998003622926152590597710213127952141056029516116785229504645179830037937222022291571738973603920664929150436463632305664687903244972880062028301085749434688159905768052041207513149370212313943117665914802379158613359049957688563885391972151218676545972118494969247440489763431359679770422939441710783575668679693678435669541781490217731619224470152467768073
e1 = 12886657667389660800780796462970504910193928992888518978200029826975978624718627799215564700096007849924866627154987365059524315097631111242449314835868137
e2 = 12110586673991788415780355139635579057920926864887110308343229256046868242179445444897790171351302575188607117081580121488253540215781625598048021161675697
c1 = 14010729418703228234352465883041270611113735889838753433295478495763409056136734155612156934673988344882629541204985909650433819205298939877837314145082403528055884752079219150739849992921393509593620449489882380176216648401057401569934043087087362272303101549800941212057354903559653373299153430753882035233354304783275982332995766778499425529570008008029401325668301144188970480975565215953953985078281395545902102245755862663621187438677596628109967066418993851632543137353041712721919291521767262678140115188735994447949166616101182806820741928292882642234238450207472914232596747755261325098225968268926580993051
c2 = 14386997138637978860748278986945098648507142864584111124202580365103793165811666987664851210230009375267398957979494066880296418013345006977654742303441030008490816239306394492168516278328851513359596253775965916326353050138738183351643338294802012193721879700283088378587949921991198231956871429805847767716137817313612304833733918657887480468724409753522369325138502059408241232155633806496752350562284794715321835226991147547651155287812485862794935695241612676255374480132722940682140395725089329445356434489384831036205387293760789976615210310436732813848937666608611803196199865435145094486231635966885932646519
up5_e1_e2 = pow(5, e1*e2, N)
c1_e2 = pow(c1, e2, N)
up2_e1_e2 = pow(2, e1*e2, N)
c2_e1 = pow(c2, e1, N)
up3_e1_e2 = pow(3, e1*e2, N)
up7_e1_e2 = pow(7, e1*e2, N)
val1 = (up5_e1_e2 * c1_e2 - up2_e1_e2 * c2_e1)%N
q = math.gcd(val1, N)
val2 = (up3_e1_e2*c2_e1 - up7_e1_e2*c1_e2)%N
p = math.gcd(val2, N)
print(f'crypto{{{p}, {q}}}')

flag:

1
crypto{112274000169258486390262064441991200608556376127408952701514962644340921899196091557519382763356534106376906489445103255177593594898966250176773605432765983897105047795619470659157057093771407309168345670541418772427807148039207489900810013783673957984006269120652134007689272484517805398390277308001719431273, 132760587806365301971479157072031448380135765794466787456948786731168095877956875295282661565488242190731593282663694728914945967253173047324353981530949360031535707374701705328450856944598803228299967009004598984671293494375599408764139743217465012770376728876547958852025425539298410751132782632817947101601}

第四题

写一个Python程序

1
输入整数a和m，a<m，且gcd(a,m) =1（如果不等于，就报错），输出a' 使得a'是mod m下a 的乘法逆元
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def extended_gcd(a, m):
    # 扩展欧几里得算法，返回 gcd(a, m) 以及 x, y 满足 ax + my = gcd(a, m)
    if m == 0:
        return a, 1, 0
    gcd, x1, y1 = extended_gcd(m, a % m)
    x = y1
    y = x1 - (a // m) * y1
    return gcd, x, y

def mod_inverse(a, m):
    # 检查 gcd(a, m) 是否为 1
    gcd, x, _ = extended_gcd(a, m)
    if gcd != 1:
        raise ValueError(f'gcd({a}, {m}) != 1, 无法求逆元')
    
    # 将 x 对 m 取模，使 x 在 [0, m-1] 范围内
    return x % m

# 输入整数 a 和 m
a = int(input("请输入整数 a: "))
m = int(input("请输入整数 m: "))

if a >= m:
    print(f"错误：a ({a}) 必须小于 m ({m})")
else:
    try:
        inverse = mod_inverse(a, m)
        print(f"{a} 在 mod {m} 下的乘法逆元是: {inverse}")
    except ValueError as e:
        print(e)