-
Notifications
You must be signed in to change notification settings - Fork 2
/
e_prime.c
310 lines (301 loc) · 21.8 KB
/
e_prime.c
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "weecrypt.h"
const char *e_string =
"271828182845904523536028747135266249775724709369995957496696762772407663035354"
"759457138217852516642742746639193200305992181741359662904357290033429526059563"
"073813232862794349076323382988075319525101901157383418793070215408914993488416"
"750924476146066808226480016847741185374234544243710753907774499206955170276183"
"860626133138458300075204493382656029760673711320070932870912744374704723069697"
"720931014169283681902551510865746377211125238978442505695369677078544996996794"
"686445490598793163688923009879312773617821542499922957635148220826989519366803"
"318252886939849646510582093923982948879332036250944311730123819706841614039701"
"983767932068328237646480429531180232878250981945581530175671736133206981125099"
"618188159304169035159888851934580727386673858942287922849989208680582574927961"
"048419844436346324496848756023362482704197862320900216099023530436994184914631"
"409343173814364054625315209618369088870701676839642437814059271456354906130310"
"720851038375051011574770417189861068739696552126715468895703503540212340784981"
"933432106817012100562788023519303322474501585390473041995777709350366041699732"
"972508868769664035557071622684471625607988265178713419512466520103059212366771"
"943252786753985589448969709640975459185695638023637016211204774272283648961342"
"251644507818244235294863637214174023889344124796357437026375529444833799801612"
"549227850925778256209262264832627793338656648162772516401910590049164499828931"
"505660472580277863186415519565324425869829469593080191529872117255634754639644"
"791014590409058629849679128740687050489585867174798546677575732056812884592054"
"133405392200011378630094556068816674001698420558040336379537645203040243225661"
"352783695117788386387443966253224985065499588623428189970773327617178392803494"
"650143455889707194258639877275471096295374152111513683506275260232648472870392"
"076431005958411661205452970302364725492966693811513732275364509888903136020572"
"481765851180630364428123149655070475102544650117272115551948668508003685322818"
"315219600373562527944951582841882947876108526398139559900673764829224437528718"
"462457803619298197139914756448826260390338144182326251509748279877799643730899"
"703888677822713836057729788241256119071766394650706330452795466185509666618566"
"470971134447401607046262156807174818778443714369882185596709591025968620023537"
"185887485696522000503117343920732113908032936344797273559552773490717837934216"
"370120500545132638354400018632399149070547977805669785335804896690629511943247"
"309958765523681285904138324116072260299833053537087613893963917795745401613722"
"361878936526053815584158718692553860616477983402543512843961294603529133259427"
"949043372990857315802909586313826832914771163963370924003168945863606064584592"
"512699465572483918656420975268508230754425459937691704197778008536273094171016"
"343490769642372229435236612557250881477922315197477806056967253801718077636034"
"624592787784658506560507808442115296975218908740196609066518035165017925046195"
"013665854366327125496399085491442000145747608193022120660243300964127048943903"
"971771951806990869986066365832322787093765022601492910115171776359446020232493"
"002804018677239102880978666056511832600436885088171572386698422422010249505518"
"816948032210025154264946398128736776589276881635983124778865201411741109136011"
"649950766290779436460058519419985601626479076153210387275571269925182756879893"
"027617611461625493564959037980458381823233686120162437365698467037858533052758"
"333379399075216606923805336988795651372855938834998947074161815501253970646481"
"719467083481972144888987906765037959036696724949925452790337296361626589760394"
"985767413973594410237443297093554779826296145914429364514286171585873397467918"
"975712119561873857836447584484235555810500256114923915188930994634284139360803"
"830916628188115037152849670597416256282360921680751501777253874025642534708790"
"891372917228286115159156837252416307722544063378759310598267609442032619242853"
"170187817729602354130606721360460003896610936470951414171857770141806064436368"
"154644400533160877831431744408119494229755993140118886833148328027065538330046"
"932901157441475631399972217038046170928945790962716622607407187499753592127560"
"844147378233032703301682371936480021732857349359475643341299430248502357322145"
"978432826414216848787216733670106150942434569844018733128101079451272237378861"
"260581656680537143961278887325273738903928905068653241380627960259303877276977"
"837928684093253658807339884572187460210053114833513238500478271693762180049047"
"955979592905916554705057775143081751126989851884087185640260353055837378324229"
"241856256442550226721559802740126179719280471396006891638286652770097527670697"
"770364392602243728418408832518487704726384403795301669054659374616193238403638"
"931313643271376888410268112198912752230562567562547017250863497653672886059667"
"527408686274079128565769963137897530346606166698042182677245605306607738996242"
"183408598820718646826232150802882863597468396543588566855037731312965879758105"
"012149162076567699506597153447634703208532156036748286083786568030730626576334"
"697742956346437167093971930608769634953288468336130388294310408002968738691170"
"666661468000151211434422560238744743252507693870777751932999421372772112588436"
"087158348356269616619805725266122067975406210620806498829184543953015299820925"
"030054982570433905535701686531205264956148572492573862069174036952135337325316"
"663454665885972866594511364413703313936721185695539521084584072443238355860631"
"068069649248512326326995146035960372972531983684233639046321367101161928217111"
"502828016044880588023820319814930963695967358327420249882456849412738605664913"
"525267060462344505492275811517093149218795927180019409688669868370373022004753"
"143381810927080300172059355305207007060722339994639905713115870996357773590271"
"962850611465148375262095653467132900259943976631145459026858989791158370934193"
"704411551219201171648805669459381311838437656206278463104903462939500294583411"
"648241149697583260118007316994373935069662957124102732391387417549230718624545"
"432220395527352952402459038057445028922468862853365422138157221311632881120521"
"464898051800920247193917105553901139433166815158288436876069611025051710073927"
"623855533862725535388309606716446623709226468096712540618695021431762116681400"
"975952814939072226011126811531083873176173232352636058381731510345957365382235"
"349929358228368510078108846343499835184044517042701893819942434100905753762577"
"675711180900881641833192019626234162881665213747173254777277834887743665188287"
"521566857195063719365653903894493664217640031215278702223664636357555035655769"
"488865495002708539236171055021311474137441061344455441921013361729962856948991"
"933691847294785807291560885103967819594298331864807560836795514966364489655929"
"481878517840387733262470519450504198477420141839477312028158868457072905440575"
"106012852580565947030468363445926525521370080687520095934536073162261187281739"
"280746230946853678231060979215993600199462379934342106878134973469592464697525"
"062469586169091785739765951993929939955675427146549104568607020990126068187049"
"841780791739240719459963230602547079017745275131868099822847308607665368668555"
"164677029113368275631072233467261137054907953658345386371962358563126183871567"
"741187385277229225947433737856955384562468010139057278710165129666367644518724"
"656537304024436841408144887329578473484900030194778880204603246608428753518483"
"649591950828883232065221281041904480472479492913422849519700226013104300624107"
"179715027934332634079959605314460532304885289729176598760166678119379323724538"
"572096075822771784833616135826128962261181294559274627671377944875867536575448"
"614076119311259585126557597345730153336426307679854433857617153334623252705720"
"053039882894990342595662329757824887350292591668258944568946559926584547626945"
"287805165017206747854178879822768065366506419109734345288783386217261562695826"
"544782056729877564263253215942944180399432170000905426507630955884658951717091"
"476074371368933194690909819045012903070995662266203031826493657336984195557769"
"637876249188528656866076005660256054457113372868402055744160308370523122425872"
"234388541231794813885500756893811249353863186352870837998456926199817945233640"
"874295911807474534195514203517261842008455091708456823682008977394558426792142"
"734775608796442792027083121501564063413416171664480698154837644915739001212170"
"415478725919989438253649505147713793991472052195290793961376211072384942906163"
"576045962312535060685376514231153496656837151166042207963944666211632551577290"
"709784731562782775987881364919512574833287937715714590910648416426783099497236"
"744201758622694021594079244805412553604313179926967391575424192966073123937635"
"421392306178767539587114361040894099660894714183406983629936753626215452472984"
"642137528910798843813060955526227208375186298370667872244301957937937860721072"
"542772890717328548743743557819665117166183308811291202452040486822000723440350"
"254482028342541878846536025915064452716577000445210977355858976226554849416217"
"149895323834216001140629507184904277892585527430352213968356790180764060421383"
"073087744601708426882722611771808426643336517800021719034492342642662922614560"
"043373838683355553434530042648184739892156270860956506293404052649432442614456"
"659212912256488935696550091543064261342526684725949143142393988454324863274618"
"428466559853323122104662598901417121034460842716166190012571958707932175696985"
"440133976220967494541854071184464339469901626983516078489245140589409463952678"
"073545797003070511636825194877011897640028276484141605872061841852971891540196"
"882532893091496653457535714273184820163846448324990378860690080727093276731275"
"819665639411489617168329804551397295066876047409154204284299935410258291135022"
"416907694316685742425225090269390348148564513030699251995904363840284292674125"
"734224477655841778861717372654620854982944989467873509295816526320722589923687"
"684570178230380965678831122893058091405726108658848458731016581511675333276748"
"870148291674197015125597825727074064318086014281490241467804723275976842696339"
"357735429301867394397163886117642090040686633988568416810038723892144831760701"
"166845038872123643670433140911557332801829779887365909166596124020217785588548"
"761761619893707943800566633648843650891448055710397652146960276625835990519870"
"423001794655367885674302859746001437854832370687011900784994049309189191816493"
"272597740300748796814848823429320230121280323274603922196875283405169069741942"
"576146739781107154641862733690915849731850111839604825335187484389231772926135"
"430249325628963713619772854566229244616444972845978677115741256703078718851093"
"363444801496752406185365695320741705334867827548278154155619669110551014727990"
"403868972204655508331707823948087859905019475631089841241446728218654599715966"
"390156419417518209359326163168883801327587526014605076760983926257264111201352"
"885913178482994756824725648855333572797722055435681263025357482165854140008053"
"148206971372621497555760518904816223767904149267426000710459226953148351881374"
"638871042735447676235779339939706323966049691453032738878745579059349377723201"
"429548033450006952569809352828877837106705855677494813738586303857628230406940"
"056653405848875270053088324591821834943180498341996399814587734358631159405704"
"436835152853836094429559643606760902217418968835481316439974377641583652422346"
"426195973904554506806952328507518687194490647677918867203064186307510535121498"
"510512073138466487175475183829799901893177515506399810164664145921024068382946"
"032085355540581471592732206775676692136640815059008069525406106285364082932766"
"219319399338616238360691117677854482361293268581999652392754884274354144028845"
"364555951247355461394031549520973970518962401579768326394506332304521926450496"
"517354667756992957189896904709027302885449454166997919929480382549802859460290"
"527631455803165140662291712234293758061439934849143621079935767373179489642524"
"888137204355792875113858569733819760835244232404667780209483996399466848337747"
"067254836188482730006483191638260221105552212467333231844630055044818499169966"
"220877461402161570210296033185887273332987793525701823938612440268683395558706"
"077581699543984695685406711744449324795195721594196458637361269155264575747869"
"859642421765928968623835063704339398116713975447362286255068036826641355414480"
"489977213731741191999700172939073033508690209225191244473932783761563218108428"
"982077069741387070532661176836986477417871802027294129823108887968318808543673"
"278068797716591116542244538066258617117294980382488799865040615639756299369628"
"093581897614910171453435566595427570641944088338168411111662007597872441370823"
"339178861147082286575310785366746950184621407364939173662549377830140743026684"
"221503351177364718538723240404210379077502660201148149354822289166636407824501"
"668153412135052785785393326061102498022730936367402135153864316930152674605360"
"643517321547010914406508788236367642368311873909374642326090216463656275539768"
"340194829327957506243996452725786244003759834220508089351290231224759706441056"
"783618708771723335554654825989068612014101072224659040085537982352538851716235"
"182565184822031252149507003783004112162121260527260599443204430562745229161288"
"917668141606391312359753503903200775295873924124764518508091639114592960711563"
"442043471335447209811784614510778723991406062902282766643092649005922498102910"
"687594345338583303911787475759770659535709796400122240921990311582292596679131"
"539915614380701292607801970225896629233681543124994122594600233994722281710566"
"039318772268004938331489803385489094686851307892920642428191747958661999444111"
"962087304980643850068526202584328420855823385669366498497208170461353761635840"
"153428406741185875815465145982702286766718553093119233401912861706133648731831"
"975608125694600894029530944291195902959685639230376899763274622839007354571445"
"964141082292859222393328362101928229372435902830038844457013837716320565183519"
"701001157220109569978904849644534346121292249647323561263219511557015658244276"
"615993264631558066720531275969485380573642083849188870951760522878173394627476"
"446568589009362661233111529108160415241002141959373497864316615567327027921095"
"935430555797326605546779635520053783046195406369718429161685827341222171458858"
"708142740902481854464217748769250933287856706746773812267528316535592452045780"
"705413525769032535227389638474956462559403789249250076243868937764753101023237"
"467337714745816255306980324990336764554303052745615129612145859444321507490514"
"914539509810013887379263799648737283964168975551322759620118382486507469854920"
"380976919326064376087432093856028156428497565493079097338541855835157894098140"
"076918923890630905425348838968317629041202129491671958119357912031625143440965"
"031328352167280213724159473440954983161383225054867081722214751384251667904454"
"166173032008203309028954888085167972584958134071321805339888281393460498505323"
"404725950972143314925866042485114058195797115641914588428330005256847768743059"
"163904943068713431187961896374755033628209399493436903210319768981120555953694"
"654247041733238953940460353253967583543953505167202616479613477909123279952649"
"290451511483079233693821660107028726519381438448445326395173941101311525027504"
"657493430637665418661289152644469262228843662994627324679587363835019371427864"
"713980540382155134632237020715331348870831741465914924063594930209211220526103"
"123906829413456967859585183934913823408842743124190991528708043328091329930789"
"368671274139228900330699958759218152976124824091169515877899640903525773459382"
"482320530555672380950222667904396142318529919891810655544124772045085102100715"
"223523427925312669301082706339423217625700763231391593497099469332410139087791"
"616512268044148097656189797350431513960669132583790337486208366954750832803187"
"867077511775256639634792592197335779495554986552141933981702686399873883470102"
"552620523123172152540625716367712700107609122815283265089843595689759610383721"
"577268311707345522501941217015413187936518185020208773269061335921820007623272"
"695032838273912438281981708711681089511878967467070733778695925655427133400523"
"267060400043488434329027603604980278621607494696549892104744439278719345367017"
"986739208038456337233119838558626380085163455971944419943446247611238446176157"
"362420159350785208256006041015568898995017325543372980735616998611019084720966"
"007083202805699170425901038769286583365577287586842504926903709342620280223998"
"618034002113207421986429173836791762328264446457563303365567773748086441099691"
"418277742534170109884358531893391759345115740238472929090154685591637926961968"
"410006765983997449720472878818312002333832980305678654808714764645128242644782"
"166442666167320960125647945148271256713266970673671446177956437523917429285039"
"870225837340698523091904649672602434112703456111141498357839017934997137909136"
"967064976371272484666132799082543054492955285949327938183416078270913266808656"
"559211027337467001325834287152408356615221655749984312362782871066494015646701"
"419437138238634547296069786933359731095371264994162826564637084905801515382053"
"383265112895049385664687529211359322202656818564182608275387900024079158926460"
"284908949222999661674377313477761341509652624483327093438984120569261451088578"
"122491396169125342029181398986839013357958576244351940089439551805547465540000"
"517662402028259448288338118863817495942848920135200909510078649418682560092739"
"776675856425983785874977766695633501707485790272487013702642032839657563480108"
"183561823721770822364231865915958836694873224117265044872683923284530109916775"
"183768315998212632371238543573126812024451754018521326637405388029012497281808"
"950215531006735981844304291052884593230647255904423559605519788393259303395729"
"346630551604309237856772292935372084166931345752840118737468546916206489911647"
"269094289829710656068018058078436004618662235628745913851859044162506632222495"
"614487244138138497637971026760208455318241119639279410696194654264800067617276"
"181156300636443211162248373791056236113588363345501022861705178904405704195778"
"598333484633179219044946529230214692597565663899658937477287513933771055698024"
"557574361905017724662145875923744186575300649980566883769642298255011950658378"
"431252321353093712352439691496623101103282435700657814876772991609411539540633"
"627524237129355499267134850315782388995675452879155784204831057493300601979582"
"077395585228073070489509362355507698378819263571417793387502163443910141875767"
"119389144162771096028594158097199134293132951459243736364564730350373745385034"
"892861131416380947523017450887848856457412750033533034161380965600431058605483"
"557739466250332300343415878146346021692350792161110131489482818953910289168163"
"287093097131841398154276788180676286509780857182621170031400033773015815363341"
"490932370347036375133545376345210503709954529420552320788174493709376770560093"
"063536455109134816273782049856570556087842119640399723445564586076895155696868"
"993848964391952252323097033010372772277108705649129661210614940727824420334140"
"574414464599682369661188784116562903551178399440709617725671649197901681952345"
"238074462998776648248737533130181427639105192346850819790017965199070504908652"
"374428416527766114253515386651627813160909648028012344933724278669308948279134"
"654439319652541548294945778757585994820991818245224493120777682508307682823350"
"015970404191995605097053646964731424484538258881126027539095488526397086523390"
"529418296918023571205453282318092703564917433719320806287313035896405708737799"
"678451747405153174013848780828810060463889367116404777559854812639075047472950"
"126094199903737212462016770305177903529527931687663050998374418598034988212393"
"409198050551038215398276772913731380067153392401269545863764220650978108529076"
"390797278413017645532475270737887640693664200121947457023582954813657818098679"
"440202202808226379570067553935758080863189320758644442066446916493344676981808"
"117165686652133896861735924509208014653125297779661371986959164518694323242464"
"044016723819780207283944182645021831314833660193848919723178171543721921039466"
"384737156302267018013435159304428538489418256788707212385205972638592249347636"
"231221881137063075069182601096890692514171425142181534915321290777237485066354"
"891708928507602343517682183550088296474106558148820492395337022705367056307503"
"174997881870099892510201780156010422778362836443237297799299351609258845157720"
"552328969783331264276712910939931037734259105923032776526676418748424410765644"
"477670977903923249584163485277351719810646738371427429744689923204069325060628"
"344689375430167878153206160090576934049061461766070943801109154432619290007452"
"098959592011594123241022748454826054043618718363302689928586235821456438796952"
"102352666733724344230915771832775658002119282703910423919664269111553335945696"
"857828170203254955525288754644660746202947661160044355516047350442921279163587"
"484735015902155221203882811680214138658651684645699648100156337412550984797301"
"386562754601612792463597836614801638716027944054827101962907745436280926125675"
"071817736417497632544367735036325800040429199069631173977878750815602273688249"
"670776355598692849016287686996280537901818481488108339469000163807910759607455"
"046889126867928123911488800367207297308013544313253477130941867171786075229813"
"735391267728125939582205242899913716906856504215750567299912741771492796088315"
"02358697816190894908487717722503860872618384947";
#define NDIGITS 10
int
main(void)
{
mp_digit *n;
mp_size len;
char buf[NDIGITS+1];
int i, e_len = strlen(e_string);
for (i=0; i<e_len-NDIGITS; i++) {
memcpy(buf, &e_string[i], NDIGITS);
buf[NDIGITS] = 0;
n = mp_from_str(buf, 10, &len);
if (n == 0 || len == 0 || (len == 1 && n[0]<=2)) {
printf("Invalid number \"%s\"\n", buf);
exit(1);
}
if (mp_sieve(n, len) != 0)
continue;
if (len == 1 && n[0] <= 2) {
continue;
} else {
/* Now run 20 rounds of the Rabin-Miller test. */
if (!mp_composite(n, len, 20)) {
mp_print_dec(n, len);
printf(" is prime with high probability (offset %d).\n", i);
}
}
}
return 0;
}