CryptoHack教程的第二章：模运算。看来这一章整章都是围着数学转了。

数学公式好像要刷新一下网页才能看到，不知道怎么回事（

Greatest Common Divisor

The Greatest Common Divisor (GCD), sometimes known as the highest common factor, is the largest number which divides two positive integers (a,b).

For a = 12, b = 8 we can calculate the divisors of a: {1,2,3,4,6,12} and the divisors of b: {1,2,4,8}. Comparing these two, we see that gcd(a,b) = 4.

Now imagine we take a = 11, b = 17. Both a and b are prime numbers. As a prime number has only itself and 1 as divisors, gcd(a,b) = 1.

We say that for any two integers a,b, if gcd(a,b) = 1 then a and b are coprime integers.

If a and b are prime, they are also coprime. If a is prime and b < a then a and b are coprime.

There are many tools to calculate the GCD of two integers, but for this task we recommend looking up Euclid’s Algorithm.

Try coding it up; it’s only a couple of lines. Use a = 12, b = 8 to test it.

Now calculate gcd(a,b) for a = 66528, b = 52920 and enter it below.

第一节GCD，我们熟知的最大公因数。具体就不再赘述了，我们可以用欧几里得算法手算或者写代码

def gcd(a, b):
    if b > a:
        return gcd(b, a)
    if a % b == 0:
        return b
    return gcd(b, a % b)

计算print(gcd(66528,52920))即可得到答案1512.

Extended GCD

Let a and b be positive integers.

The extended Euclidean algorithm is an efficient way to find integers u,v such that

a * u + b * v = gcd(a,b)

Using the two primes p = 26513, q = 32321, find the integers u,v such that

p * u + q * v = gcd(p,q)

Enter whichever of u and v is the lower number as the flag.

第二节讲的是扩展的欧几里得算法。

不管是手算还是写代码都有点麻烦，我的建议是直接用gmpy2库里的gcdext()来计算。

这里放一个别的大佬写的

def egcd(a, b):
    x, y, u, v = 0, 1, 1, 0
    while a != 0:
        q, r = b//a, b % a
        m, n = x-u*q, y-v*q
        b, a, x, y, u, v = a, r, u, v, m, n
    gcd = b
    return gcd, x, y
print(egcd(26513,32321))

结果是10245和-8404，输入-8404即可通过。

Modular Arithmetic 1

Imagine you lean over and look at a cryptographer’s notebook. You see some notes in the margin:

4 + 9 = 1
5 - 7 = 10
2 + 3 = 5

At first you might think they’ve gone mad. Maybe this is why there are so many data leaks nowadays you’d think, but this is nothing more than modular arithmetic modulo 12 (albeit with some sloppy notation).

You may not have been calling it modular arithmetic, but you’ve been doing these kinds of calculations since you learnt to tell the time (look again at those equations and think about adding hours).

Formally, “calculating time” is described by the theory of congruences. We say that two integers are congruent modulo m if a ≡ b mod m.

Another way of saying this, is that when we divide the integer a by m, the remainder is b. This tells you that if m divides a (this can be written as m | a) then a ≡ 0 mod m.

Calculate the following integers:

11 ≡ x mod 6
8146798528947 ≡ y mod 17

The solution is the smaller of the two integers.

这一节开始引入了模运算的概念，很容易得到x=5,y=4

答案是4.

Modular Arithmetic 2

We’ll pick up from the last challenge and imagine we’ve picked a modulus p, and we will restrict ourselves to the case when p is prime.

The integers modulo p define a field, denoted Fp.

If the modulus is not prime, the set of integers modulo n define a ring.

A finite field Fp is the set of integers {0,1,...,p-1}, and under both addition and multiplication there is an inverse element b for every element a in the set, such that a + b = 0 and a * b = 1.

Note that the identity element for addition and multiplication is different! This is because the identity when acted with the operator should do nothing: a + 0 = a and a * 1 = a.

Lets say we pick p = 17. Calculate 3^17^ mod 17. Now do the same but with 5^17^ mod 17.

What would you expect to get for 7^16^ mod 17? Try calculating that.

This interesting fact is known as Fermat’s little theorem. We’ll be needing this (and its generalisations) when we look at RSA cryptography.

Now take the prime p = 65537. Calculate 273246787654^65536^ mod 65537.

Did you need a calculator?

这里讲了很多，实际上就是介绍了费马小定理：

如果是素数，并且不是的倍数，则

$$a^{p-1}\equiv1 \mod{p}$$

所以答案很显然就是1.

Modular Inverting

As we’ve seen, we can work within a finite field Fp, adding and multiplying elements, and always obtain another element of the field.

For all elements g in the field, there exists a unique integer d such that g * d ≡ 1 mod p.

This is the multiplicative inverse of g.

Example: 7 * 8 = 56 ≡ 1 mod 11

What is the inverse element: 3 * d ≡ 1 mod 13?

Think about the little theorem we just worked with. How does this help you find the inverse of an element?

这一节讲的是逆元，题目中提示我们用上一节中的定理计算。

$$\begin{align} 3^{12}&\equiv1 \mod{13}\\ 3*d&\equiv1 \mod{13} \end{align}$$

所以

$$\begin{align} 3*d&\equiv3^{12}\mod{13}\\ d&\equiv3^{11}\mod{13} \end{align}$$

3^11^模13与9同余，答案为9.

Quadratic Residues

We’ve looked at multiplication and division in modular arithmetic, but what does it mean to take the square root modulo an integer?

For the following discussion, let’s work modulo p = 29. We can take the integer a = 11 and calculate a2 = 5 mod 29.

As a = 11, a2 = 5, we say the square root of 5 is 11.

This feels good, but now let’s think about the square root of 18. From the above, we know we need to find some integer a such that a2 = 18

Your first idea might be to start with a = 1 and loop to a = p-1. In this discussion p isn’t too large and we can quickly look.

Have a go, try coding this and see what you find. If you’ve coded it right, you’ll find that for all a ∈ Fp* you never find an a such that a2 = 18.

What we are seeing, is that for the elements of F*p, not every element has a square root. In fact, what we find is that for roughly one half of the elements of Fp*, there is no square root.

We say that an integer x is a Quadratic Residue if there exists an a such that a2 = x mod p. If there is no such solution, then the integer is a Quadratic Non-Residue.

In other words, x is a quadratic residue when it is possible to take the square root of x modulo an integer p.

In the below list there are two non-quadratic residues and one quadratic residue.

Find the quadratic residue and then calculate its square root. Of the two possible roots, submit the smaller one as the flag.

If a2 = x then (-a)2 = x. So if x is a quadratic residue in some finite field, then there are always two solutions for a.

这一节讲的是二次剩余与二次非剩余。

这里用程序遍历每个数依次计算即可，算得6是模29的二次剩余，6模29最小的根为8.

Legendre Symbol

In Quadratic Residues we learnt what it means to take the square root modulo an integer. We also saw that taking a root isn’t always possible.

In the previous case when p = 29, even the simplest method of calculating the square root was fast enough, but as p gets larger, this method becomes wildly unreasonable.

Lucky for us, we have a way to check whether an integer is a quadratic residue with a single calculation thanks to Legendre. In the following, we will assume we are working modulo a prime p.

Before looking at Legendre’s symbol, let’s take a brief detour to see an interesting property of quadratic (non-)residues.

Quadratic Residue Quadratic Residue = Quadratic Residue
Quadratic Residue Quadratic Non-residue = Quadratic Non-residue
Quadratic Non-residue * Quadratic Non-residue = Quadratic Residue

So what’s the trick? The Legendre Symbol gives an efficient way to determine whether an integer is a quadratic residue modulo an odd prime p.

Legendre’s Symbol: (a / p) ≡ a(p-1)/2 mod p obeys:

(a / p) = 1 if a is a quadratic residue and a ≢ 0 mod p
(a / p) = -1 if a is a quadratic non-residue mod p
(a / p) = 0 if a ≡ 0 mod p

Which means given any integer a, calculating pow(a,(p-1)//2,p) is enough to determine if a is a quadratic residue.

Now for the flag. Given the following 1024 bit prime and 10 integers, find the quadratic residue and then calculate its square root; the square root is your flag. Of the two possible roots, submit the larger one as your answer.

Challenge files:

- output.txt

这一节讲了勒让德符号判断一个数是否为模p二次剩余，在gmpy2库中就有一个legendre()可以直接使用。

先计算一下哪个是平方剩余

from gmpy2 import legendre
ints = [25081841204695904475894082974192007718642931811040324543182130088804239047149283334700530600468528298920930150221871666297194395061462592781551275161695411167049544771049769000895119729307495913024360169904315078028798025169985966732789207320203861858234048872508633514498384390497048416012928086480326832803, 45471765180330439060504647480621449634904192839383897212809808339619841633826534856109999027962620381874878086991125854247108359699799913776917227058286090426484548349388138935504299609200377899052716663351188664096302672712078508601311725863678223874157861163196340391008634419348573975841578359355931590555, 17364140182001694956465593533200623738590196990236340894554145562517924989208719245429557645254953527658049246737589538280332010533027062477684237933221198639948938784244510469138826808187365678322547992099715229218615475923754896960363138890331502811292427146595752813297603265829581292183917027983351121325, 14388109104985808487337749876058284426747816961971581447380608277949200244660381570568531129775053684256071819837294436069133592772543582735985855506250660938574234958754211349215293281645205354069970790155237033436065434572020652955666855773232074749487007626050323967496732359278657193580493324467258802863, 4379499308310772821004090447650785095356643590411706358119239166662089428685562719233435615196994728767593223519226235062647670077854687031681041462632566890129595506430188602238753450337691441293042716909901692570971955078924699306873191983953501093343423248482960643055943413031768521782634679536276233318, 85256449776780591202928235662805033201684571648990042997557084658000067050672130152734911919581661523957075992761662315262685030115255938352540032297113615687815976039390537716707854569980516690246592112936796917504034711418465442893323439490171095447109457355598873230115172636184525449905022174536414781771, 50576597458517451578431293746926099486388286246142012476814190030935689430726042810458344828563913001012415702876199708216875020997112089693759638454900092580746638631062117961876611545851157613835724635005253792316142379239047654392970415343694657580353333217547079551304961116837545648785312490665576832987, 96868738830341112368094632337476840272563704408573054404213766500407517251810212494515862176356916912627172280446141202661640191237336568731069327906100896178776245311689857997012187599140875912026589672629935267844696976980890380730867520071059572350667913710344648377601017758188404474812654737363275994871, 4881261656846638800623549662943393234361061827128610120046315649707078244180313661063004390750821317096754282796876479695558644108492317407662131441224257537276274962372021273583478509416358764706098471849536036184924640593888902859441388472856822541452041181244337124767666161645827145408781917658423571721, 18237936726367556664171427575475596460727369368246286138804284742124256700367133250078608537129877968287885457417957868580553371999414227484737603688992620953200143688061024092623556471053006464123205133894607923801371986027458274343737860395496260538663183193877539815179246700525865152165600985105257601565]
p = 101524035174539890485408575671085261788758965189060164484385690801466167356667036677932998889725476582421738788500738738503134356158197247473850273565349249573867251280253564698939768700489401960767007716413932851838937641880157263936985954881657889497583485535527613578457628399173971810541670838543309159139
for i in range(0,10):
    print(legendre(ints[i],p))

ints[5]为1，其余都为-1，所以只有ints[5]为平方剩余。

费马小定理推导求解

在提示中提到可以用费马小定理解

$$\begin{align} a^{p-1}&\equiv1\ \ \mod{p}\\ a^{p+1}&\equiv a^{2}\mod{p}\\ a^{\frac{p+1}{2}}&\equiv a\ \ \mod{p} \end{align}$$

那么很显然，的平方根即

from gmpy2 import powmod
p = 101524035174539890485408575671085261788758965189060164484385690801466167356667036677932998889725476582421738788500738738503134356158197247473850273565349249573867251280253564698939768700489401960767007716413932851838937641880157263936985954881657889497583485535527613578457628399173971810541670838543309159139
a = 85256449776780591202928235662805033201684571648990042997557084658000067050672130152734911919581661523957075992761662315262685030115255938352540032297113615687815976039390537716707854569980516690246592112936796917504034711418465442893323439490171095447109457355598873230115172636184525449905022174536414781771
print(powmod(a,(p+1)//4,p))

得到答案

93291799125366706806545638475797430512104976066103610269938025709952247020061090804870186195285998727680200979853848718589126765742550855954805290253592144209552123062161458584575060939481368210688629862036958857604707468372384278049741369153506182660264876115428251983455344219194133033177700490981696141526

SageMath列方程求解

也可以用SageMath解决。

p=101524035174539890485408575671085261788758965189060164484385690801466167356667036677932998889725476582421738788500738738503134356158197247473850273565349249573867251280253564698939768700489401960767007716413932851838937641880157263936985954881657889497583485535527613578457628399173971810541670838543309159139
a=85256449776780591202928235662805033201684571648990042997557084658000067050672130152734911919581661523957075992761662315262685030115255938352540032297113615687815976039390537716707854569980516690246592112936796917504034711418465442893323439490171095447109457355598873230115172636184525449905022174536414781771
PR.<x>=PolynomialRing(Zmod(p))
f=x^2-a
f.roots()

用SageMath求解它的根，得到两个数，最大的即为答案，与上一个方法相同。

Modular Square Root

In Legendre Symbol we introduced a fast way to determine whether a number is a square root modulo a prime. We can go further: there are algorithms for efficiently calculating such roots. The best one in practice is called Tonelli-Shanks, which gets its funny name from the fact that it was first described by an Italian in the 19th century and rediscovered independently by Daniel Shanks in the 1970s.

All primes that aren’t 2 are of the form p ≡ 1 mod 4 or p ≡ 3 mod 4, since all odd numbers obey these congruences. As the previous challenge hinted, in the p ≡ 3 mod 4 case, a really simple formula for computing square roots can be derived directly from Fermat’s little theorem. That leaves us still with the p ≡ 1 mod 4 case, so a more general algorithm is required.

In a congruence of the form r2 ≡ a mod p, Tonelli-Shanks calculates r.

Tonelli-Shanks doesn’t work for composite (non-prime) moduli. Finding square roots modulo composites is computationally equivalent to integer factorization - that is, it’s a hard problem.

The main use-case for this algorithm is finding elliptic curve co-ordinates. Its operation is somewhat complex so we’re not going to discuss the details, however, implementations are easy to find and Sage has one built-in.

Find the square root of a modulo the 2048-bit prime p. Give the smaller of the two roots as your answer.

Challenge files:
- output.txt

这一节讲了求模p平方根的方法，叫Tonelli-Shanks但实际上我根本没明白他到底在讲些什么

实际上计算还是很简单的，Python中有很多库都支持计算模p平方根（比如sympy中的sqrt_mod）。

这里继续用上一题中的SageMath计算

a = 8479994658316772151941616510097127087554541274812435112009425778595495359700244470400642403747058566807127814165396640215844192327900454116257979487432016769329970767046735091249898678088061634796559556704959846424131820416048436501387617211770124292793308079214153179977624440438616958575058361193975686620046439877308339989295604537867493683872778843921771307305602776398786978353866231661453376056771972069776398999013769588936194859344941268223184197231368887060609212875507518936172060702209557124430477137421847130682601666968691651447236917018634902407704797328509461854842432015009878011354022108661461024768
p = 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161
PR.<x>=PolynomialRing(Zmod(p))
f=x^2-a
f.roots()

得到答案为

2362339307683048638327773298580489298932137505520500388338271052053734747862351779647314176817953359071871560041125289919247146074907151612762640868199621186559522068338032600991311882224016021222672243139362180461232646732465848840425458257930887856583379600967761738596782877851318489355679822813155123045705285112099448146426755110160002515592418850432103641815811071548456284263507805589445073657565381850521367969675699760755310784623577076440037747681760302434924932113640061738777601194622244192758024180853916244427254065441962557282572849162772740798989647948645207349737457445440405057156897508368531939120

Chinese Remainder Theorem

The Chinese Remainder Theorem gives a unique solution to a set of linear congruences if their moduli are coprime.

This means, that given a set of arbitrary integers ai, and pairwise coprime integers ni, such that the following linear congruences hold:

Note “pairwise coprime integers” means that if we have a set of integers {n1, n2, ..., ni}, all pairs of integers selected from the set are coprime: gcd(ni, nj) = 1.

x ≡ a1 mod n1
x ≡ a2 mod n2
…
x ≡ an mod nn

There is a unique solution x ≡ a mod N where N = n1 * n2 * ... * nn.

In cryptography, we commonly use the Chinese Remainder Theorem to help us reduce a problem of very large integers into a set of several, easier problems.

Given the following set of linear congruences:

x ≡ 2 mod 5
x ≡ 3 mod 11
x ≡ 5 mod 17

Find the integer a such that x ≡ a mod 935

Starting with the congruence with the largest modulus, use that for x ≡ a mod p we can write x = a + k*p for arbitrary integer k.

这节课介绍的是求一元一次同余方程组的中国剩余定理。

我们可以用遍历找到答案，或是用数学公式求解

from gmpy2 import invert
a1,m1=2,5
a2,m2=3,11
a3,m3=5,17
M1=m2*m3
M2=m1*m3
M3=m1*m2
print((a1*M1*invert(M1,m1)+a2*M2*invert(M2,m2)+a3*M3*invert(M3,m3))%935)

答案为872。

Adrien’s Signs

Adrien’s been looking at ways to encrypt his messages with the help of symbols and minus signs. Can you find a way to recover the flag?

Challenge files:
- source.py
- output.txt

非常简单粗暴，给了一个源码和output让我们解答。

那就让我们先来看看源码，大致意思是把flag中每个字符转换为8位二进制数组成二进制字符串，然后判断字符串中的字符，如果是1则将n直接添加到ciphertext中，如果是0则将-n模p的余数添加到ciphertext中。

e是大于1小于p的随机正整数，n是a^e^模p的余数。

计算一下勒让德符号legendre(a,p)结果为1，所以a是模p的二次剩余。由二次剩余的性质可知n也是模p的二次剩余，-n则是模p的二次非剩余。

所以plaintext中每个1对应ciphertext中一个模p二次剩余数，反之同理。

得到plaintext后每隔8位转为byte字符就是flag了。

from gmpy2 import legendre
p = 1007621497415251
ciphertext=[67594220461269, 501237540280788, 718316769824518, 296304224247167, 48290626940198, 30829701196032, 521453693392074, 840985324383794, 770420008897119, 745131486581197, 729163531979577, 334563813238599, 289746215495432, 538664937794468, 894085795317163, 983410189487558, 863330928724430, 996272871140947, 352175210511707, 306237700811584, 631393408838583, 589243747914057, 538776819034934, 365364592128161, 454970171810424, 986711310037393, 657756453404881, 388329936724352, 90991447679370, 714742162831112, 62293519842555, 653941126489711, 448552658212336, 970169071154259, 339472870407614, 406225588145372, 205721593331090, 926225022409823, 904451547059845, 789074084078342, 886420071481685, 796827329208633, 433047156347276, 21271315846750, 719248860593631, 534059295222748, 879864647580512, 918055794962142, 635545050939893, 319549343320339, 93008646178282, 926080110625306, 385476640825005, 483740420173050, 866208659796189, 883359067574584, 913405110264883, 898864873510337, 208598541987988, 23412800024088, 911541450703474, 57446699305445, 513296484586451, 180356843554043, 756391301483653, 823695939808936, 452898981558365, 383286682802447, 381394258915860, 385482809649632, 357950424436020, 212891024562585, 906036654538589, 706766032862393, 500658491083279, 134746243085697, 240386541491998, 850341345692155, 826490944132718, 329513332018620, 41046816597282, 396581286424992, 488863267297267, 92023040998362, 529684488438507, 925328511390026, 524897846090435, 413156582909097, 840524616502482, 325719016994120, 402494835113608, 145033960690364, 43932113323388, 683561775499473, 434510534220939, 92584300328516, 763767269974656, 289837041593468, 11468527450938, 628247946152943, 8844724571683, 813851806959975, 72001988637120, 875394575395153, 70667866716476, 75304931994100, 226809172374264, 767059176444181, 45462007920789, 472607315695803, 325973946551448, 64200767729194, 534886246409921, 950408390792175, 492288777130394, 226746605380806, 944479111810431, 776057001143579, 658971626589122, 231918349590349, 699710172246548, 122457405264610, 643115611310737, 999072890586878, 203230862786955, 348112034218733, 240143417330886, 927148962961842, 661569511006072, 190334725550806, 763365444730995, 516228913786395, 846501182194443, 741210200995504, 511935604454925, 687689993302203, 631038090127480, 961606522916414, 138550017953034, 932105540686829, 215285284639233, 772628158955819, 496858298527292, 730971468815108, 896733219370353, 967083685727881, 607660822695530, 650953466617730, 133773994258132, 623283311953090, 436380836970128, 237114930094468, 115451711811481, 674593269112948, 140400921371770, 659335660634071, 536749311958781, 854645598266824, 303305169095255, 91430489108219, 573739385205188, 400604977158702, 728593782212529, 807432219147040, 893541884126828, 183964371201281, 422680633277230, 218817645778789, 313025293025224, 657253930848472, 747562211812373, 83456701182914, 470417289614736, 641146659305859, 468130225316006, 46960547227850, 875638267674897, 662661765336441, 186533085001285, 743250648436106, 451414956181714, 527954145201673, 922589993405001, 242119479617901, 865476357142231, 988987578447349, 430198555146088, 477890180119931, 844464003254807, 503374203275928, 775374254241792, 346653210679737, 789242808338116, 48503976498612, 604300186163323, 475930096252359, 860836853339514, 994513691290102, 591343659366796, 944852018048514, 82396968629164, 152776642436549, 916070996204621, 305574094667054, 981194179562189, 126174175810273, 55636640522694, 44670495393401, 74724541586529, 988608465654705, 870533906709633, 374564052429787, 486493568142979, 469485372072295, 221153171135022, 289713227465073, 952450431038075, 107298466441025, 938262809228861, 253919870663003, 835790485199226, 655456538877798, 595464842927075, 191621819564547]
plaintext=''
for i in ciphertext:
    if legendre(i,p)==1:
        plaintext+='1'
    else:
        plaintext+='0'
flag=''
for i in range(0,len(plaintext),8):
    flag += chr(int(plaintext[i: i + 8],2))
print(flag)

答案为crypto{p4tterns_1n_re5idu3s}

Modular Binomials

Rearrange the following equations to get the primes p,q

N = pq
c1 = (2p + 3q)^e1 mod N
c2 = (5p + 7q)^e2 mod N

Challenge files:
- data.txt

$$\begin{align} c_{1}&=(2p+3q)^{e_{1}}\mod{N}\\ c_{1}^{e_{2}}&=(2p+3q)^{e_{1}e_{2}}\mod{N} \end{align}$$

将右式展开后，因为，所以所有含的项都可以约掉

$$\begin{align} c_{1}^{e_{2}}&=(2p)^{e_{1}e_{2}}+(3q)^{e_{1}e_{2}}\mod{N}\\ 2^{-e_{1}e_{2}}c_{1}^{e_{2}}&=p^{e_{1}e_{2}}+2^{-e_{1}e_{2}}(3q)^{e_{1}e_{2}}\mod{N}\\ \end{align}$$

同理，二式也可以进行化简

$$5^{-e_{1}e_{2}}c_{2}^{e_{1}}=p^{e_{1}e_{2}}+5^{-e_{1}e_{2}}(7q)^{e_{1}e_{2}}\mod{N}$$

两式相减

$$5^{-e_{1}e_{2}}c_{2}^{e_{1}}-2^{-e_{1}e_{2}}c_{1}^{e_{2}}=5^{-e_{1}e_{2}}(7q)^{e_{1}e_{2}}-2^{-e_{1}e_{2}}(3q)^{e_{1}e_{2}}\mod{N}$$

可见右式为的倍数，，所以为左式与的最小公倍数。

from gmpy2 import powmod,gcd
N = 14905562257842714057932724129575002825405393502650869767115942606408600343380327866258982402447992564988466588305174271674657844352454543958847568190372446723549627752274442789184236490768272313187410077124234699854724907039770193680822495470532218905083459730998003622926152590597710213127952141056029516116785229504645179830037937222022291571738973603920664929150436463632305664687903244972880062028301085749434688159905768052041207513149370212313943117665914802379158613359049957688563885391972151218676545972118494969247440489763431359679770422939441710783575668679693678435669541781490217731619224470152467768073
e1 = 12886657667389660800780796462970504910193928992888518978200029826975978624718627799215564700096007849924866627154987365059524315097631111242449314835868137
e2 = 12110586673991788415780355139635579057920926864887110308343229256046868242179445444897790171351302575188607117081580121488253540215781625598048021161675697
c1 = 14010729418703228234352465883041270611113735889838753433295478495763409056136734155612156934673988344882629541204985909650433819205298939877837314145082403528055884752079219150739849992921393509593620449489882380176216648401057401569934043087087362272303101549800941212057354903559653373299153430753882035233354304783275982332995766778499425529570008008029401325668301144188970480975565215953953985078281395545902102245755862663621187438677596628109967066418993851632543137353041712721919291521767262678140115188735994447949166616101182806820741928292882642234238450207472914232596747755261325098225968268926580993051
c2 = 14386997138637978860748278986945098648507142864584111124202580365103793165811666987664851210230009375267398957979494066880296418013345006977654742303441030008490816239306394492168516278328851513359596253775965916326353050138738183351643338294802012193721879700283088378587949921991198231956871429805847767716137817313612304833733918657887480468724409753522369325138502059408241232155633806496752350562284794715321835226991147547651155287812485862794935695241612676255374480132722940682140395725089329445356434489384831036205387293760789976615210310436732813848937666608611803196199865435145094486231635966885932646519
q = gcd(powmod(5,(-e2 * e1),N) * powmod(c2, e1, N) - powmod(2, (-e1 * e2), N) * powmod(c1, e2, N), N)
p = N//q
print(p)
print(q)

得到结果为

p=112274000169258486390262064441991200608556376127408952701514962644340921899196091557519382763356534106376906489445103255177593594898966250176773605432765983897105047795619470659157057093771407309168345670541418772427807148039207489900810013783673957984006269120652134007689272484517805398390277308001719431273
q=132760587806365301971479157072031448380135765794466787456948786731168095877956875295282661565488242190731593282663694728914945967253173047324353981530949360031535707374701705328450856944598803228299967009004598984671293494375599408764139743217465012770376728876547958852025425539298410751132782632817947101601

---

那么到这里第二章的内容也结束了！这一章全是数学知识，孩子学得很开心，脑子快要烧了。