中国剩余定理

信息安全基础与密码学综合实验

实 验 报 告（二）

中国剩余定理

一、实验目的（包括实验环境、实现目标等等）

1. 实验环境：Python 3.11.3
2. 实现目标：根据中国剩余定理的原理，编写程序进行一次同余方程的求解，并且基于给定的大整数进行测试、验证。

二、方案设计

背景

本实验旨在通过代码实现中国剩余定理来解决同余方程组的问题。中国剩余定理是数论中的一个重要定理，它提供了一种在模数互素的情况下，求解多个同余方程组的方法，十分便捷。

原理（中国剩余定理）

设正整数 ( $m_1, m_2, \ldots, m_k$ ) 两两互素，对任意整数 ( $a_1, a_2, \ldots, a_k $)，一次同余方程组：

$$\begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_k \pmod{m_k} \end{cases}$$

在模$ m$意义下有唯一解，该解可表示为：

$$x \equiv M_1M_1^{-1}a_1 + M_2M_2^{-1}a_2 + \ldots + M_kM_k^{-1}a_k \pmod{m}$$

其中：

$$m = m_1m_2\ldots m_k, \quad M_j = \frac{m}{m_j}, \quad M_jM_j^{-1} \equiv 1 \pmod{m_j}, \quad j = 1, 2, \ldots, k$$

算法

如果我们有一组同余方程：

$$\begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_k \pmod{m_k} \end{cases}$$

需要求其解：

1. 判断正整数 ( $m_1, m_2, \ldots, m_k$ ) 是否两两互素；是，则继续，否则输出“不能直接利用中国剩余定理”。
2. 计算 ( $m = m_1m_2\ldots m_k$ )，$M_j = \frac{m}{m_j} $。
3. 计算 $M_j^{-1} \pmod{m_j}$。
4. 计算 $x_j \equiv M_jM_j^{-1}a_j \pmod{m_j}$。
5. 计算 $x \equiv \sum_{j=1}^{k}x_j \pmod{m}$。

三、方案实现

流程图

主要函数介绍

欧几里得算法

用于计算最大公约数和模逆：

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    g, x1, y1 = egcd(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    return g, x, y

模逆运算

定义 invmod(a, b) 函数，用于求解 ( a ) 模 ( b ) 的逆：

def invmod(a, b):
    g, x, y = egcd(a, b)
    if g != 1:
        raise ValueError('模逆不存在')
    else:
        return x % b

中国剩余定理实现

定义 crt(a, m) 函数，输入 ( a ) 和 ( m ) 两个数组，分别求出各项数值并打印结果：

def crt(a, m):
    for i in range(len(m)):
        for j in range(i + 1, len(m)):
            if egcd(m[i], m[j])[0] != 1:
                print(f"m[{i}]和m[{j}]不互素,不能直接利用中国剩余定理")
                sys.exit(1)
    M = 1
    for i in m:
        M *= i
    print(f"m = {M}")
    M_j = [0] * len(m)
    N_j = [0] * len(m)
    x_j = [0] * len(m)
    x_ans = 0
    for j in range(len(m)):
        M_j[j] = M // m[j]
        N_j[j] = invmod(M_j[j], m[j])
        x_j[j] = a[j] * M_j[j] * N_j[j] % M
        print(f"M[{j}] = {M_j[j]}\nM[{j}]^-1 = {N_j[j]}\nx[{j}] = {x_j[j]}")
        x_ans += x_j[j]
        x_ans %= M
    return x_ans % M

主函数

读取文件中的数据，分别解析 ( a ) 和 ( m ) 数组，并调用 crt 函数进行计算：

if __name__ == '__main__':
    with open("4.txt", 'r') as f:
        lines = f.readlines()
    lines = [line.strip() for line in lines]
    a = [int(line) for line in lines[:3]]
    m = [int(line) for line in lines[3:6]]
    x = crt(a, m)
    print(f"x = {x}")

四、数据分析

测试数据与运行结果

对于 1.txt

4287515873132249290206743177914384561990566578711226941286419682287340749050657014821437224252742510554110503337292273093244157462381584685591016767785322030525556423396932770357076761886205280501197627765160017336467165781735019979121735426313741358
9771213103492817551591736308167187727178414122203761280661360222386950001056708945835617029274862813823697577841711021589284847322704660314093793164431513466118083565545914124844865718601678585640515334042262368481197071154064487046068421730243918436
2871231008911723824076489774982060049173360467932843727430035963211499257855033672890013137615901197366662729491707870527026785205880503044112360438626531884437395888361473482075216260556158042797849456731292280076916674319344428850262268951454742769
523588466314748561196800547940629847378796004147993330931776203208323618661627286646160693474256366051855641456936957996916791238107540211391414024227284220353391110201587430764443793515845351571689819479217940971087824120375329864822917836240987338016618026960507206742219347185084380693186775229819
317745883257029510336183192778003289012257294858665410453006329348840569846686869388239118060047339072195255137025252583106134251049564221071665049427912133921409213745644834553780586494509368977383172661987062891371874646381447459043958986576855501862553382811348208828172964166628664439116854493278
274509651013765749900581458403181028928811855296015383658106227866104786947166444350049845567188043293317048016470662312247176561908274271045049786210266815953952092252708145204148233325749861787089768619491551224058050260278439653129762278559642431354065023465249888103710665657431717274663995421146

运行结果：

m[1]和m[2]不互素,不能直接利用中国剩余定理

对于 2.txt

2723892435966726189283462276643000548302226198889141817271757889651791308558358920795889114701247042820953483001071963208633889856501082910099461214048359204822344882593461206652273529272346755366022660843454301688458652872256466505628217179694074094
2574998818518266651220122107251540966447132827595609705116996618260293790734419076247444256252913539722381387572958613725900982296614578282669882909634235393122965926856917378784459675539995451129795956896012126332225498107074370341403693020317759418
1781258431311982632509611410510400792618440693508399564824629398616965024476334843482876127346406898293301878103754249257328472698732075070095284373461813427012777487042219973876236132881332648134355962699370943697607785129797620664715009015407521642
759559057169065570999365038186245069257166785574400967089713556997586313978702767033720062027310916321816725456168230628730432721763523085247850176915093667510118867133688773720665005106656294000822021407867602170116979006350351962115410840112983409275865316166602058575897774587037222032050625198776
162096068855815576871200156982612105191973597814288277415871059518357860258523595254074620436189056715082088810045021486961809615856369594829505800620058919009041671018055868246962688383106910337278589526663076908482043347921324756884818583808332776724939914794568740995016696150714984320332832165639
221565095752045847693974642381259072766160166741185970477021942423348168207374731906401091326965278115747898341405162270873799283241313819410812712020488498760003564364189286994891360176169449650229402226518150330938294146833925692827181229808371227478309250733697671916325016948939371162416317936664

运行结果：

m[0]和m[1]不互素,不能直接利用中国剩余定理

对于 3.txt

9627297126611174594522186713351637491244433834447229238430307159786950107250136874379769639524094482401960267574348651618425247869257869043925209428739949361336393570622010769855217975387876361864613203164797704720546119428340704360000321372125079451
3368239602193026714994792600570855858637938975042620061387630778780542928245424087992306458841966330024770821112030902265998997268253438791767794086742829965256363777663260688838137020186571613597169435250709651247156388793983980734625262154786871249
9998710312818046344741965494024275281792837383458797610964276251929744291966010433420065501069534288072000719966384862116781315396878264878225506588891085271739437315612072840823244230137551451832073695252719636345922452993935602737905493910007729373
858965591728706423530311864597452473389568979454299710257413628272687981748566305677123933001010648857449475472117317710924545723205231784914795276636826867781542494530392050266688097787411462387564569946366372734004445404346335720435524740834791132820370057578926512094810495815016020866579264076589
366047310809781584236826454375586522253024244215547391088400197400590448561225130055859938711550691842370297092970200272442715853500436351502510547208183430404757705676909484899400733434837764512565165408608277011211200399290438709664869935571120849289194196434871217206016776476885229737822799548497
248988308048501980592472496030060787190255544508964420449149705972243053385845017852879586545253289642107087862508950446371961849575493137717610704043491971035499691602701547145350999437476962412738959026455512044796946218712762146613024038832960777009419158527491051855424828882137045359168294259229

运行结果：

m = 78287412980376778076356330343010712928504093286414501978056136421346923608214943588658577249413253906863855434149139814410874226604715450863516781068644239602736664460753109818735066304873954227519853772187144524675831599437550405806801280057386996727609166021245027468914572777539437303000444501504048570209220229678498506457906748094298324015001174909574665390550722854633113078215992470687106331683828240958675269114345085029335132922023910442782601343804459448240738645342407674106302379038415344421713369000206601558012539385859569521503791827711638045218891113192096568493855891249744256954140887267219553896082078832817346891055752997176740893479550830537555872631830660453602712896542818910263695754475316305359766376941161069335663899971097631919628234709234321017873779741832889295952146633411206068842200647171305828718652115555606614854351610831089729313987249619966900062564582790458857
M[0] = 91141500584231646073509664268202103376425461137950468170960679074418203232198965978454323889094755473581549892088499813822736287803377193004618890770741451259217393112366126400897648208435770062330393483025404064027371010722604169384184966766057947010452190881808567624132394280027224798232248490686969124599610676474861261638871834392069263633302593216693666949218945969992488151914647624518567579653575266039683558517470888519866293866374927162698799789993562217395133745633874613057298575732959643258328874996616152992056018866134135319879761024113478291331671348374358912841179208704258275328813
M[0]^-1 = 320547619181159049322077118411227037468064793575040608846075237755836487801700148417060649633206869993115048230380752832380479974566385261202288191346840879534492067708728283547597296595306916462267542618615501431674645605394548373808838756825120926783638559532566096931878831265545179835546789372264
x[0] = 63761831873048043488707437323494892443821589645924158626227691821829807769341772126841657809332423164650868345656355197589623178597175713311253895913723254901662077555676313550361654060656463022394630803094183004307893442926672214343239393987208881962626515342421833278880768791776001996627788699599378063661428951030405983306791983736070264315929649817008298960421656582858000295830818374033000716176058504662443979721702554378206673890885504438848490653321511218895808248988766847460838976999636998444737300490643501653955668226611278961561883584637859871727549939122285874706695853642984283513160397079986509414860743282712841423599541009091132762204521701041424552165531908481367807864368157261738339011024247040868381463800181153994304152813083926164461654061610006689717708653041276773797783801648790673871119044838127725018729909448522992416331038908154910286989196407770692812106899349574459
M[1] = 213872389356410939883171110393828339367097726987457315792740781843561533957969696863941853547082329261290208731728350965623176123993606589476237456325733938636326135401088469788341766520067291883866899673560260424025642561499630202808648922560040515931062715906757475127171391238795136363684202744189925453246422862897933707118572601308153643230917138947321953034226304316146263173359790713308085846690902099953901885122247440184238946095569769209540633465678529654073664265506529438757875301622518608718138915357407106502664208934558435852338712088148111500546140023369239437338106891432516476089881
M[1]^-1 = 343826330536106960353061805122177953555914159110936313170560286502610601755924936251169628136107275506184388479957531650524010016219464217673334717398938107272517664007681354336946818629001750582409029904577881120965297425765775466066748893609205077900233414031147941984355363974492417453326969146315
x[1] = 35473387307966623060435227526207454131287017473972731920099867085795393269268200807647555574010120093418012250150316162080615355792814565319621973220804769309548584754943037566384665281371268269671559366106249044676318078275525671076144454589046412195052737258202485574504477783763005431931007482153514827504112070350879502742173260942541221484291502403727503499572019829341890754823863152567554284072037323876987197386214431353047362035516416603595523808926636409673269358752087475944123355846074623871954153452083217760759523202189312615305373988262001067363572374305910752013385444740867209604666317474424434288275987903787132398086019045175199662304266815565067085517508478657539779196348922719773908681892936887487353832331408779451196024501834987466988238393042575210531255930204906567995193475758621539433356905773719267327298445782982540324482088031890950989996556480780385724295095528082929
M[2] = 314422044930425753787986322934069696088918746488682683882672575592826395660214468557834291300881977059953634119334958917805399915538514934054133242076907030736447952341326631294732074595485309665758378246652521817854415633550693897963072823597299540874032658759055442778115326467268215317895856954097580723645997287745166271875370449399872731972755192023188604631936657442680823677142761426075898355918923785877348041953885157945497083946070166930607084052550155747868727943177822781825442120316771752259124115376938461518438926049011365544800168233861529992371023232092921550379377486172960827836733
M[2]^-1 = 171186076079321078367101575960694921294374067879934648421488245907002475562684917105185920684716936273216380839736513957879874241450376581095332253869658903318243873822904296630267540815663416362709538720252781847727019819550604706714057535198675840876906732869052191429307881256733724106112724649496
x[2] = 47200825634455050532312818099810268721618176371369899046298115321107152344004756989541002730626838019846887825238204935164180362103035511840169953065440436147120465585231396309556414635693177956708000061108343828821141006592264452831603228311134525870962212789941033537990174479116087640188307196063063784768086734613375651677067754888322066325187296090818178286051090001090617009146265496228315091709963626515815207477757184321085438121555815550954213139676451460145621100608747895789912476120799113753289235945611889364774276140189464398620226729810648885994621160099194586557506758182306784859330709991139621885807753398763213292528893030364981745386709090212399155101761411572747544497737739834126236926301916126369855722734652299816107803845714930934446141296229750277471721702350054220125998538261814972488362472736525243565427018163357251689722622426878699011478168329078613001651304312049219
x = 68148631835092939005099152606501902368222690204852287614569537807385429774399786335371638864556127371051912986895736480423544669888310339607529041131324220755594463435097637607567667672846955021254336458121631353129520928356911932444185796830002823301032299369320324922460848277115657765746658876311908105724407526316162631268126251472635228110407273401979315355494043558657394981584954552141763760274231214096571115471329085023004341125933826150615626258120139640473960063007194545088572429928095391648267320888132007221476928183130486453983692474998871779866852360335294644783732165316414021023016537278331011692862405752445840223158700087454573276415946776281334920152971138258052418661912000905374788864743783749365824641925081163925944081189536212646267799041648011159846906543763348265966829182258021116950637776177066407192803257839256169576184138535834830974476671597662791475488716399247750

对于 4.txt

4295624200916103150599187894069568981644887527006022293335411265325330766209384042149064411907179821424044008998783005917891040115867971765387896882502372910534420366586969297740256508667912971220346963656236357992720027363453060989101521723818782859
5048708579602446318345786079263805330041321937318356977713731438546230007240990016692471522814001533907319360690279621114614314033960765948096994997978898030493629876397052852607482295309726966711964115036814323557452116697775795013599746606308941699
3596008781131805011469947008682729873414721821476767635020831688934235027100273960073060644233468675066081666974397611077160956117019314165266334949865339553955144752190049946668292832024262707189972278781623056371646171170037065247015908280526298099
253268116941049462372755485294627845953395456491303414556526733075374137967004752504673449144127614535913543873030021468008726507050465022071707160741698808385761380642247594073913361295533275673179302652183682186833234185200977261250232230317956532527047423424409071712741825783736332529018918148163
125248861531316255813195601224233646259612691753136401744012312139150529279621053123373479202484067233487585722100985297146237842513670859818330920681154364341465011756714318618809651568983662473459040332663903629238803126754073155288151349861846938331504036858910307146027842456534288216106730122837
698855668303654763609354611237287260490079971863647816714075293967494108799939157241632182265896815845218861766490836254355441380776592281152436190044369477118275337292092410384500713140977087470037378083843253426645431017510956102035201863381656508487752007901934453758443979487225850241951137642259

运行结果：

m = 22168780348867171528948488543594791300889570117946595529607495373231382034508616731458480970224620909021667079453644961637539651867608550153454231110622098123829139715657196042438236320461852762940237131407534717478418516205574692699559122024646158088291023862838836800936731066493487351132547428189898512223610203328680646707788816893775115564239624216501867464765882220724274524724774184452430883121017321235694652884319431368920443431386802617987991110600809865687010919563113734239817324173081054598419957265168132116914229640083791071084712423477676610265275685983951965918677979500610328407489537774227024513958173006981388439440209243566375675196633237430607975232774090044896921558728965187714870541763254509770961580154255231609465440449008589013093448848607145499182159176478202756575907929718858873114546063206660878750226910009178496116384479400749146914511936056670489070659811817395629
M[0] = 87530876829739938316222321171554745818518198149502424918412021513861776351117551320653502598133273315079967121338948648694839009408530719322997914554448286258476245493581894386487755341031986745292922341174213769934239655085796050463990085063499446712523431661098220935659056351978808806178678228380784295812134260743757040134199914382017985636755916737721795547290125878690641838390537897868815394311706169119610196966335953846968164663975444357454392519124033384897405376961858302274162186883427055117084284201293712464676956900636322993950089215871079893955789758278504906842218411054197632168783
M[0]^-1 = 106103690019916658417780285614758894184393291283187640245041510410057420120895693784977049498331922780543489279621835812962923311335991594446483798048098214045984913203354219527731681505277375065692103994606507675923682922836102562644899271332133164808667125430191713114424322029633819073975843563047
x[0] = 11529904910092211794708777313536463759734181675525855398311232613624581361044791848157673187984087828942264976084452887164426498581317075816115174416995715192585098624070050053044955486779656803996137366045189554596033258389494038459390355616565301238674393166064468298272220701319949177690655828215588083668260451756856136890269189574060457856632634253790001987146348622833429640004988438482939923256849122779321894589003949162749115781062026779523465885368185376306221989192936615580588927546876893810044327682704269796699608799792227348818903386487713602681448670726822072505643805742079504292641446727950362862554838089382552789185591841431541637024304459448134331987700094974473624919843515530309981045358443041141280767528091544096450115360551904341297396172331738761095723644694127301482636990614630131119315466000859773406760818543132999616814348890150633826160878069087728136754733888501661
M[1] = 176997859124845308827073654081730807353583878165730595041585783923670239037352188227085770027784021016118976417121584776330808082900224105739218957022163015943537432575713646458108238475705448666848240754989161722873490008680242507495549799396847627285889505247060985199062700786676654523371015065115609945828686224799267674385795050932049669887321595668097105528570809324446166664864164308519324486723848510744562285844647344274656633669608712184942569521293548933012117116498287867252821198850326968766876864542076697791199469807640027411533673164540183115228523725723371039069547763133662252020217
M[1]^-1 = 43099871028909216371616908875643260778675513073156218374064652173406965258937674954865561608797638050131480624577004104520432006636732276367686673654636368667869260874906381481728058058329979468355143884869951972371506224071871591869526220916066955665294561948491149284380394402970145507264517062588
x[1] = 637983223256148573502603886920565838551398174405937952796359014741393904804513116677045571760338560261031824541054224879743163719119010019895506818134016461072851498685949140083496853465651646241537043814275626496922285578478281960313085700630508676132125062831096102800343622853249182606901604697963746809916879993417587937546810483000957727789753583635871473076407449819717675137505656667269476659816686019988544538352122890047376651201898366120461482974254343945038358785088657701627511052203188689345463951573896834443279097102942165235550511512890174130622947892169188870934777645471792451434223134688592176714117386818872872056513485429331089119534979193802541748405524478675174860941781123987093081319062901531051093852369165144567405722164287934380211315098959899827671023679720057720847983118232436323558008699969805695022061016503434320611181392004291869000219421957604657712559027679590
M[2] = 31721543309046716916826956709116478069932767217494091911269201221189168624352559748640347775841896704395975693668800627542745391835258718285935050403529440497737736356899053352886909563029941307075345076769095069146884881981008604575634569105223405679345656801818869778777844218903912656392240517833380574311381422626719040288701382403284935586935758814630615783499767536005412900480995435888471433602865846542539186386857096627737975865147572507061900656231178881420927168336478674561238408611820756692155539417285018071241057683421925668991255573282200879969807589783948383602100948258285555898431
M[2]^-1 = 165592398033830753047012925837936946080990788458660508576840156491536833493695774067168215987793323737332132960129098139191025491180021323050876628141140652466325110012977903716975947998703110454325807253712423333507448852259199046136163565803732891004123735908097863812713084147418544465685367018743
x[2] = 11146319817431279803831914439933813295569195210199565873650576775331474684993506409706105283174682760340797044860862515134100529018220613518882324755076645817216759559098671339476217832603867379028284394380116996889278442222936243993903518040193490475511215497977318547705091204239081286171907090316231947988905308497896036481769961957917673074890910328249452584723924405139521044751171450891841154197006204640780298055269098954581362212434489280938082244538296400535424144615489051159375450709197911500229166695347923584911530644891164989295132575117764971629821367652748810702270621364312661872974620396535059376774538452930019407716111633068991597185788152677990033448867541554526234248576533020358585178423793173814232434015859296018196136178184901314154285054374664924582448468535017191561715617877178055663698493334802247540100597969943742231035023236805403790117168488158447075736056978482683
x = 1145427601912468643094807096796051592965204942184763695150673030466067916334194643082343072694488240522426766032724665540730539451048149201438774879584279347045569966197474490166433852387323066325721672832047460503815469985333871714047837332743142302026709864034046147840924461918792295336917095039885266243472436919489114601797145121203973095073673949173458580180798257068393835168891361589619670992654692204396084298305739638457411213311611808594018502279926255099673573030400590201774565135196939401199001064457958099140188901702543432264874049640692138176617300287788106160171225251253630209560752484946989902085320922150056629518007716363488648132994353889318931952199070962778112470632864486940788763338044606715602715242064773649748216811892504576738443693198218086323683960430661794189292661891181749992025904828970947891656567520401680052076074118211182570766329922533290799543538077268305

五、思考与总结

问题一

若正整数 $m_1, m_2, \ldots, m_k$ 不是两两互素，是否能直接用中国剩余定理求解？
例如，方程组：

$$\begin{aligned} 7x &\equiv 5 \pmod{18} \\ 13x &\equiv 2 \pmod{15} \end{aligned}$$

需要如何求解？

答：

题目中给的方程并不是最简形式，首先需要将其拆分：

$$\begin{aligned} 7x &\equiv 5 \pmod{18} \quad \Rightarrow \quad 7x \equiv 5 \pmod{9}, \quad 7x \equiv 5 \pmod{2} \\ 13x &\equiv 2 \pmod{15} \quad \Rightarrow \quad 13x \equiv 2 \pmod{3}, \quad 13x \equiv 2 \pmod{5} \end{aligned}$$

化简后得到：

$$\begin{aligned} x &\equiv 4 \pmod{5}, \quad x \equiv 2 \pmod{3}, \quad x \equiv 1 \pmod{2} \end{aligned}$$

此时 $m$ 数组中元素两两互素，可以使用中国剩余定理求解，最终结果为：

$$x \equiv 29 \pmod{30}$$

完整代码

#中国剩余定理代码
import sys
def egcd(a, b):
        if a == 0:
            return b, 0, 1
        g, x1, y1 = egcd(b % a, a)
        x = y1 - (b // a) * x1
        y = x1
        return g, x, y
    
def invmod(a, b):
    g, x, y = egcd(a, b)
    if g != 1:
        raise ValueError('模逆不存在')
    else:
        return x % b
    
def crt(a,m):
    for i in range(len(m)):
        for j in range(i+1,len(m)):
            if egcd(m[i],m[j])[0] != 1:
                print(f"m[{i}]和m[{j}]不互素,不能直接利用中国剩余定理".format(i,j))
                sys.exit(1)
    M = 1
    for i in m:
        M *= i
    print(f"m = {M}".format(M))
    M_j = [0]*len(m)
    N_j = [0]*len(m)
    x_j = [0]*len(m)
    x_ans = 0
    for j in range(len(m)):
        M_j[j] = M//m[j]
        N_j[j] = invmod(M_j[j],m[j])
        x_j[j] = a[j]*M_j[j]*N_j[j]%M
        print(f"M[{j}] = {M_j[j]}\nM[{j}]^-1 = {N_j[j]}\nx[{j}] = {x_j[j]}".format(j))
        x_ans += x_j[j]
        x_ans %= M
    return x_ans%M

if __name__ == '__main__':
    with open("4.txt",'r') as f:
        lines = f.readlines()
    lines = [line.strip() for line in lines]
    a = [int(line) for line in lines[:3]]
    m = [int(line) for line in lines[3:6]]
    x = crt(a,m)
    print(f"x = {x}".format(x))