Constructing Miller–Rabin Pseudoprimes with SageMath
In this article we implement using SageMath the work of François Arnault Constructing Carmichael Numbers which are Strong Pseudoprimes to Several Bases
The appendix An Overview of Arnault’s Method, from the paper Prime and Prejudice: Primality Testing Under Adversarial Conditions, has also been used as a reference.
First steps
The pseudoprime number that we are going to generate has the form n = p1 · p2 ⋯ ph.
For convenience we will define h = 3, resulting in n = p1 · p2 · p3
We must also define the basis this number will pass the Miller–Rabin primality test.
t = {a1,a2,⋯,an}
To recreate the example in the appendix, we will use the primes less than 30.
t = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}
Sb Residues table
We calculate the table Sb (a⁄p) = -1
def Sb(t):
S = {}
for b in t:
S[b] = []
for p in range(3, 4*b, 2):
if kronecker_symbol(b,p) == -1:
S[b].append(p)
return S
Sb([2, 3, 5, 7, 11, 13, 17, 19, 23, 29])
2: [3, 5]
3: [5, 7]
5: [3, 7, 13, 17]
7: [5, 11, 13, 15, 17, 23]
11: [3, 13, 15, 17, 21, 23, 27, 29, 31, 41]
13: [5, 7, 11, 15, 19, 21, 31, 33, 37, 41, 45, 47]
17: [3, 5, 7, 11, 23, 27, 29, 31, 37, 39, 41, 45, 57, 61, 63, 65]
19: [7, 11, 13, 21, 23, 29, 33, 35, 37, 39, 41, 43, 47, 53, 55, 63, 65, 69]
23: [3, 5, 17, 21, 27, 31, 33, 35, 37, 39, 45, 47, 53, 55, 57, 59, 61, 65, 71, 75, 87, 89]
29: [3, 11, 15, 17, 19, 21, 27, 31, 37, 39, 41, 43, 47, 55, 61, 69, 73, 75, 77, 79, 85, 89, 95, 97, 99, 101, 105, 113]
k2 k3
We must choose k2 and k3 as 2 primes different from the bases used, in practice, greater than the last base.
Later we will analyze how to choose some values in an optimal way, for the moment we will use those of the example: k2 = 41 k3 = 101
Table
From the above table of residuals, we filter by those that satisfy the intersection condition of the sets for i between 1 and h: ki-1(Sb + ki - 1)
k = {1: 1, 2: 41, 3: 101}
def Rt(t, S):
m = {}
B = {}
for b in t:
mod = 4*b
m[b] = {}
for i in range(1, h+1):
m[b][i] = []
inv = inverse_mod(k[i], mod)
for s in S[b]:
sb = ( inv * (s + k[i] -1) ) % mod
m[b][i].append(sb)
B[b] = list(set(m[b][1]).intersection(m[b][2], m[b][3])) # Arreglar para que funcione con h distinto de 3
B[b].sort()
return B
2: [3, 5]
3: [7]
5: [3, 7, 13, 17]
7: [15]
11: [21, 23]
13: [21, 47]
17: [5, 29, 31, 39, 63, 65]
19: [33, 37, 39, 47, 69]
23: [31, 47, 57, 87, 89]
29: [19, 37, 41, 55, 77, 95, 99, 113]
For each base we must choose one of the residues.
Additional conditions
p1 = -k3−1 mod k2
p1 = -k2−1 mod k3
x2 = inverse_mod(-k[3],k[2])
x3 = inverse_mod(-k[2],k[3])
p1 = 28 (mod 41)
p1 = 32 (mod 101)
Chinese Remainder Theorem
Once we have all the constraints in the form p1 = A (mod B) , we use the Chinese remainder theorem (crt in SageMath).
We do the calculations using the numbers chosen in the example:
crt1 = [3,7,3,15,23,47,31,47,47,55] + [x2, x3]
crt2 = [i * 4 for i in t] + [k[2], k[3]]
p1 = crt(crt1, crt2)
mod = 4* reduce(lambda x, y: x * y, t, 1) * k[2] * k[3]
print("p1 = %d mod %d , k2=%d, k3=%d" % (p1, mod, k[2], k[3]))
We obtain the same result as in the example:
p1 = 36253030834483 mod 107163998661720 , k2=41, k3=101
Choice of residues
The main problem is that when the number of chosen bases increases, so does the complexity of finding compatible residues.
My solution to this problem consists of checking this compatibility progressively, instead of doing it with all the bases simultaneously. In this way, we choose the first residue of each base and if this one is not compatible with the previous ones, we go to the next one, and in case we do not find any compatible one we go back and choose another one in the previous base.
Moreover, in this way, if it is not possible to find compatible residues for all the defined bases, we can obtain a partial solution with a smaller number of bases.
residues = []
Y = {}
X = 0
Y[0] = 0
while True: #for b in t:
if X>=len(t):
break
b = t[X]
while True: #for base in B[b]:
if len(B[b])==0:
print('UNSOLVABLE, try another k2 and k3')
exit()
elif Y[X]>=len(B[b]):
residues.pop()
X -= 1
if X <= 0:
print('UNSOLVABLE, try another k2 and k3')
exit()
break
base = B[b][Y[X]]
residues.append(base)
crt1 = residues + [x2, x3]
crt2 = [i * 4 for i in t[:X+1]] + [k[2], k[3]]
try:
p1 = crt(crt1, crt2)
if X>=5:
mod = 4* reduce(lambda x, y: x * y, t[:X], 1) * k[2] * k[3]
print("%d - p1 = %d mod %d , k2=%d, k3=%d" % (X, p1, mod, k[2], k[3]))
X += 1
Y[X] = 0
break
except:
residues.pop()
Y[X] += 1
continue
The following results are obtained:
5 p1 = 290871043 mod 38262840 , k2=41, k3=101
6 p1 = 1783121803 mod 497416920 , k2=41, k3=101
7 p1 = 86343998203 mod 8456087640 , k2=41, k3=101
8 p1 = 2978325971083 mod 160665665160 , k2=41, k3=101
9 p1 = 106447014334123 mod 3695310298680 , k2=41, k3=101
Improvements
solved = False
residues = []
Y = {0: 0}
X = 0
while True: #for b in t:
if X>=len(t):
residues.pop()
Y[X] = 0
X -= 1
Y[X] += 1
solved = True
continue
b = t[X]
while True: #for base in B[b]:
if len(B[b])==0:
print('UNSOLVABLE, try another k2 and k3')
exit()
elif Y[X]>=len(B[b]):
if X == 0:
if not solved:
print('UNSOLVABLE, try another k2 and k3')
exit()
residues.pop()
Y[X] = 0
X -= 1
Y[X] += 1
break
base = B[b][Y[X]]
residues.append(base)
crt1 = residues + [x2, x3]
crt2 = [i * 4 for i in t[:X+1]] + [k[2], k[3]]
try:
p1 = crt(crt1, crt2)
if X>=5:
mod = 4* reduce(lambda x, y: x * y, t[:X], 1) * k[2] * k[3]
print("%3d - p1 = %d mod %d , k2=%d, k3=%d" % (X, p1, mod, k[2], k[3]))
open("log.txt", "a").write("%3d - p1 = %d mod %d , k2=%d, k3=%d , %s\n" % (X, p1, mod, k[2], k[3], residues))
X += 1
Y[X] = 0
break
except:
residues.pop()
Y[X] += 1
continue
Miller-Rabin pseudoprime
proof.arithmetic(False)
i = -1
D, P1, K2, K3 = 107163998661720, 36253030834483, 41, 101
while True:
i += 1
P = P1 + i * D
if not is_prime(P):
continue
Q = K2 * P - (K2-1)
if not is_prime(Q):
continue
R = K3 * P - (K3-1)
if not is_prime(R):
continue
pseudoprime = P*Q*R
print(pseudoprime)
481121197813453488822072439791414954990651681818044507
6443720759266643520397120277444812868383359470762335147
20344142377169477837040700284941512802799901617537251347
24964597503881043179618771841997687223821360798513204627
29837394232085892643153870380237568644696975862433784787
44313459019486783991509950041785277745503910274192294147
60668428110349406158611956696695902180084285902737804027
91900550475197018427841211222006307477190723489571705587
98024495406750801188170372188698667117004033867329327067
140277264152028217582056560687226797738571162579314652667
183200788011064383003373479584203142739932494189806558307
Miller-Rabin pseudoprime for primes <400
D, P1, K2, K3 = 173008463535598978105335889964045449676769752525364639390267547572932541766933240298753535702993725897270876547514121694726358789414328565199620852636229327034855880, 13690410418353044929368896733658377970427289405478462058496414793357178580977696340960396011434334102235570363541382347819399389941925528029708405522455364960935230643, 401, 421
i = 15793
P = 2746013075036067706146938606935828164715651991038562211948991793612680810706154360379174985368814247197834523678431906272632783751162416558227320531206425126822414143483
Q = 1101151243089463150164922381381267094050976448406463446991545709238685005093167898512049169132894513126331643995051194415325746284216129039849155533013776475855788071536283
R = 1156071504590184504287861153519983657345289488227234691230525545110938621307290985719632668840270798070288334468619832540778401959239377371013701943637904978392236354405923
3495700935892996495849575102560472246674767943168860068520173732981675243146346666459045803703531594886180838355802373674638075032131263557299198400609711599502974716708712723068425650500317253668183934887892215118994062994482257114660442472268384685376529188883135961482911917441363788308157016322909485207572548032195963679427678852316300519948903238741545516509080405518992849121619593677468802205375380772735673896323711357089114922999274806140879986390622161578509827266494047665614106323256669096351719947
Miller-Rabin pseudoprime for primes <=541 (100 bases) - 40 seconds
D, P1, K2, K3 = 163830761733856511988870240072545991183860227456702154728519670383547331324532868908995681607056416577049061619183840032668027646026325503554869855624445945171736628483536356155835702608605962227867004832088324490108635927029320, 61309724624610862695589712628872018557582207284360158693661111867310905398770637226362461989457090233054760243914315912657635473831084968145866149830353785538894834149435862099495304568054840446918205737017673126269089745383911027, 2081, 4177 # 100 bases
i = 47161
P = 7787732278755017824602699104690213508779614394369890477845377286825786597995065267843507802259844752423265555266243395693314487288078622041297083410934849005783165970061493954764862875292520625075354020623135144404282468700013671
547
Q = 3252935772835970945336547416029102182617244932528303252596014092707131061982538762378233209003937153087198022434709866381097461340230440426649791740747486429715628425694686024905283223009685865093975374414283549817668787175995710
6047643
R = 1620627087208919209299821683686033431177037755468374208439623013388446191042773082238233973650273692979281562050905250643778744804649161246793923057815542078103476838369796891986567964348373542078181171691674423550531181736472845
0487227
4105533452433021765013837810250129497906776520439478762444757535787150166441808983131547549061042819241803677734684089387936615218512623246819260378395895806190969367738434747226833314918439125195560533069527626034315805252829069712946717489170662443699387652432168043013276992556383661463839991504034566570743939526431419627777024666651653328024067508705964704654262029757671485757644661464119465787544601305942781717049259725682702584999377699680541279376069665052863573819455144839742780771486371611198963915144096863366918510828427548413169928095028815881158255689153934576571383186599819333534474537810962373427256838686635300737173281200715737713827696261842481543872169300021385829998511793741667
Miller-Rabin pseudoprime for primes <=659 (120 bases) - 4 minutes
D, P1, K2, K3 = 6793457464927132429839506140923221331166241933169983904080669440998323551865225177574525086971838229214342990755152217463168162824468888781497331344909044957196064039220542791586451534883392575403444258722768484053080198145074194991857958744163006288027394657809573867671273538719480, 1082010667437248961796874734910407026117763268437636443783741306377257133956559959850528382751452152066059013480363673785771001504893985670563477957863982411914255677126209398089467705585303017170266366542357800372289023063897165514359429127927131974451722841878737137362641844033906907, 2081, 4177 # 120 bases
i = 218281
P = 1483964699569196642879594114681772082414416218682714893010416347556932320358649776945995438892051272663202061378505744853863580750992787497784582461255955224713628310222225510488371695191467117768809482604806985267962687754368837522532106521762572307531359456143210330546515901149260720787
Q = 3088130539803498213832435352652767703504400151078729692354676419265976158666350185824616508334358698412123489728670455040890111542815990782889716101873642822629060513572451287326301497693443072076892533300603336342630353216841550884389313671787912971972759028234020697867299590291611559955667
R = 6198520550100534377308064617025761988245016545437700108104509083745306302138080118303422948252098165914195010378018496254588176796896873378246200940666124973628825451798235957309928570814758150920317208840278777464280146749998634331616608941402264528558488448310189550692796919100462030723123
28405815753529733559871806180650039227867183312173853665420427796878772014159921711572401606946254230318069136497853819954843219894290827397106454689820806592661994947114634189392275706284517175986740195541286806800371927994028155032848450096856722472297378042151775383466616008301763864020974316014741404820195618498752268634168176834951324092092652744315159786840924543524757372307179838259863039906757419421192850001323907093526425222439081893290512297526378692918427101494493840846656975716801804079879946067663917708606762045425485806071117778908983120127998676781134102581087012920764615219782665111270556617281369131204235756134060928359948359362510963939433119537493888316954320239178843079973668982874418895817461560956789617818976460192017033826230643346380855667183906186750875634903725232324406188659403727600027656714749497004539324774953128638940332666708267
Miller-Rabin pseudoprime for primes <=866 (150 bases) - 8 minutes
D, P1, K2, K3 = 2250542028162300204153375799483819036940380565881521892017369792873402147819921438100391052652614499581989722557044612743292071890316063115263506738931952267478191918712573601330274640160953118962248905196901713363571114121177238029573374004614554212113178449892699140204919389729228927462110471546569270024185299292143839352837409077230512452871086976514876279432547640, 956774561096681708150590904754727613528013059044072907853464565219312818165066398131272277645363153810356901606749683001363364192805948338274353580811556834009276084912662895062366451865686593067752928594372324809380605595209980033364952306384768611755478497944132336038185261066852303121708852713073740713123352192944359938216703699178305879978494286142267013692561550587, 4177, 2081 # 150 bases
i = 156155
P = 352390164968780670087720988873150489326953140324273123955825844571365425210984898564697837104614380336035962027502051185930136850225110784102247248398730563162066335151474593610791402886199320884617730719616559375097827931187641584541395169996970481604288859340938566574737372564234595470967569537067598101339778763157665594080542318154108977958063081103822772428482038274787
Q = 1471933719074596858956410570523149593918683267134488838763484552774593381106283921304742865585974266663622213388876067803630181623390287745195086756561497562327951081927709377512275689855654563335048261215838368509783627268570778898629407625077345701661114565467100392582678005200807905282231537956331357269296255893709569186474425262929713200930829489770667720433769473873781123
R = 733323933300032574452547377845026168289389485014812370952073582553011449864059573913136199014702525479290836979231768517920614785318455541716776523917758301940260043450218629304056909406180786760889497627522060059578579924801482137430643348763695572218525116288493157042028472306172193175083512206637671648888079606131102101281608564078700783130729271777055189423671121649829667
100.00% 380371432714438408643606610732822034847501900960333382032713208764416811879198939946321547624163503138106841926986062482811833773120155739166510497052364920558649187257533762310146733292309049350859872905914985367446132676885922076941014934134432725906044649741489417231517074464758740359189739317946413297918400822335298115187408307788994326109218134963447530614220806901707097182841114209042839897697147321148815046367620771589024116388606578702883143181008990896766466348901162595112838012768179898379272540531185894718935283059491243160599812939061700628648090146449800171778383527896386709921034379445027411802470097269217661302163364757977112018260870700413942713090760785694478453023051874115350553661810946528211503096476241522166725773089294494883007561732858752410233072288635504861044426459380806154142259565635096615291047530321001179237368195551945161510774296817381738478834668793627762884824744107001790130705206456321611527072785458058386656171841783283079254920152265902008156065481037182307117628871546722067989964550142796898091922281173993887885943414538122625393225365356834513640834479825410961094544504378267
Miller-Rabin pseudoprime for first 200 primes - 5 hours
D, P1, K2, K3 = 17200311933401204143114537735913751876646554205919606149595894402613516093901955630877083502012810711630700617549546709505138428819063464806620389981456203011644717861346549334927838631340154226824349424067786775315461094886367547888512209208816859615624839019714617394350161237146288007853780813596876087476182430055957149362518154453871016830965562455764486002268816023849962353925664803384185465483369126203382492389680061124207973131227039933132444825547494444218065763833503053265789406320606264143000203183356477080, 3331583297144207488262873516467830218985924616249217752512332623807581641849198865452945479223342669598328157704628378889592701637660018419441789256199596918978343273829623753932911481150958653002082197377658858445718117918991010252179548699572749436131982279009984926584844357812628549617140704643572092133934765203825493164238917485845484333219048612276143088419961476168329622462425219577001093844620861537699989936384963205899870388734638750839482885861172039092730742745792187956606873550446330832935350111560233187707, 4177, 2081 # 200 bases
i = 2562536
P = 44079750123867332267568417945153949909193340353236653081913377191519436658844990973390690994393123252408887365850649855167349001533925274870117229450777052237566987072817370770282576806481024410442563157950347710928226130363651741706288702085824292921420944464502426784175069620349712915043213211655928033789000554351076035191994060359090665470288387601757179045398342699968555460201719807824474087071735408046248658508217570076189302506190748640840322116365035395147878100933595372291459528988731540022780104014777133583862587
Q = 184121116267393846881633281756908048770700582655469499923152176528976686923995527295852916283580075825311922527158164445034016779407205873132479667415895747196317305003158157707470323320671238962418586310758602388547200546528973325107167908612488071532775285028226636677499265804200750846135501585086811397136655315524444598996959190119921709669394595012539736872628877457768656157262583637282828261698638799409180646588824790208242716568358757072790025480056752845532686827599627870061426452585931642675152494469724086979794021723
R = 91729960007767918448809877743865369761031341275085475063461737935551947687056426215626027959332089488262894608335202348603253272192098497004713954487067045706376900098532948572958042334287011798130973931694673586441638577286759274490786789040600353569476985430629550137868319879947752576204926693455986238314910153604589229234539639607267674843670134599256689593473951158634563912679778920082730575196281384144243458355600763328549938515382947921588710324155638657302734328042811969738527279825550334787405396454751214988018041467
100.00% 744481529345852753070123825977979466391706411383282995989834377263226589509482057414516645244922434228291378091261713247708000760971590514908865791546302764026055786350635816199760049472584371652543545731522858891404996717429638664505291381403214441125344194255994669756364228134322881768401410524121530304586827029116472204840821307988211802770113119063366611673220306501994985268136122118545077859717968752294888992215185683016537446569803174222462849135915008616747228184552730575404412408417008246140581992827510403343324797456075340997006389461922850054998637750041168004315124788720033445267176833496978582963493652607159974552197354653086741039856830900242942857177890114755368611080098296666340250598911588377510415828810912354397069914013861602516954912695571038390062764657684291189204888777246978774855758349374609686397956828632214369637758230561952903718758717316643193035669106298374378347646197261052891308274328517871607707638424303157101004891484739845157761551845192431539939827159174576679556485246335300927319856143357850128179286574406774927765638965481814188369190709131489487813439039278482942716429305990821603156296550488831966444205232591740196708645476726264601439914115536178636543793793680872519390376730226688655878855435160215558128557731509649512614575899161651112634690598315371549963925026952211709531180782628631420997105213722525239040500852051584219749796892003745873378515637875031051931601686570219778349426589557641046965734942945686229507069963658824980697467098920533895698789779865772111805316222261553194460255301379229349303398247260055887267
Miller-Rabin pseudoprime for first 311 primes - 20 hours
D, P1, K2, K3 = 2903334900920497107157352051974397758929400628889766141990740045074490277418686136756612233375271134548426263070675012672050852065661266469320575873093629860918659642735689916918213855776107557517623546129896173392900954907298528534486136345926008904479988351298416466444574506310203520543810516889496678344774453049703492832774732318349336806719093250972459541669761082617109836792695107444826710483326867584431844456518914998221490508926698337052463377746826794610398911328334911575191205944042042944311030847233562450835379595296712591515461818208763673189382400758589698538910159783832001609038684105311510103523080614791383380923554533545527869571703319047599699683813075682037884640233818061303040619519572100995757622806819872963455715180487038621170671206187939910398315384957764845168158377873614142153179829843635142167502074968220842814445937691812640822079174064680, 2440030577176129390870911122445066662739070661186677846069755743422925521230771432335781266006749611007898543561431693511661810242577227001339103313006317133313123616524971080005359434456618563376771190698072566345860280765963726249341573984019152015915228912857350337086414892763592380415227485461726252003444758223376187598893805049737629404219942695086813312453805752943401080076836101378633250966494333329218841416292480791679406497315047522024894045784981729096048842103569744041381740066655167217132096551294406696963125060039850495050864779438887606959797045887915782791531635685480457007402997446516784813498031091972767895204475337787880543317496002389255568044506365125979979319189176172961959341058588169903636731399948632216346851872530283233915933333202934556512258628822274671049442493496380618093327214845331139554316172248480628640184434757171846633546235080242907, 4177, 2081 # 311 bases
i = 3017691
P = 8763807631070851965185647782197117414204160983856173956636248073104306565275103158147533708412462074897582896775569781358845469631119990100071817030364795305758804059563231812154847048085314409916291687734970585948542535795926567598011344849857822888985035756730927035378680901414507964493787330008243847022924208756236159177627708549541666167009167174315419220073416796916852201580861727581665194036107632701060935971253313600689687321870832278960210156901984478383745349967417877390291707196548831781878031084970390712520830611370571767497936354431661145317500363373477221756373870623917257224588958673888113020624166694622397274057786679227325422799020456562459440906590070533130566117191019835404595909499695641195892453256935017895179987450591642346993059896205693510706315010977404628051394465977300914866464721115514506942145820285173804002208360593900951741654471097498496787
Q = 36606424474982948658580450786237359439130780429567238616869608201356688523154105891582248300038854086847203759831554976735897526649188198647999979735833749992154524556795619279370796119852358290220350379668972137507062172019585272856893387437856126207290494355865082226776750125208399767690549677444434549014754419974798436884950938611435539579597291287115506082246661960721691646003259436108615515488821581792331529551925090910080823943454466429216797825379589166208904326813904473859248460959984470352904535841921322006199509463694878272838880152461048603991199017811014355276373657596102383427108080380830648087147144283437753413739374959132538291031508447061393084666826724616886374671506889852484997113980228693275242777254217569748166807581121290083390011186451181794220277800852619131370674684387185921397223140099504095497343091331170979317224322200724275424890725774251221075123
R = 18237483680258442939551333034752201338958859007404698003760032240130061962337489672105017647206333577861870008189960715007757422302360699398249451240189139031284071247951085401094236707065539287035803002176473789358917016991323187171461608632554129431977859409757059160623034955843591074111571433747155445654705278421727447248643261491596207293546076889750387396972780354383969431489773255097445268789139983650907807756178145603035239316813201972516197336513029699516574073282196602849197042676018118938088182687823383072755848502262159848163205553572286843405718256180206098475014024768371812284369623000361163195918890891509208727314254079472064204844761570106478096526613936779444708089874512277476964087668866629328652195227681772239869553884681207724092557644004048195779841537843979030974951883698763203837113084641385688946605452013446686128595598395907880574382954353894371811667
100.00% 5850797453080941400653678824264622701126524955411214056119329867806939007774506007776020892533112875262786114786818512784084894270341021346067839029684598352493757700480909031058713961427870493806070115219708941881975805977746331123655396670012658345726824203396520965362090617451842636983102278850593102400129299381167748741794854555794514740327886342115005135512604623503289202325446050602904259518509271546353824416648964531601179233310434413817634522664204084419834763787442217412813710975439548484704664549494746504206126854629724284659034715361923390817968183114430697159028974527438444420675325469233939340448084417309702534207156216408677453907378575052873120200775640747033664983954989380102582960746779972979546468831629180687142863864915675787515698868531430994470780056007358195229392891834291612840944727131790019972587545176058445393871575221253968160307175662272614939428362964798621201908283600227425067622379841784688742002584396668156394465338611382204502926795517894551552862682940781378918014690462018200676234123867105312199529332642695221366479748757370850474165127779888249613861127691466337705299784157335744307987884889172520519227364049556648332779512809738628028754434197875651430400246044884191277481420229124018936086995009944507237484021307867499995359192315418939671378779943473952080377910425589518866559903062424628610419058385237198379955799887868909238179334779546212262288990122417901059739727025374445404880032389298297364912078870435550673982187548617076769873510713253094879547615429581904625251313588070459739361551464578963838617502458034406296007231002239291787390430518041015857206316459462850065841493807354947887091621281258440899461347100471740977026010421811808405684898096368031471104139674349278302356999359976247433991946043382686160912010851608731573358718893580503251714197859234976681608525262847859036167651214842583188142189281697404133004077081426702693833807279071493671341061457996558139730172146855597742706647807271614058600278779438211425049750996739852243057676480549096856773906260057270449309344307876079199610172051216728121842610144979350416256460160868642605154238600442743452079758553483264274048368946358584935742236380670011145119387200446012936902389941965007780859522383612905796927804013220039743831866023380247339233003823453140744229188817190747381955623282109166465240796608132487834224897287431731165007624971453449479587807396656891822914207566223017200475409928628051687644290705807435216047147720670387448289473744472515735093081378209419382027393859570071946257266470329591797790227339326682673129777464514371244246630744093080419461740868223853308912398762985909902693188267