[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:	Mathematics at DEC

Moderator:	RUSURE::EDP

Created:	Mon Feb 03 1986
Last Modified:	Fri Jun 06 1997
Last Successful Update:	Fri Jun 06 1997
Number of topics:	2083
Total number of notes:	14613

2.0. "29th Mersenne Prime" by HARE::STAN () Fri Jan 20 1984 23:11

From:	NOVA::KLEIN          10-NOV-1983 12:58  
To:	TURTLE::STAN
Subj:	prime number

2**132049 - 1 is the 29th Mersenne prime, following 2**86243 - 1.  It was
found by a group in Chippewa Falls, Wis., using a CRAY XMP computer.

>From the Chicago Tribune - Sunday, October 9, 1983.

-steve-

T.R	Title	User	Personal Name	Date	Lines
2.1		AURORA::HALLYB		`Wed Feb 01 1984 20:45`	533
	For those of you wanting to know what this number looks like, here follows a 500+ line printout. What's the longest repeated sequence of digits? 132049 2 - 1, a large prime number 51274027626932072381278576362034022188004658622706992683124038418582312743056 20361077749499092908732125557093200451596185805491533791569813459934004301403 42096387650305139593110201531492353980427458239674399280795047471922595649354 97551137310842558681977969184345819375982377194496938307582955585279884344839 84402926845375042397676916772484150646410917772519028191260065794740179769324 69836772698386215118970395984248890006127207602445911234087810954645734649155 41439258426851459490230675515467717759547932604327529454818060988029290009074 27445042956652440017686821739642342283937834042844291309099347969102747457019 19014196486248736912528723230412018067171830057434251357669941185777431339506 72876530748505883249371034082824131952564383837872072789637642175859892976521 30376043003743753738855745090992464814545996050643193581313404735505484589430 72309379882335985627252266833638525995267775655285655128900989292858535181799 75970304985148888963978533511071172987974410341944775593043721090972907247709 47530415951652971238902317815917038680603767679621050951143780665933783692044 96656507352878526703089545090220941654908751575549709553931290430952265766257 33799102373336678490798492204238407628849737395002001272989749348300668403931 58838988914961956695510930546945980827951096112962664643335992487280560134900 88667976418119058452753559630999310334402928242536463995315666354468210745480 49312562389555331134960188168541821955433305310809063234450783162509673489396 38518364397769154256659856173480003883657206670525805339385205102031809817585 31484060297268201941884623865528516400475214581257462934749614718786025583639 95477125722717636522259007245477824846352895474264518057593855992669738897957 34232290479220332115891609768156288342457935909120914007323909196438381794326 45676829349050764518804913985649069585592134723966710605859973040307047589776 17773848764284505873458199930077197245396990980555416797298736555045767090099 05603259030920627958993042266397424051597783360050334896922727141271478699045 08215222802717638724225892679553679746808513452862510697609534519157791347637 10284106467420376740516284558780002163772653974520840152408670908688672217535 97264076182115949014522094557935332115678514099817970329091688526234719385466 55949465337353789900332316610714947887711700639274293231455929008483577709466 76060297804589340363869760392747812685558449955126149644399329249403128483336 45844887797516295800024064774185402159078978805168601770447303316431713617130 23479435054186679280689300340068920296317647026335202306208973087652704323046 30148791445219526612177036777994411876576629733847379664025810387479610459956 95691052348543766640499372261445442597160606259053966068732511151005174297931 07247644207065472572899731246860699749626280695741775474611675161188860784752 01182386959886056320057650401164524830037382221088831826454009277483759918513 16480041378139797501430225910917778283739088610331481527007155171810533856350 04661051904375976373528760831772075829204364783609033658069016057030546867332 79080887693468206442022223708055677899246525337102830136231615215664524349520 81959455776793645596433449191241875779804568888134130384052737038581482023245 95772710277426979026848362339784987730766556636007764242468643152136233153553 86252361472070104777264527146085766392169295136684084526256077063538835329508 70370035801874995812813451432008448947266393601762979801361580687909591815579 38947776683475325194028755780106655172267797996314841246693694228087327759571 96907713252148567888114240357934339633989933310311194413838829553893901516574 76397193836314471258409404667849604708290823276044211968110911567811341262080 36077879086594755139574481707058382406115009844503283519791740729869126101337 88986535793215220786403680480709845010867943950423307823903967518454715250309 20057416168578236420486622426378767586883883893489433813011353455573101221128 38440654574139403358109443763176941213029466172410617518112539805002769511299 34300236303236754909929394965047448055786354721797883337682006648196072843409 17322755531869709230020828192538563016722363953568715031024807326998142181473 13579811661912530867291253025668319905148059685561912264425168681223252113340 26196692225856684659069111368325725145620092743928809735843737983615474064794 32084329403349301000394827230213855184882751071528067261670154680072053788815 28274741057473745370363756363057043511762819597857385944173902131463960919457 06174683809643129848980510158085312495201739814518791649994147436757498042347 74729611723419052649393703587908248649035483760388377673954593219972520460512 64813503749364171662302650756694856817761250109927767584201977333309089492382 91001100763098679691510810525889826079518654712133131832450605970022726931102 45785965527572016217588182180611542407587567815731154265933832507231884099577 59149014505857436343085513236956174404714976093532604663308059617255408726879 80008466913099700431557019057330404465499216307165577148578514352957382447397 11179222259227248795100488126594739221835603749600314934633344076353028287578 58602459883912682206971310175059847467081275869329265916182802616695034674881 51434633347045421767845214353886728175786192784946722288064651263689456251820 69538753150748681827976974516834491919682447499595479376473830053931431014725 19553034501037426529933248910413241027197778010217644083462544601286666534719 44850144981922139067124615715584618562155440942433157785525120021409506708252 41426485599659881554353612591403867412422460776539555531219070870630305526323 46772477307011965281113493563828974629279822937885688836313494092670811488061 95991163945788190440205324689815218191760252070147491618382883231494902585238 75175248280151699750221467024407911729970497221734109043858511965549018877943 19831945958940173728033040751886263005158888161356956210884245900476019960540 38015983975654918236511483269014005206610661942410359825183450690967936189812 82457558427497482957008675010720183774437435785017575700492736626204612419206 70650771096163564217020527455047359751183667592542038136830901570993893589160 16213217600369164113116815161232978749759154801987030786634194588044028643055 16787820345985693428927205941604062174961545371679212308834552826121715932392 54010737957715436182681849113752952673804938390357565185510364232641363012113 91554841648882433775001634072330456224669768001242719449503192850794712096426 15721698927302762004348567984609484332582529312222882172855754718970819602949 19677252021446309459590035464995540978917531779217326996789002914227120549444 93452178736712822956125877293051039999799297434815793690706225158271102270433 11618627937047489237015082734016466143123088742374780178674664214517749524379 31126958323824927651523113575921828576605467781544008285836245203135652232261 94649719087517413999205174853559311542767604530826514399383245576596787598613 25499804190722614943694407186007001553845676121681900718551500159385916394847 10520905063576672822902671715968653660591184364916536576688352482756488117786 42417645810291324881290765075275121095034491584384538417192821385581625212993 27913862781561956545791246753034127861941934167249886926595445327450131322517 71377017949044430991794917425763599027261893744959578381869309546641762568516 10644353269993911060158995112350372073384659503932197116498164562569866569532 06680202126257859098323891799580888242623952863477848461113235288921659445319 44474653937217471426655192601108678496308672788660004914156617796085138854279 11841570274366347658102582451678820575846258269462205984150980310067287310570 36482791782676668744498636690294917146323352239119119476127803088758287801924 08075910690302812873303262099843699141522737208390700114038662514477647333461 65374978116273513171617667541527556291835789659140576127788986163332536800769 89723132963096267843619665840738100891818504497613087480563689696696325338836 25775284876905955689515502338746727247121743855929727042244324085919329588596 49226129079925285163295238600224140771264681903501156757042629967129245557385 06087065654538334187094265197591237263839877125045316352683284056878031458951 84936271305086441633489719931521113185740898006988868166077768153814646485367 23073181574673359729186962623598776121912642994973068569287165071758806223928 42467165074998385165181483505794499544813906347343204942924289137256184514880 01827306643272627757718026074680077926993888191030732382060392938047952942187 60150494766913209866996959421158975684832082447919795199012403750005911950167 65017126144548505799030998701713970033915814767773118132358804291265033958409 75536912785395723196259014174346156953677974963423563979835361957245025884775 94596948469059944775251563392732469133467599567449901114963349818059052308020 41004715927427344647936927755876493290124167078164505345564766348558129462609 11651078222493722888015589272976941556247144576993114085539151137862436826354 01276866759115477083521098181756440390113697495658583728123006898540482470488 05169051527318082276479596762887555775088256570118179705331031761747334969615 95037736679831106106901561131879211865148063226939479627499260144552960191975 60157449468611110120228867141611611477739318687028698844908528607438288230273 19235368138865992343266288790246372010312873917433718997957513043906163604361 46506063438647474853758240073053015972294093982604819160542927012433698127577 03381389735776165939716218335823603179801442986655331159571417886007214702506 58181066937770192408683344698511389924513540955385986068357670703852792679139 16724930458368079664341635860044052007228086303808159215454427074703771549885 11684756075606111389639668889836562844491712333266312163774006608061205403864 44244638323057376171601637971899649659721093999368390685082260546366837300067 44340150758876000771122420387630232597730481803860371863000025584030255745949 51790755493635828403549877906433285027143681044352590860327846332199819507142 88365275795169344442417986953571445084667257645779903420686950035236373635997 79724178443364175239391413734195339275977143524991073234572914259291795906620 55352925984486877232491198890462844536891684762653640110339416472769719208393 64592580134373888421503390706541131854336458868715573463168468946708115745948 27281305529902659267559273143968012115395733700800764796835899807482538488574 86719590199834947380497798073779770511529648060914497941929725010839856749964 43156468519126946644957077909219434127902644367394435341912828719668752255166 98585255350736807448119941906762376736959121287347359420223204415617433147308 09679415948064725537075550123311137452127095897639553619191228820113046866769 10655457379868999971589191216488216541751852793814911404750535949300187484925 83743765180478561695901988130998405654880627045611645337040521943537254759594 26013651464415805380578554316201254474861247800998942306524482793967825652387 39301707121850930983800079628678351299301787704456611541537321343947537106101 35119319593634360293012299236074808775398199323308434441173322363918321977377 80740345593667856089895241816834424089538193245209069406373868584031980207016 62889681076874975308719004149166109223719368525619529510261110807516307297190 17584596211055563005298530265146251165672984922350414865049070685671163507488 83357015894783779732698193987399986607275696758116170424081027782536245332079 08630722333533136304860833953319141187521024046533785992713775724685202401271 07370808855671412180018324535229224165973839266430749554599777299542165804128 83212000935523758241417177318843436369976017174400172013774292091302142172691 81591888763203788884971870727424396746714711131361876200606993333760112725521 18262673727964646363102514554625518946509144235797649383700236195691925583445 22427033056967684561873044487900076176138445788496636168714751318502045905770 91027335977696875263844896997340942208281171440084942987470051070820569697809 93552840920658058160771620909064655407818161711497762908154009483982950144401 38945787738666860795973833701929853367617296087338786312385936353684174173748 81263553568889305307888189572488525337141762186719515574461226838677147108083 49166041382705275505058610608911693816006947766772315519937392530234037354987 41728423908547117848410492901968884191325847034526268660576923812479291486572 27857819802319538730633607454535685288705442980644771846584674510901124420706 90408927634310291673995013288833020949122073388950420566883052391942097661549 07475941503275610321109779235855579472973453307732775311844398917757237644064 64342485914416226166364694249554479287406623303522282581319216588937074375846 41196690551386003715332332276892948405008552491448409966307239614446627853434 98461225248399449316076236079289088679199310118938380003650366745855051577972 93416527639758415131263874026878221837674217823597295757639756335103814510257 67271579443438463305268784978938589257067741434573417503042284251944070250576 03077421904222756273472385434609002168796369969895564283601181119980854311237 74452854194395028445348594789007015764392608154412173386561671417077425392837 27463089645481718774828504838957431073008992903673744813477709587558557451642 20818782588374438677102219302718404464558498845157179832516477258769696369127 34850443435164346055033917516879631881271065620961264741404822095026362667332 68218587536459812521361676495367610112768116428806213342030958578999521918624 14707974233916342137018301086822371865264911468089902286329830112121262427391 70016294559949113413729541382740831559822863555356273751098038633680013128660 87185382018934236602455324831445116067781820302733454929123521656684759373540 71416818880754966341711175410752643906661541719151837681023095680857154660315 61760559193169183847770680748160024719617594042164298308850480956705556130577 08076463638911512285148859684079011146037061486110649185673168795717305663712 13079231373948127144679706567853031994803691062906850759644529232383173557919 32993212169480061725978070236115335240264266619442608348761729139966228197947 62141245812181826136653518748480187175860307895967347255085223925104941705600 72195348216813522414052783866732001326427699546048247533755253321710118272290 27485291404780578605204091710542469776515619500478949781826013371842116881908 95439188097780826689827143717122279940541122021512400619398113446542438638851 44791395779930947525539504907485059105545765690318919257710905011474975948189 27053935402002458054741587143409260726965960497642217918689714450184025085894 39556406769199720977379873583413054727088017728512121613184131409497141079131 57303687665395492978670181458890864724704188438020659101594364782962089441200 24165178018299849011692869626363429989884067672619117200954976010545718563777 17841190851739792397624492314410040321959943770411744046373410928109844891247 53407203407650849319511469718561317340356857531121069832026488007468213386422 98597351573168341944332049367210957576797292230250422788252297593130535812079 51351185779370674551071168896347395381501856323312820228098416855730204545151 40980258593473904390760589183758929507033526872366432450812824709385639037880 51753220214621017761154534219477943282771708164383363942150445814460815273018 85922404943477846383556452561473137915693526453405239910738974831722091772396 21870425856379026760997796813433155860419886545767975900057137776357477057660 48956047167864210244365611122529830187277258068103824913666385901198916611173 66225164595980499521905084522807155267307843953749065075568497283304567619367 25582100667744761318518913936481905011397765315368105150054420749164154688740 55835769896673562682217599658026991924624441652350908785301948627693734467992 77813788784441825962819924381472079926830577398668858067837878839684050663712 57234428345628089139214688346721945505814804708669768027696709178338914206663 55989549293274445922282980966757946143453996245344251567096725883299323244172 60273723987078934302827826870857598688309060999882465341590682029157338895375 43757590879226879486066077555818538295853117025358209878489007596397724760785 14212708117780908640744397057580907683989541620562196551875902368717453133782 32959671377921137155641241661055565078506263408511867220848865514774340615772 99231501583902492026967463296816477408997346461737254459782704034301771196972 66024540074986111456598238572170495974076889943809623971112960493513344390202 18164799629898531708656468757988277178545294817032337846855545497322950030142 98270269786680147863099705600257808059726588660284731078982643314843677376848 71316172119935309665901532295565911998796748977682150922965823378100567223289 11878576504181585823512834282473045100537004082155313461025914303446653137047 92290757891972251146997103997353698908038164846410953002090539371802514445104 66085026473928413349140845751190224484462062291833120232242119827413671527908 23470528488823204340939450478372812455199542741138225239834463840416138790229 01796401952594938204274399304369492329279134128960775302298850377452945214763 58038334182604126998658614415992797224390651531982694721302911841754380652121 29004198118219064180562179703875990315777735425015855047814062245135439342282 22285764760615654876465500517322310436012173179764671813573122275409683931875 61451253054789431744109734388447074377997628391442589712472842282496599855559 59405313145571678439188995823592455212430052389860796931774554563116043135376 64171642274187668933205322568667349176303262529182918389054550161915840201466 82530755163011902032819311309960095804246873510424584264096394699306670088013 29907654853879997303214599913684078273701164765720088829279258327539364450775 67944655109985383207027879508657457044355575817321800663586765873360010883080 72635841068793487992957731712602027373353956185468182032224148187974219776973 61576807519497524890721526034214761269973964039393543619055696912087815835720 78951008536139871101336844598994864356235037453877998662992111024980286391482 46432225992647405793335082423709256861876941610775317675133601150846659691926 74992324273839146971115911633638191543442459301418511483001735254194331161893 51417912239014222594278388159075394324776146923810229442873064811767146205590 09987830221259930624711672848003254859888710758406079962719178597728385829287 32845010535894245447132649685817150876095903721363373192620046692049572299421 22840280001907516105994898767283664328414139937136500413862867654324695037188 37950951571618882635770007155160313424849952286962952302904613085507681699282 13935944470594299559301979430957550896079514733706135905056554186510179307303 81448740127658959740040816705718800972670864900669323569374414088009217617389 15793270737169601644359173050007391399659705319944823320155135839490332700221 54771073857602172570013159700721111791554917343508436602993918772314095639838 00804277988987973529463864307872040279947443974028116047754511186114749102697 13051908084167669775944986011822680218291951261995876080342404819648137906879 68670761097234715094781489226037359700619505947836708861624505498654496906028 35626918367979993318425012334302920581585668393525748145186241038687138104397 50115467493230228612128575796307856946987822510338299271775422112471459416496 34082438009140657234735812767088362631616187098716883743768507152525005771556 69838069930210218499093561282733940721073056465000115438715153885891851882741 60422952303793732183481970154108997599287760243459465491906227204893657437131 03573414949514522121632867757513219433344650634566717663121559762097483469563 70417432051555487335881007937882472065627415967357710790533264889793480544456 99333806531340854298532422890121033686305427486377248424968995883123309583150 44761282564193651413648890877866276666582416261428510385177275769611763994450 18470507399161902143286218401902382460495087168536723757227575397681848515655 80349105881928023221584608563306808385742748297643746416576917013326835257160 06583339705413027401787041130246609884486409383564525258502680715345593950005 63767978622318356124187918832573368826765443769916988921300542807477427640526 13525727171592256114277216950416230082742613712666340597840453139536368149689 85091083006921343135575808655706500636177056408111116440695331842442741034414 01414603721525703053879615482181810716523651920243891785442833372906440901102 83717189809141306059691254328992864801660180750117065905723199839527715193240 84697782354400007535136844991145736948636580658504142180966230772733335294327 01274540146503251407468274564140649521536071618028460131284222577938017288562 10698051081608034556943203047881069109053166384829740583454965339080759855170 68534685648045898708859747163627180406106567892198659554841399165198394647932 63585513079948462611160569062070769217898337936410857699380669920971386602455 22369376362224530810707486604715910514835913440555702891614082341854686142785 06929653310932166122558372436782211616735588298141238035823220334400119817867 49601932271947558577981046062639835901331023473200159937293081699188310216691 77474017210922549809286899167718990197028764355130709168795292807275154892799 92824471886724631435984611306775965720902182574926521361847486948502723908849 64897792279670475512067574234738837083987953226898886475000080700757733970181 23204976257629745438133140435189863995238900348165010219457406111693593877160 31434034250329195031480395338390093376680511712387084956319797360770690486321 96061252896753532381088859707560719557190636453203898232776274509411182991497 36138057789438801615873813219580294061643754205701374228422493436724019602375 98654084602962680760165069701473207528150273374949282918912658099195096892082 94464297765549382164354436674461223035723808340088758063403872585620898756901 32134331844910322908793759539285036832837329602020159758375540313165102621792 85718486209856626962264823597449438889995513271550654805040651456386094838673 06606737329171954441229469386661264519814426765094686000353358301068546159342 06381258964326546632992670438836692311645980886579939856286384418158270062548 94291312055357360405801167322157555974406747378660203885095661302321350801071 21575773609489730186046884506189916632394378179652949940486080426942409871490 06834600971876727642863217693014151675544809258104365525453763570094549910041 52504438193099885100434727142692279509501874653252942669485874732422658689636 73684545102768295277008947630846020866705073050165875632106471566836422167637 49725214855616926217755354729722628921211227356488692447147114118683338122905 32724200773794788630796892218831092610007355338936288721113694098514890717563 96485352686019069044364408290580072838415988719517698000175616231405788173193 87968271309600971313614204008888997905484661557968388774162337359120890682582 55119688208260968264956086204174367634716248081962761614873765939692805453980 05707953243603731266970590798476819637091401793997150939419812973205441817020 00604656831768094383342026265342355112248052813792877679448920633195607207963 30265496144232565230838479388475908214325116765320164624664363714386231282840 06666819792138480059652925899067930987838835511130588423011405859580023202042 17922778391891207080626233962106893946358585168117675317289380934126349504615 30845247598000244481558476611708831452255226478891735504664244603400598291116 48528652601307587215671956630650618928619988402804520359675383285145471984626 42647107464185469981703940773278555290966031304945320116490166188526741221755 81970081566833135764635865334239137556752595565967631971796368733564129062010 43485718722073654078456231050459720529909189788870585358380411961151043159159 15195706888527789998582871600790742661656398056712409624169047960506988653384 33092447775519785656479655580063182482968475193720597548174420171521907295487 64035804592885438408361210933460339504747396032688995914603603589785555985270 25766909458633822943206403572439684659265234327367979568792867116515445746634 93586179470081169339353921942723377522500204120372895405306638933551052448064 35113563657797138612632810349832064927659398409563878463848286063824009619857 72657057528419637494535124501629492220657374181071548528752623113826029232854 34138927377233331932491793853073275664704846389961946194735075061533442526441 49737707267456602967891575989908952182450789051442096081582940831530202698734 78289243378270016506323189355099352165726255120210967458098692281676680845667 25940353997585766639258755658054063394364505274280296477304340036405787469723 55871831786825710964402483049865107255803496575204652936199019538663945440158 85860283067567133877840981225786204403320196385903895277967094807553513005747 13312529606120211481118202180269270812314555156561403704848886390736815579136 06862284069156739191521264312518917285506034204188226210028023820011810681362 11287973016133579100374511377754112183979439460117010625462731791365710608707 23336440955887825855956027198927475924566701896644479984393341183835927189626 53248817051070226731931002467567295021073782196715733960067172903272489618441 34358992677946471401260413751480310381424925275214567958294630811315585631585 51001273045088179382668282076539433693223365337382868613316821475900846378703 65149591981086009472798060343416107535076748026707257906417165374402518218731 98169281896088926526028742749940505645770773753362873956929810082732218354544 20080545810203302104691428169064270492370609272302896660963150602325237543925 54562882521175413214715075628761051542850803555271482894521309555251581644240 82028101790693796729301830143804148626460826561494718059331073043181693231033 61004485567433035580502605272505592087472714806033862306974129394329825699050 32206867717383669128064594272121273846649959940192939539307887861785456748148 09294962848711978633164198912777299190547831468951276579704066408950915400824 84269789017560499206333799410745892014408055730499037921939191848659752999770 79338505461381805683840802006845563569935602356688176385836660247593848026952 77050036320431673107398871251171577396682141242768269823140256115508880691498 16345708480160409872426589794027650122443610602990340231270818767602932302223 98240250928176645869069264859808518568985181295814047089397351787326338947326 24611879072906974539801649300044955107508098181900045149142311352439798244276 93154405906433398578623706760258792733311588777408143512986791532681902323045 89060753846355963189735676054631501900792738432896841188585560371125469727582 39375813849739149421461118491687971653633051930669362771000783987166058623159 05242344184973206202398684439160071382034803559082019087066974958711800551401 06330502245552928807227642243896333391681097495480652724131533921335160125041 26961520487664067372531532766914432502141896463595345991517932258905809592044 26298067612451774768082521870759528862466711450670501755325261395459442275006 32586652723990107809305817427311802303034571461328461570491747093389505327215 07730383905854210117538711849328951748295866047496785983411644185352883548074 53934272894815362032146132860766574767805881301143371158220936898123079443422 00742686076621171741683390179362786955705607722024208202709390791594746279403 50296914741248028272201571834695762959632772067424745696242592018843404897154 78274746039676399920017305747697223997174593522480753609065635015648414619076 01023006699614657207762620967331264047942346295558406977560955320190760739845 99569723866266216985519262039857550536981689337777763139434492073739933219594 93112387314535743628660556999702567793326674815517752749861124786122479123620 15414664236588538401702293042525510412618989156875042349430821256898021092980 98422338637450707308246238547575408993705952345389511696281558829575098584334 91406120687110330062082474148299686381747152308844152845611808371807228497299 25806338057795837188946753414618280834420993845708820129949007006519942407222 96022097485865075021157872052697914727351829909629830573732117236353934093600 91919921236300045420274762922621126251354814289630322005528617579632864039069 50171002923797550536352515747428694496321883343777040890614246217329422281194 08764395455351692021181462696912861155028148673525261822956306039849479255751 12408661344790727918910820644737090579609862721377860705057128441653921021013 64793238702875383594897675073044171893490501453606166471341577638762155692349 70198187442796422152279591551545003025472718989681022472833409388131116952573 37614033147448580944665849042937856239761302870393794229670146013365913879618 86826418652941377607532066228741223667774288493382099151176597760034048894549 91493772124976920074427061127920873156525797475431340917946047203382625717139 32335843783408305317861163869245989924784587070311084543064193096870765510753 55999927703238683130266204404639915424028541531243516089739091486555433187737 65808990711489993823658747308292435497266219120320537490746323294139203401144 42091552754496116318420001168846194359894280952801043351839168249936261100907 07190744445468849523867064951662654268100773841195721427370136701816882276316 51268847910110027594360263796302118678944440930868499771944818604720697414184 35229287503231681735920949667178680829785540712544707590315163825706995663029 80862677517649554830383080441662757011700367357685725677192079647728342245450 44972350894648155887838448419331731190434351733636234172116946423136988993648 41794457803083193894872134331303705412656490067536307973194353203324594218120 39608534082848090926305207407243216077758877130014230268517055004581693653696 42845177624487869288952001764911005005737511051433241938404667169214122751022 32795124642298508179028432771605989190790951237965762279962681657402140134800 27542449819002375985064699912693543452933083463127794424047329610371352368707 71883563613556254299905328910471459552198363636654235008066887705351119568226 80219085375907666650607964538501157318663303760694185415793926243780497088480 26837841908083608864791863483793898921554006106599698445728888725671747534443 63634040846731032989752557217103548883830302135942112865570067881183348927808 67854870060105408674925221488379586393989920947270253386854485701470567489393 28433714688847256288346637264286577895358097851845939308670498376675644277725 05089827749029700107095354100646416249923588567830290525927570180838506647803 98777072155314844907373046315254627682393604288047336945915331136810779178765 65800396665664521862118984250115413576632769575809074643286673387296080429560 61813650505622912605461239629756259662441951919279233274670171216984524344601 39693728916031899776327496230081996803350410739620580055346211614651017625041 68266993770581157103508594158856232450346110002877838497581784214764421158170 60963415606722581089259831315431264049806346339743965329111093290513621560743 35428586161691597285629840058650813022928883884272395672715040460351991596733 48420126633126464172095869312075441430400178036500547751887725918433260088491 59574965753461182557783116266448136033469890564045961721824740381418547002729 58836072810424503440069597645792440840000115821935452746452152720676413319603 74414039212788326246014611122671253091599317762345729794821143389858195645744 29305381453290167988885750920484971056850434139692244745590821544515378070148 83548635205211465612559677085171736512782231826166837718042603077917115008397 21181793801309944616358074636689563859290070881663293106843888142782259674785 40306537123809859500796391130215327960890891558168371664713547558350064552789 79687456469514492057899549313750298047390946724388744261113224793885368604816 07279776906711329172868248777467133099660098238912461634248092238454248417639 23355524521191928278429608370213407980729637177178369601852186139885235217412 05916602659619048603392587831777159347259065082230321341477287017770598450910 22209733498340013844266861350096823249170719756424658207094735269179565959825 54553267108280096299628956996192108146272759400505646929000743922043490355778 94872628956120583996358084773648909085088774282849007504266156530518010416356 49766287698735513853858849433799915195926909610471832254930421101438645607804 89778907145299804692105384034373548858828997143565504902290729247935832983124 43234847493517495480937248674802499128814931488691543918467843571681062101222 39624654710622017356668036373398446181030729648138984029713680589214903094396 12464119158935167919298761155899018910992412904198769344818262834555816882815 42862315836099328367623794013751049838609714444357589488032598498960249030094 91017222866842771764486552189628911014633814732699316881553277507714850189703 33522997254896570882927943668929863140819541118634592137048161802871355200982 83504778066303812201606359304113208919712228322618312823825536950907984730119 04664599772777674689583942119775077616705958501769876823123319939440426019213 04285845068244436474582089863974200639852256510985719351764767834242251278317 21573858151729339529011807846950384795223315305451829810919057452143788917191 33811380838320473259478214612087562511048242885491485366632549248078846000272 50768514005435284372096831678814734633674405473643965922899495093564671966549 59008449152003943292794009085072460672216585447890597437606434104274035409548 58335350704677278236973458459841825164036773947362307301201980064243407913747 13897973705318245703921648822843246551222503602575846803140959991599795013789 39513696880340279190219083695772237151623529811682899335158824918163689561722 04164083290898871220966515283950770247495872100451404738230851953929198718588 90308628862473856517011710077103831628571862501843405853078050022001798413660 54194090602281090861998196296922013181753853845936445034965187036281532338048 79738988605052770070773821111016540267457155442251027554667823541838231055703 39334706701662744085487261699963434905517661438288185620642152155604891926968 98159470217990197113027766838397227932956569554555545989435108034157139515296 86841041364789976014059807128291070982611088467118712896789732442152393783603 60028811120390740423415502625054676577416789626349787778079252659824740421576 21138586246247782804229205020394569875993972078857954928604625856432496001976 35809497415995503069956945643042398154759865624406918633720082225914993942043 90292288188085137558644011446684322904395924941761938457580849532062256847940 99975629674295745657427560414506102809436770470190573971990429610392526799576 43978346420659094503093209157677286944632178338093696791301039799178415329212 56153527522430739593987022981971342533337635877709833317302649962400219833904 00985319470085890432677698126239245779037531442010770396997342141749497483554 77455685920136099767391625811501361256846786558510232147395051438437567709550 35968683975803020435278224695079339823623392824459891678831769497237710572041 18204669747691004167909848008567446234294039130072814759713245226645606676163 54306393215034944919815732363101436988818788734422126527484477798832557771532 33432496542717898806391507602669569687520054231063023083067611030647954113074 54430777793620052797448437439214089275747968421001091221147357583516814883030 18816972545230291485361095167820647695029226617983932385551056834004412945837 54589214652103528631278730887820902899709668722417608442618722120774728336460 42893236502516808051116059814318116092763706722093466767355305606436667334472 06209666918609072625997685392528778408486710198126027623432597849221532402506 53282922685980584219506925061990975681213068365481871723163145283397740266776 56932088069937170338533215839433394021467403927778051932960257106053136318229 93501832759999868604612430634182122416321609655322513169720608539998058092819 94731415075060331827573369773978564701616990608446940568966889243151533431539 17737421620855384896762318951087460392881425950274806744502997950701760298742 83502754716890401290196276961392348136428603489591857731288734287149599054564 03820142414055222290572423638033485499050085363416765805412607906660948202608 80030199941087375945979263627519680484680659925598228597454257740101087903260 68801636217089206028849976102041255596598945125609539480428690095520309784046 50129171356899054263131269851460124836991457415735186296986041194577515702140 84254483347518106023144277304378856156227163664995824297143134171828033196563 13634810669748192209402681801082851608325778778674728085699284562331620626773 21222866076380695701306952427128932720022050643944425719193413868536412515009 04838622307233730741236931779397265308705381707482636859500924332422892213428 27504129597603080586780826719766690916059171085574025331902033431699553832473 38287373835967885648542134373713959573258314745788330997473576678389077894882 77200438455694987136384688241565836067447589745782801291663633468851525554172 28704511525864848499280853645875350067900328794687669685463290186819886919553 82814962191957682385074607837846528902841792316908277854741022093177224804006 49497416905511957627676940660218890733192574523561422334487096985554816428342 09026127765745208482852490391457267173431240641888882107527148692893010007626 17566038222560131326368874713825813740793415066256467539968825565493175916237 62008770729564578434076040215768360656921522304779204135219478284821047259976 86910899884630564353267915087752355984316883326613128331750677212935052730938 72707203392326953366943765627911902812836479905563681158843622677701168470851 33046476770282347722097257804897501284072969336802122093819821219785446794760 61649583193372717794702918358708430058317235593578920563910643962755293946195 59038356060878508879699396819210545043070911919085901748607666094521090876573 60133408272526489608224589773526478124889845091375623164931506899006450635103 49843082459420196299970911012831064836699362109971893840718118668926974815441 29484276807983748023269822507500502256558605123231529389565164955452460990530 47943872480165786087459869783418999103170647352972924797848600627960934890530 47223032418641501781282076907354315558416395365703645920686092220855508558043 57159395012987321194572782287747214558347385634080980451016674113371379812398 97774375728553030586072745237063050994810305760613665648248860333670132801896 66942832144699985690960514639829236675531173147342114059178445075721131781319 88478355486497583223190745542628484861307908433324102395544462765576695753382 65706010968438816853385484312353291649394903415555167783385015823651415225423 18637549826624444098088294989941826041884069992787087773080684515991274731634 30161908430844949344982234650104632462325937497602990738942741286686070820840 54805350654017105938431248458091715495300579123111562236208405002787176750229 11202555112448234898739072570344289738393660177422089458645734287599038201457 42758012853018494026897772047628029576610745074745952354612605330736606068308 13698902891630278524864450584708733234691771495952397799102696538969601664942 52304897894927625036003917957341463956575708831191681590855948821851035596500 94357375435895600569912753723726788607584528787599533733320544654874118020699 52858209077840227211038161954710275471248173933538332254337221235425893255791 49606958812620052800046489973753937496962284151493861826872216833833432099259 15204993964262910036605937014097444618151977818958898647908946939651817174012 06866696194338818512916247063740425797050284785413522557279495894791115871656 25774430702620595230737437620966543193996422647525308672346202031704886273054 12588443026036026063257769868204384295693510347027855901781477166577959058790 38769217227718823199412577097449038839878532622591396413498204370081518345422 65737118082705099529951463044604466534865414885549150010040690109930703166596 90874639503986678637053903714976947122308423231212024533432412834408124923550 89512296946050902300337482666275069949122435624452472960307814446575827128830 44326860175376060329764313072118507089472541307836876603834444863977214957820 31679977411565556602637191977338996093380256007239191321437760222890768195903 21701313909366285557832285291544118740210343339794843248785539883300940172476 54191654728279987863204291029454249061965847854995132177112730132886073480123 68268493279260403717058658594894184249773083050086907542750133834325374971854 45995707129232441541861524776401028901096821850407923309985389650049369576678 11050160355013632458865243152243940469753567444360461513964331842064842407835 85709902306172138491398542760432741212755677381153053892561883906376602193683 23673673082271167895614943253264415324079640048510932988337863164470356633985 2138578455730061311
2.2		TURTLE::GILBERT		`Tue Jul 10 1984 19:14`	1
	The longest repeated sequence is "25308672".
2.3	What are the others?	ZFC::DERAMO	Daniel V. D'Eramo	`Tue Dec 01 1987 15:46`	8
	Does anyone have the entire list of values of p for which 2^p - 1 is prime? Is it definitely known that for all n not in the list and less than the largest element of the list that 2^n - 1 is composite? Or are there [reasonably small] values of n for which it is not known whether the nth Mersenne number is prime or not? Dan
2.4	29 known Mersenne primes	ZFC::DERAMO	Daniel V. D'Eramo	`Thu Dec 03 1987 22:04`	21
	I found the list at home! The following is from the second edition of Seminumerical Algorithms, i.e., "Knuth's Volume 2," section 4.5.4 page 391. It listed twenty-seven primes, and .0 gave the last two. A second reference gave the first twenty-four of these, but it substituted 9889 for 9689. Fortunately, 23 \| (2^9889 - 1). Assuming all of these are correct, the twenty-nine (29) known Mersenne primes are 2^p - 1 for the following primes p: 2 3 5 7 13 17 19 31 61 89 107 127 521 607 1279 2203 2281 3217 4253 4423 9689 9941 11213 19937 21701 23209 44497 86243 132049 Will somebody please check this list for typos or other errors? Does anyone know if it is known that no other value of p < 132049 yields a Mersenne prime? Dan
2.5	The Lucas-Lehmer test	ZFC::DERAMO	Daniel V. D'Eramo	`Thu Dec 03 1987 22:07`	11
	From Seminumerical Algorithms, second edition, by Knuth (his Volume 2 book) section 4.5.4, pages 391-394. The Lucas-Lehmer theorem: Let q be an odd prime, and define the sequence <L(n)> by the rule L(0) = 4 L(n+1) = (L(n)^2 - 2) mod (2^q - 1) Then 2^q - 1 is prime if and only if L(q-2) = 0
2.6	Another curious fact about Mersenne numbers	ZFC::DERAMO	Daniel V. D'Eramo	`Fri Dec 04 1987 20:58`	12
	From: Elementary Number Theory, A Problem Oriented Approach Joe Roberts, MIT Press, (c) 1977 by MIT. If p is an odd prime of the form 4k + 3, and q = 2p + 1 is also prime, then q divides 2^p - 1. For example, if p = 3, q = 7, and 7 divides 7. Or p = 11, q = 23, and 23 divides 2047. Dan
2.7	30th Mersenne Prime	TALLIS::STEELY		`Sat Dec 05 1987 02:00`	10
	I found an article in the November 30,1987 issue of Insight ( a news magazine) discussing fascination with prime numbers. The article states that a programmer named David Slowinski, using a Cray X-MP took 3 hours to find the 30th Mersenne Prime. This occurred in September 1985. The number is 2 raised to the 216,091st power minus 1. Simon
2.8	Thank you, Ephraim Vishniac	ZFC::DERAMO	For all you do, disk bugs for you.	`Wed Feb 10 1988 22:49`	47
	Newsgroups: sci.math Path: decwrl!decvax!ima!think!ephraim Subject: Re: Largest Known (Mersenne?) Prime? Posted: 9 Feb 88 19:41:00 GMT Organization: Thinking Machines Corporation, Cambridge, MA In article <11192@shemp.UCLA.EDU> khayo@MATH.ucla.edu [not CS !] (Eric Behr) writes: >In article <385@osupyr.UUCP> gae@osupyr.UUCP (Gerald Edgar) writes: > >additional Mersenne primes: >(...) > > 2^132049 - 1 [1983] >Since large primes have no relevance whatsoever to my favorite hobbies, >I did not listen carefully - but I'm sure an NPR report about a week >ago mentioned another record-setting Mersenne; either the journalist was >wrong or we're all behind the times... ??? > Eric My co-worker Roger Frye found an article about this most recent discovery in _Science_News_ for February 6, 1988. The Mersenne prime discovered by Walter N. Colquitt is 2^110,503 - 1. It's not a record, but it was overlooked in previous searches. The article explains that some record-setting searches weren't exhaustive. There may be other undiscovered Mersenne primes less than the largest known (currently 2^216,091 - 1). Thanks to the unswerving dedication of sci.math readers, I'm now aware of the following Mersenne primes and discovery dates. According to the Science News article thirty-one are known, so this must be the complete list to date: 1. 2^2 - 1 [1644] 12. 2^127 - 1 [1644] 23. 2^11213 - 1 2. 2^3 - 1 [1644] 13. 2^521 - 1 24. 2^19937 - 1 3. 2^5 - 1 [1644] 14. 2^607 - 1 25. 2^21701 - 1 4. 2^7 - 1 [1644] 15. 2^1279 - 1 26. 2^23209 - 1 5. 2^13 - 1 [1644] 16. 2^2203 - 1 27. 2^44497 - 1 [1979] 6. 2^17 - 1 [1644] 17. 2^2281 - 1 28. 2^86243 - 1 [1983] 7. 2^19 - 1 [1644] 18. 2^3217 - 1 29. 2^110503 - 1 [1987] 8. 2^31 - 1 [1644] 19. 2^4253 - 1 30. 2^132049 - 1 [1983] 9. 2^61 - 1 [1886] 20. 2^4423 - 1 31. 2^216091 - 1 [1985] 10. 2^89 - 1 [1911] 21. 2^9689 - 1 11. 2^107 - 1 [1914] 22. 2^9941 - 1 (The date for the 29th entry is assumed. Since it's in the February 8th issue of Science News, I suppose it was found sometime last year.) Ephraim Vishniac ephraim@think.com Thinking Machines Corporation / 245 First Street / Cambridge, MA 02142-1214
2.9	2^756839 - 1	GUESS::DERAMO	Dan D'Eramo, zfc::deramo	`Thu Mar 26 1992 21:49`	36
	Xref: ryn.mro4.dec.com sci.math:24390 sci.crypt:7427 Path: ryn.mro4.dec.com!nntpd.lkg.dec.com!news.crl.dec.com!deccrl!decwrl!mips!zaphod.mps.ohio-state.edu!magnus.acs.ohio-state.edu!usenet.ins.cwru.edu!agate!linus!linus!gauss!bs From: bs@gauss.mitre.org (Robert D. Silverman) Newsgroups: sci.math,sci.crypt Subject: New Mersenne Prime Message-ID: <1992Mar26.143538.106@linus.mitre.org> Date: 26 Mar 92 14:35:38 GMT Sender: news@linus.mitre.org (News Service) Organization: Research Computer Facility, MITRE Corporation, Bedford, MA Lines: 24 Nntp-Posting-Host: gauss.mitre.org Cray has just announced the discovery of a new Mersenne prime. It is 2^756839 - 1 and is over 3 times the size of the last one. It was discovered by a Cray-2 in England. It has 227,832 digits. Computational number theorists are concerned over this announcement because we would like to know whether this is the NEXT Mersenne prime. In the past people at Cray have jumped around, hoping to set a record, rather than searching through increasing exponents systematically. The discovery would have MUCH more value if we knew there were no more Mersenne primes between 2^216091 -1 (the last one discovered) and the new one. Walter Colquitt checked the entire range from 216091 to 365,000 without finding any, but we'd like to know whether there can be any between 365K and the new one. Otherwise all this means is marketing hype and publicity for Cray. I would like to note that on one occassion a Mersenne prime WAS discovered that was smaller than the largest known. It was discovered by Colquitt and had fallen through the cracks of the people at Cray. -- Bob Silverman These are my opinions and not MITRE's. Mitre Corporation, Bedford, MA 01730 "You can lead a horse's ass to knowledge, but you can't make him think"
2.10		WBC::BAKER	Joy and fierceness...	`Mon Mar 30 1992 19:22`	9
	The discovery of this prime was used as a piece of news filler on the CNN cable channel recently. The newscaster, who clearly didn't have a clue, said that this prime was, "three times the largest previously discovered prime number..." I wish I'd known it was that easy to find them... ;-} -Art
2.11	on primes in the news	STAR::ABBASI	i^(-i) = SQRT(exp(PI))	`Mon Mar 30 1992 19:41`	7
	ref .-1 That Newscaster who did not have a clue, easily makes three times as much money as you and me combined :-) or is it :-( /nasser
2.12	Did CNN really say that?	GUESS::DERAMO	Dan D'Eramo, zfc::deramo	`Mon Mar 30 1992 20:24`	14
	re .10, From reply .8, the prevous largest known Mersenne prime was 2^216091. So this one, 2^756839, is approximately three times as long (counting the bits, or digits) as the previous one. Actually, over 3.5 times the length. The largest known prime had been 391581 * 2^216193 - 1, not a Mersenne prime and only slightly longer than the previous record Mersenne prime. So this new one is over three times the length of that, too. Dan
2.13	And the number is?	RUMOR::ROBBINS	Worth Robbins	`Wed Apr 01 1992 12:51`	16
	I have a friend, actually the retired CEO of a mature hi-tech company, who has a friend ... To make a long story short, he would very much like to have a print-out (all 32+ pages) of this new Mersenne Prime Number, to give as an unusual gift to his friend who is retiring. I am not a mathematician, so I don't have a clue how to generate the number. Can someone either mail me the number, or give me some direction for generating it? I assume it doesn't require nearly as much compute power to generate it as it does to find it! Sorry for the intrusion into this lofty conference. I promise not to pollute it any longer than necessary! :) :) :) Thanks for any help.
2.14	re. .-1 I will try it with Calreal ...	OINOH::KOSTAS	He is great who confers the most benefits.	`Wed Apr 01 1992 17:28`	16
	re. .-1 I think Calreal may be able to do it. I have just started a batch job to compute 2^756839. You can do this with Maple probably faster. Any way both the Calreal executable and the potential output from the computation of 2^756839 are in: COGITO::$1$DUA203:[kostas.userlib] Enjoy, Kostas BTW: Calreal computes 2 to a large number with the BU function. So 2^756839 is done with BU( 756839 ). Also remember to subtract one from the last digit in order to get the new Mersenne prime.
2.15	Mailed...	CIV009::LYNN	Lynn Yarbrough @WNP DTN 427-5663	`Wed Apr 01 1992 20:03`	4
	I have mailed off MAPLE's results (2925 lines/78 chars). The number takes about an hour and a half to compute on my 3520. It literally looks like the output of a random digit generator.
2.16	humm..if it looks like random, and feels like random..then..	STAR::ABBASI	i^(-i) = SQRT(exp(PI))	`Wed Apr 01 1992 20:15`	8
	ref .15 (Lynn) >It literally looks like the output of a random digit generator. then how do we know it is not a random number and maple is just tricking us by waiting long befor typing it so that we believe it? :-)
2.17	Be my guest	CIV009::LYNN	Lynn Yarbrough @WNP DTN 427-5663	`Wed Apr 01 1992 20:20`	6
	> then how do we know it is not a random number and maple is just tricking > us by waiting long befor typing it so that we believe it? Well, you could try factoring it. (That ought to keep him out of my hair for a while! ;-) )
2.18		BEING::EDP	Always mount a scratch monkey.	`Wed Apr 01 1992 20:40`	8
	Re .16: Well, I computed it too, so we could compare the results. Powers of 2 are pretty simple to do with a program. (I did the subtraction of one from the 227,832-digit number by hand though.) -- edp
2.19	i wonder what algorithm EDP used for this part?	STAR::ABBASI	i^(-i) = SQRT(exp(PI))	`Wed Apr 01 1992 20:57`	6
	>(I did the subtraction of one from the 227,832-digit number by hand >though.) i really love to hear more about how you did that .
2.20	Your mileage should not vary!	CIV009::LYNN	Lynn Yarbrough @WNP DTN 427-5663	`Wed Apr 01 1992 22:18`	11
	The 32nd Mersenne Prime is: 2^756839 - 1 = 174135906820087097325163599245903327890779363690507030974654735538382721562066 257631914797436422461610635130071368293660728159709054586772369049491142934772 020896204050242188730034975677375975566408927899798507256190573103216371084706 ... [several hundred lines omitted] ... 912403438449903036450540594384275497234460834579807796823701486980464630401353 549158331329746013894828484221196197247890145658094439640926716840918349113692 649241768590511342720126927068487680404055813342880902603793328544677887.
2.21		GUESS::DERAMO	Dan D'Eramo, zfc::deramo	`Wed Apr 01 1992 23:32`	3
	I have it but in binary instead of decimal. Dan
2.22	(-:	AUSSIE::GARSON		`Thu Apr 02 1992 02:17`	13
	re .16 > then how do we know it is not a random number and maple is just tricking > us by waiting long befor typing it so that we believe it? You could take the reputed 2^n and divide it by 2 756839 times. If you finish with 1 then MAPLE was not lying. If you get bored before finishing (say after 10000 divides by 2) then you could check whether the frequencies of occurrence of digits as the first digit of each of the numbers produced to date (which should be powers of 2) match the expected distribution (although I'm not aware of what statistical test you might use).
2.23	Mission Accomplished	RUMOR::ROBBINS	Worth Robbins	`Thu Apr 02 1992 11:42`	8
	re: .15 Thanks, Lynn, for giving me what I asked for. My friend was delighted! I also gave him a print of this discussion (hope nobody minds, didn't seem to compromise any confidentiality). He was most intrigued by the power of this kind of communications tool. Worth
2.24		BEING::EDP	Always mount a scratch monkey.	`Thu Apr 02 1992 11:45`	6
	Re .20: The first and last lines match mine. -- edp
2.25	A 1-derful idea	VMSDEV::HALLYB	Fish have no concept of fire.	`Thu Apr 02 1992 16:08`	8
	.21> I have it but in binary instead of decimal. .16> then how do we know it is not a random number and maple is just tricking .16> us by waiting long befor typing it so that we believe it? You could convert it to binary and see if it matches Dan's in .21 John
2.26	How about an improved algorithm to compute the Mersenne primes ...	OINOH::KOSTAS	He is great who confers the most benefits.	`Fri Apr 10 1992 14:05`	12
	Hello, I wander if anyone has any ideas on how to compute these large numbers. I am not happy with the algorithm I used in Calreal, and I am looking for an improved one. Calreal takes too long. How Maple is doing this? The intervals for every 100k (i.e. from 2^i to 2^(i+100,000) ) computations are so far {5, 4.5, 10, 10, ...}. These are elapsed hrs on an overloaded system, running as a batch job at priority 3 Kostas
2.27	Look for other avenues	CIV009::LYNN	Lynn Yarbrough @WNP DTN 427-5663	`Fri Apr 10 1992 15:35`	8
	Since 2^n-1 involves only simple arithmetic (although on arbitrary-sized arguments), the problem must be there. I would suggest you adapt something like Brent's Multiprecision arithmetic package, or simply replace CALREAL with MAPLE or Mathematica. If you are determined to stick with CALREAL, take a look at your storage allocation, as you may be page-faulting your system to death. Use virtual memory Zones to limit address scattering, check your page file size, etc.
2.28	What is the algorithm Maple uses?	OINOH::KOSTAS	He is great who confers the most benefits.	`Fri Apr 10 1992 16:08`	11
	Lynn, I was looking for Maple's algorithm. Do you how Maple does it? Of course I can replace something with something else but I am more interested in the process which will lead me to the solution rather than the solution itself without any knowledge of the steps in between. I will also look at system related things I can improve use of (i.e. better use of memory, reduce the page-faulting, etc. ) /k
2.29	Divide and conquer	CIV009::LYNN	Lynn Yarbrough @WNP DTN 427-5663	`Fri Apr 10 1992 19:08`	14
	In all likelihood, MAPLE evaluates B^n (for integer B and n) by forming B^2, B^4, B^8, ... by squaring until the exponent would exceed n, then representing n in base B, then multiplying the powers together with the corresponding base B 'digits'. E.g. 500 in binary is 111110100, so 2^500 = 2^256 * 2^128 * 2^64 * 2^32 * 2^16 * 2^4. For B=2, n=~1,000,000 < 2^20, this would involve only about 20 squares and divides (to form the binary representation), plus another < 20 multiplies, or < 60 [extended-precision] operations in all. Since the numbers get very large, storage management becomes quite critical. There are actually somewhat faster ways of doing this, but only for special cases. This is the fastest general-purpose algorithm for doing it that I know of.
2.30	divide and conquer multiplies	3D::ROTH	Geometry is the real life!	`Fri Apr 10 1992 20:24`	27
	MP is very slow (O(N^2)) Maple is probably better - I'd guess it uses Karatsuba multiplication; BIGNUM and PARI (a couple public domain packages) do. For numbers of this length, an FFT based algorithm wins. For "modest" lengths, other less esoteric techniques (but still better than O(N^2)) are useful. I once coded up an FFT based multiply, it's not that hard - but what I wanted to do was compute PI as a hack and was finally too lazy to finish the AGM algortithm off. Knuth discusses this in some detail in VOL II. Another excellent reference is Aho, Hopcroft & Ullman - their book on analysis and design of algorithms. (There are two by these guys, the book published in 1974 is the one you want - the later one is more elementary and doesn't have the neat polynomial and number theory algorithms.) Just for grins, we ought to put together a program to run on the ALPHA and get DEC some publicity! It's a crapshoot to find yet another Mersenne, but what the heck? Wish I had time right now, or I'd consider coding something up! fwiw - I believe the DEC library has the Aho et al book, and defintely has the Knuth volumes. - Jim
2.31		OINOH::KOSTAS	He is great who confers the most benefits.	`Fri Apr 10 1992 20:30`	6
	re. .29, .30 Thanks for the info. Kostas
2.32	the hard part	RDVAX::GRIES		`Mon Apr 13 1992 11:19`	39
	<<< Note 2.26 by OINOH::KOSTAS "He is great who confers the most benefits." >>> -< How about an improved algorithm to compute the Mersenne primes . >- << The intervals for every 100k (i.e. from 2^i to 2^(i+100,000) ) >> In binary it is quite easy to compute 2^i. It is just 1 followed by i zeros. The hard part is to convert it to decimal. This is a log file for a program that dose just that: 1741 3590 6820 0870 9732 5163 5992 4590 3327 8907 7936 3690 5070 3097 4654 7355 3838 2721 . . . 1961 9724 7890 1456 5809 4439 6409 2671 6840 9183 4911 3692 6492 4176 8590 5113 4272 0126 9270 6848 7680 4040 5581 3342 8809 0260 3793 3285 4467 7887 $ GRIES job terminated at 10-APR-1992 19:37:00.03 Accounting information: Buffered I/O count: 137 Peak working set size: 1240 Direct I/O count: 719 Peak page file size: 5235 Page faults: 1275 Mounted volumes: 0 Charged CPU time: 0 03:08:31.65 Elapsed time: 0 03:30:40.07 A few lines where omitted. To rases any number to a power is also on the order of On2. By noting that (a+b)2 = a2 + 2ab + b2, one can sqaure a number in 3 verse 4 digit multiplies(used recursivly), one can build a table of an using this and strassen mult (which also using 3 verser 4 digit multiplies). From this table and exacting the bits from i (the power) one can use sqareing and this table to produce x*i quite fast. (the job was run on an 8800 (a little faster than my pc).
2.33		OINOH::KOSTAS	He is great who confers the most benefits.	`Mon Apr 13 1992 13:26`	15
	re. .-1 Hm! Still it takes too long. 3hrs for just one conversion. The numbers I gave in 2.26 included the computations of all the numbers in between the intervals. I have revised the algorithm (whuch I wrote over 15 yrs ago, not thinking that I may use it one day) this small change has reduced by 50% the time to compute things. I will also take in conciderations some of the better ideas/algorithms which have been mentioned by Lynn and Jim. Kostas BTW: I am still interested in Jim's idea to do somthing on/for ALPHA. And also to possibly include some 3d graphics with what ever...
2.35	results from calreal's computations ...	OINOH::KOSTAS	He is great who confers the most benefits.	`Fri Apr 17 1992 13:32`	112
	Hello, finally calreal was able to compute 2^756839 (allong with 2^524288, 2^131072, 2^65536, 2^32768, 2^2048, 2^1024, ..etc.) All the log files are in cogito::$1$DUA203:[KOSTAS.USERLIB] Enjoy, Kostas [the file: cogito::$1$DUA203:[KOSTAS.USERLIB]756839.TXT follows the <ff>] 17-April-1992 KGG Bin( 756839 ) = 10111000110001100111 = 2^19+2^17+2^16+2^15+2^11+2^10+2^6+2^5+2^2+2^1+2^0 756839 = 524288+131072+65536+32768+2048+1024+64+32+4+2+1 2^756839 = 2^524288 * 2^131072 * 2^65536 * 2^32768 * 2^2048 * 2^1024 * 2^64 * 2^32 * 2^4 * 2^2 * 2^0 2^756839 = $copy cogito::$1$DUA203:[KOSTAS.USERLIB]BU_756839.LOG 473 blocks 2^756839 = 17413590682008709732516359924590332789077936369050703097465473553838272156 20662576319147974364224616106351300713682936607281597090545867723690494911 42934772020896204050242188730034975677375975566408927899798507256190573103 21637108470694652916898854453072238024854779794184696894887758147211719609 65210713013814778365553675674358992096753406551200742920360681239094095454 31263090578167973446135882135220353524610720279709899877492086995072413691 41881560320836818547291247759862604646096021625722838827389398918901046172 19312155545932570137995324568811857599667820430751438563819872265046778990 75388614684059162796035611746273011187409173317780614397122325261492282373 . . . 08931828844882542977421984695686241777087064030247524792828312585598040121 58842129767473187809311531318216753914541797571068392534875840214937021204 75037889055619401647443568291937923950889819022384242323287676366831963185 72845992994357198238764218257600092347749874489787697991240343844990303645 05405943842754972344608345798077968237014869804646304013535491583313297460 13894828484221196197247890145658094439640926716840918349113692649241768590 511342720126927068487680404055813342880902603793328544677888. 2^524288 = $copy cogito::$1$DUA203:[KOSTAS.USERLIB]BU_524288.LOG 228 blocks 2^524288 = 25963705678310007761265964957268828277447343763484560463573654867754610524 58820506291297794947214897395589962375459750509570675451859578206757876095 31508697262806961751931496377866583367890040412170536419385921982874094559 . . . 80413270039602684203180937221428794395056582480709158696527133056906527421 02152309910224784007189358162459091908170350667564127339646062694187078575 7806032358647396868643349179648430125596209011369814364528226185773056. 2^131072 = $copy cogito::$1$DUA203:[KOSTAS.USERLIB]BU_131072.LOG 83 blocks 2^131072 = 40141321820360630391660606060388767343771510270414189955825538064669013687 29258341160522025816124993789993695822370688304664951507188547123423222707 02846264574450449509977123603977273147952610921109000431179440424033912478 . . . 15246895239142374977327742276519573650394798160420938696928927504422600899 90057846092135730271596012667026861366440630925589866880619587057899636653 6709926807407399180325362544275565838974676261850665812318570934173696. 2^65536 = $copy cogito::$1$DUA203:[KOSTAS.USERLIB]BU_65536.LOG 42 blocks 2^65536 = 20035299304068464649790723515602557504478254755697514192650169737108940595 56311453089506130880933348101038234342907263181822949382118812668869506364 76154702916504187191635158796634721944293092798208430910485599057015931895 . . . 26015571920237348580521128117458610065152598883843114511894880552129145775 69914657753004138471712457796504817585639507289533753975582208777750607233 9445587895905719156736. 2^32768 = $copy cogito::$1$DUA203:[KOSTAS.USERLIB]BU_32768.LOG 21 blocks 2^32768 = 14154610310449547890015530277449516013481307114723881672343857482723666342 40845253596025356476648415075475872961656126492389808579544737848881938296 25087319174392779354491301105016265127795702984696021178324293352120754541 . . . 09297002910250505302287769412337441199360424519160716552890882816796378296 88164182798145303520723375206351878277849374382770810991349316293218242762 7261046280168269958077541122668104633712377856. Note: All the .log files above contain long lines and they should be printed with the qualifier: /para=(data=ansi,page_ori=LANDSCAPE) 2^2048 = 32317006071311007300714876688669951960444102669715484032130345427 52465513886789089319720141152291346368871796092189801949411955915 04909210950881523864482831206308773673009960917501977503896521067 96057638384067568276792218642619756161838094338476170470581645852 03630504288757589154106580860755239912393038552191433338966834242 06849747865645694948561760353263220580778056593310261927084603141 50258592864177116725943603718461857357598351152301645904403697613 23328723122712568471082020972515710172693132346967854258065669793 50459972683529986382155251663894373355436021354332296046453184786 04952148193555853611059596230656. 2^1024 = 17976931348623159077293051907890247336179769789423065727343008115 77326758055009631327084773224075360211201138798713933576587897688 14416622492847430639474124377767893424865485276302219601246094119 45308295208500576883815068234246288147391311054082723716335051068 4586298239947245938479716304835356329624224137216. 2^64 = 18446744073709551616 2^32 = 4294967296 2^4 = 16 2^2 = 4 2^0 = 1
2.36	Go for an ALPHA splash!	AIWEST::DRAKE	Dave (Diskcrash) Drake DTN 534-2660	`Sun Apr 19 1992 07:23`	3
	Re .30 on ALPHA. An EXCELLENT idea. Please can we do something splashy for DECWorld? Or certainly by the summer... How about the next three primes....
2.40	output from .-1 program after 2 days run. what does it mean?	STAR::ABBASI	i^(-i) = SQRT(exp(PI))	`Fri May 01 1992 17:54`	41
	m = 47303 current i= 756736 current i= 755712 current i= 754688 current i= 753664 current i= 752640 current i= 751616 current i= 750592 current i= 749568 current i= 748544 current i= 747520 current i= 746496 current i= 745472 current i= 744448 current i= 743424 current i= 742400 current i= 741376 current i= 740352 current i= 739328 current i= 738304 current i= 737280 current i= 736256 current i= 735232 current i= 734208 current i= 733184 current i= 732160 current i= 731136 current i= 730112 current i= 729088 current i= 728064 current i= 727040 current i= 726016 current i= 724992 current i= 723968 current i= 722944 current i= 721920 current i= 720896 current i= 719872 current i= 718848
2.41		GUESS::DERAMO	Dan D'Eramo, zfc::deramo	`Fri May 01 1992 19:21`	11
	I think m is how many words it needed to allocate for one of the "bignum"'s, and the "current i" shows the countdown on the number of steps in the Lucas-Lehmer test yet to go. (See reply .5, where the count goes up from 0 instead of down to 0.). Is the program subtracting two after squaring? You should run this first on two smaller exponents, one known to give a Mersenne prime and the other known not to. Dan
2.42	How long is forever?	RDVAX::GRIES		`Mon May 04 1992 16:43`	32
	<<< Note 2.41 by GUESS::DERAMO "Dan D'Eramo, zfc::deramo" >>> / Is the program subtracting two after squaring? You / should run this first on two smaller exponents, one known / to give a Mersenne prime and the other known not to. / Dan I started this job on both a vaxmate and a 6000 on friday. The vaxmate ran checking all primes for mersenne primes starting at 3, it correcttly found all mersenne primes 3 .. 3217 and is on p = 3767 , about 3days time. The 6000 is checking p=756839, in 3 day cpu it is on i=499712 which is about 1/3 finished. Both were complied without inline nor macro, which is about 4 times faster. So to check p=756839 would take about 4 days on a 6000. To run big numbers on a pc one cannot used the code send becuse of the 64k data segment limit problems. The point is if one is interseted in looking for mersenne primes, it will take a control search over many machines, and quite a few number of months. If you are really interested it would not be hard to have a list of good canidates and a check out procedure. Gries
2.43	How many machines are available?	VMSDEV::HALLYB	Fish have no concept of fire.	`Mon May 04 1992 18:25`	17
	> To run big numbers on a pc one cannot used the code send becuse > of the 64k data segment limit problems. If this is the only problem it can probably be solved. On my home PC I use ZorTech C++ which contains a built-in DOS extender that allows direct use of lots of memory. I have personally malloc'ed a 10MB array and indexed through it via generic for(;;) statements. The extender does all the magic behind your back. 386/486 only, tho. I could make up a generic .EXE file that ran off input parameters, and place the file somewhere reasonably public. Then it becomes a matter of handling candidates. All this assumes there are enough machines and willing participants. I don't know if we can get a handle on that, though. John
2.44	restartable lucas	RDVAX::GRIES		`Fri May 15 1992 19:41`	264
	#include <stdio.h> #include <stdlib.h> #ifdef vms #include "alloc.h" #else #include <alloc.h> #endif #include <time.h> #include "core.h" #define SIZE_SHORT (8sizeof(unsigned short)) /#define short_test 1/ / fast_mod_2_to_p_minus_1(D, C, p) D = C mod ((2^p)-1) where C is an at most 2p-bit number. uses the following algorithm: 1. Since C has at most 2p bits, it can written as U2^p + L where U, L are at most p-bit numbers, i.e. 0 <= U,L < 2^p. 2. Using (a+b) mod n = (a mod n + b mod n) mod n (ab) mod n = (a mod n)(b mod n) mod n 3. and the fact that 2^p mod (2^p-1) = 1, we have C mod (2^p-1) = (U+L) mod (2^p-1) 4. Since U and L are at most p-bit numbers, U+L has at most (p+1) bits. Hence (U+L) mod (2^p-1) = lower p bits of (U+L) if U+L < 2^p-1 or = lower p bits of (U+L+1) if U+L => 2^p-1 5. For more efficient implementation, we always add 1 to U+L. Then if we find U+L+1 is < 2^p-1, (i.e. the p-th bit of (U+L+1) (counting from the 0-th bit) is not set), we will subtract 1 from U+L+1. / void fast_mod_2_to_p_minus_1(unsigned short D, unsigned short C, unsigned long p) { unsigned short U, L; unsigned long M, N, i, j, k; unsigned long buf, bit, bit2; unsigned long result; /* M = smallest number of unsigned short words that contain p bits / / N = smallest number of unsigned short words that contain 2p bits / / k = number of bits of M short words in excess over p bits / / j = number of bits of p bits in excess over M-1 short words / M = (p+SIZE_SHORT-1)/SIZE_SHORT; N = (2p+SIZE_SHORT-1)/SIZE_SHORT; k = MSIZE_SHORT - p; j = SIZE_SHORT - k; bit = 0x0000ffff; bit >>= k; bit2 = 1; bit2 <<= j; result = 0xffffffffL; / subtract 1 from U+L / for (i=0; i<M-1; i++) { buf = (unsigned long) C[M+i] << SIZE_SHORT; buf += (unsigned long) C[M+i-1]; buf >>= j; result += ((buf & 0x0000ffff) + (unsigned long) C[i]); D[i] = (unsigned short) result; if (result & 0x80000000) result = (result >> SIZE_SHORT) \| 0xFFFF0000; else result = result >> SIZE_SHORT; } if (N%2 == 1) { buf = (unsigned long) C[N-1]; } else { buf = (unsigned long) C[N-1] << SIZE_SHORT; buf += (unsigned long) C[N-2]; } buf >>= j; result += ((unsigned long) (((unsigned short) (buf & 0x0000ffff)) & bit) + (unsigned long) (C[M-1] & bit)); D[M-1] = (unsigned short) result; if ((D[M-1] & bit2) == 0) { / if (orig D < 2^p-1) then subtract 1 from D / L_DEC(D,1, M); } else { / take only p bits / D[M-1] &= bit; } } #ifdef short_test #define ARRAY_SIZE 5001 static char flags[ARRAY_SIZE]; sieve() { long i, prime; for(prime=2; prime<ARRAY_SIZE; prime++) { while (flags[prime]) { prime++; } for (i=prime+prime; i<ARRAY_SIZE; i+=prime) { flags[i] = 1; } } } #endif extern int split; main(int argc, char argv[]) { long i, j, p, M,temp; unsigned short B, C, E; clock_t stimer,timer; #ifndef short_test char string[20]; FILE last; #endif set_stack(120000); /* printf("Total memory %ld\n",farcoreleft());/ #ifdef short_test sieve(); #else last=NULL; if (argc>1) { if (argv[1]!='n') last= fopen("lucas.log","r"); } else last= fopen("lucas.log","r"); if (last==NULL) { if ((last= fopen("lucas.log","w"))==NULL) { printf("cannot create lucas.log\n"); abort(); } printf("Split = %d\nInput split:",split); gets(string); i= atol(string); if (i) split= i; printf("\nsplit = %d\nInput p:",split); gets(string); p= atol(string); printf("\np= %ld\n",p); M = 8 * sizeof(unsigned short); M = (p+M-1)/M; printf("M= %ld\n",M); C = (unsigned short ) farcalloc(M, sizeof(unsigned short)); if (C==NULL) { printf("\n fail to getspace for C m = %ld\n",M); exit(1); } / printf("created C %ld\n",farcoreleft()); gets(string); / BIG_ZERO(C,M); C[0] = 4; / printf("zeroed C %ld\n",farcoreleft()); gets(string); / i=p-2; } else { fscanf(last,"%D %d %D %D",&p,&split,&i,&j); printf("\nsplit = %d\n p= %ld i= %ld\n",split,p,i); M = 8 sizeof(unsigned short); M = (p+M-1)/M; if (j!=M) { printf("error old M %ld != %ld\n",j,M); abort(); } printf("M= %ld\n",M); C = (unsigned short ) farcalloc(M, sizeof(unsigned short)); if (C==NULL) { printf("\n fail to getspace for C m = %ld\n",M); exit(1); } for (j--;j>=0;j--) { fscanf(last,"%4x",&temp); C[j]= temp; } } fclose(last); / printf("last closed i = %ld %ld\n",i,farcoreleft()); gets(string); / B = (unsigned short ) farcalloc(2M, sizeof(unsigned short)); if (B==NULL) { printf("\n fail to getspace for B m = %ld\n",M); exit(1); } / printf("created D %ld\n",farcoreleft()); gets(string); / #endif #ifdef short_test for(p=2; p<ARRAY_SIZE; p++) { while (flags[p]) { p++; } M = 8 sizeof(unsigned short); M = (p+M-1)/M; B = (unsigned short ) farcalloc(2M, sizeof(unsigned short)); if (B==NULL) { printf("\n fail to getspace for B m = %ld\n",M); exit(1); } C = (unsigned short ) farcalloc(M, sizeof(unsigned short)); if (C==NULL) { printf("\n fail to getspacQRe for C m = %ld\n",M); exit(1); } BIG_ZERO(C,M); C[0] = 4; i=p-2; #else { #endif stimer=clock(); if (stimer&0x80000000) stimer=0; / printf("ready to g i = %ld %ld\n",i,farcoreleft()); gets(string); / while (i>0) { strassen_squ(B, C, M); fast_mod_2_to_p_minus_1(C, B, p); #ifndef short_test / timer=clock(); printf("i = %ld time %ld C[M-1] %d\n",i,timer-stimer,C[M-1]); */ if ((i % 1024)==0) { timer=clock(); if ((last= fopen("lucas.log","r+"))==NULL) { printf("cannot reopen lucas.log\n"); abort(); } fprintf(last,"%ld %d %ld %ld\n",p,split,i-1,M); for (j=M-1;j>=0;j--) fprintf(last,"%04x ",C[j]); fclose(last); printf("i = %ld time %ld\n",i,timer-stimer); } #endif i--; } if (BIG_LENW(C,M) < 1) { printf("Mersenne number %lu\n", p); timer=clock(); printf("time %ld\n",timer-stimer); } farfree(C); farfree(B); } return 0; }
2.45	core.c for data > 64k	RDVAX::GRIES		`Fri May 15 1992 19:42`	2669
	#define LINT_ARGS 1 #include <stdio.h> #include <string.h> #include <stdlib.h> #ifdef vms #include "alloc.h" #endif #undef stack_mem /#define stack_mem 1/ #ifdef __MSDOS__ #define inline 1 #include <alloc.h> #endif #include "core.h" /#define mar 1/ unsigned split = 64; long zero = 0; #define SIZE_SHORT 16 unsigned print_flag = 0; unsigned BIG_ERRCODE = 0; void BIG_ERROR(unsigned count, char S) { BIG_ERRCODE= count; printf("%d \n",count); puts(S); printf("\n"); } #ifdef stack_mem unsigned short stack; long top_stack = 0, stack_left = 0; #endif long set_stack (unsigned long size) { #ifdef stack_mem if (stack != NULL) farfree(stack); top_stack = 0; stack = (unsigned short ) farmalloc (sizeof (unsigned short) size); if (stack != NULL) { stack_left = size; } else { stack_left = -1; printf("Allocation failed\n"); } return (long) stack; #else return 1; #endif } void reset_stack (unsigned long size) { #ifdef stack_mem if (size != top_stack) { #ifdef DEBUG printf ("reset_stack size: %ld != top_stack: %ld \n", size, top_stack); #endif } top_stack = 0; farfree (stack); stack_left = 0; #endif } unsigned short * BIG_ALLOC(unsigned long size) { unsigned short p; / if (print_flag) printf("\nBIG_ALLOC(%ld)",size);/ #ifdef stack_mem if (stack==NULL) set_stack(10000); if (stack_left >= size) { top_stack = top_stack + size; stack_left = stack_left - size; return &stack[top_stack - size]; } BIG_ERROR(0,"ALLOC failed"); return NULL; #else p= (unsigned short ) farmalloc (sizeof (unsigned short) * size); if (p==NULL) BIG_ERROR(0,"ALLOC failed"); return p; #endif } void BIG_FREE(unsigned short A) { #ifdef stack_mem long lo,hi,current; current= top_stack; hi= top_stack; lo= 0; do { if (A >= &stack[current]) lo= current; else hi= current; current= (hi + lo)/2; } while (lo<current); if (A != &stack[current]) { printf("current = %ld top_stack= %ld \n",current,top_stack); printf("A = %Fp &stack[current]= %Fp \n",A,&stack[current]); BIG_ERROR(0,"Free failed"); } stack_left = stack_left + (top_stack - current); top_stack = current; #else farfree(A); #endif } unsigned short_log2(unsigned long i) { unsigned shift = 8; unsigned exp = 16; unsigned long two = 65535; do { if (two >= i) { two >>= shift; exp -= shift; } else { two= two \| (two << shift); exp += shift; } shift >>= 1; } while (shift); if (two >= i) { exp -= 1; } return (exp); } unsigned BIG_LENGTH(unsigned short A, unsigned long N) { register unsigned long i; if (N==0) return(1); /* length of 0 or -1 / for ( i=N-1; i>0 && A[i]==0; i--); return(16i + short_log2(A[i])); } void BIG_CONST(unsigned short A,unsigned short V, unsigned long N) / INITIALIZE BIG A TO VALUE unsigned V / { register unsigned long i; unsigned signword = ( ((int)V) >= 0 ? 0 : ~0); A[0] = V; for (i=1; i<N; i++) A[i] = signword; } int BIG_CMP(unsigned short A,unsigned short B,unsigned long N) / RETURNS SIGN OF A-B / { register unsigned long i; if (N == 0) return(0); for (i=N-1; i>0 && A[i] == B[i]; i--); if (A[i]==B[i]) return 0; if (A[i] > B[i]) return(1); return(-1); } / Macros for portability / #ifdef inline #pragma #endif #define WMASK 0xFFFF void BIG_ZERO (unsigned short A,unsigned long N) { #ifdef vms ots$move5(zero, (unsigned char )&zero, (unsigned char)zero, N sizeof(unsigned short), A); #else register unsigned long i; // memset( (char )A, (int)zero, (int)(N sizeof(unsigned short)) ); for (i=0; i<N; i++) A[i] = 0; #endif } void BIG_COPY (unsigned short A,unsigned short B,unsigned long N) { #ifdef vms ots$move3(N * sizeof(unsigned short), B, A); #else register unsigned long i; // memcpy( (char )A, (char )B, (int)(N * sizeof(unsigned short)) ); for (i=0; i<N; i++) A[i] = B[i]; #endif } unsigned short BIG_LEFT_SHIFT (unsigned short A,unsigned short B, unsigned SHIFT,unsigned long N) { register long i; unsigned long carry = 0L; /* carry to start / for (i=0;i<N;i++) { carry= ((unsigned long) B[i] << SHIFT) + (carry >> 16); A[i]= (unsigned short) carry; } return (unsigned short) (carry >> 16); } unsigned short BIG_SMOD (unsigned short A,unsigned short V,unsigned long N) { register long i; unsigned long R = 0L; if (V==0) { BIG_ERROR(11,"Divide Error"); return (0); } for (i=N-1;i>=0;i--) { R = (R<< 16)+(unsigned long)A[i]; R = R % (unsigned long) V; } return ((unsigned short) R); } unsigned short BIG_SDIV (unsigned short Q, unsigned short A, unsigned short V, unsigned long N) { register long i; unsigned long R = 0L; if (V==0) { BIG_ERROR(11,"Divide Error"); return (0); } for (i=N-1;i>=0;i--) { R = (R<< 16)+(unsigned long)A[i]; Q[i]= R/V; R = R % (unsigned long) V; } return ((unsigned short) R); } /***************************************************************************/ / from here on we assume that arguments are unsigned / /**************************************************************************/ unsigned long BIG_LENW (unsigned short A,unsigned long N) { register unsigned long i; if (N==0) return 1; for ( i=N-1; i>0 && A[i]==0; i--); if (A[i]) return (i+1); return i; } unsigned short RESULT, MULITPLIER; unsigned long BIG_ACC ( unsigned short B, unsigned short C, unsigned long N); #ifdef mar unsigned long L_ACC ( unsigned long B, unsigned short C, unsigned long N); unsigned long L_DCC (unsigned short A, unsigned long B, unsigned short C, unsigned long N); unsigned long L_SCALE (unsigned short A, unsigned long B, unsigned shift, unsigned big); unsigned long N_SCALE (unsigned short A, unsigned long B, unsigned shift, unsigned big); unsigned long BIG_PART_MPY (unsigned short A, unsigned short B, unsigned short C, unsigned long N) / A = B * C / { register long i=0L; register unsigned long result = 0L; RESULT= A; if (N & 1L) { result = (unsigned long) A[N] + BIG_ACC (B[0],C,N); A[N] = (unsigned short) result; result = result >> 16; i= 1; } for (;i<N-1;i=i+2) { result += (unsigned long) A[N+i]; A[N+i] = (unsigned short) result; result = result >> 16; result += (unsigned long) A[N+i+1]; A[N+i+1] = (unsigned short) result; result = result >> 16; RESULT= &A[i]; result += L_ACC ( (unsigned long) B[i] + ((unsigned long) B[i+1] << 16),C,N); } return ((unsigned long)result); } unsigned long B_PART_MPY (unsigned short A, unsigned short B, unsigned short C, unsigned long M, unsigned long N) /* A = B * C / { register long i=0L; register unsigned long result = 0L; RESULT= A; if (M & 1L) { result = (unsigned long) A[N] + BIG_ACC (B[0],C,N); A[N] = (unsigned short) result; result = result >> 16; i= 1; } for (;i<M-1;i=i+2) { result += (unsigned long) A[N+i]; A[N+i] = (unsigned short) result; result = result >> 16; result += (unsigned long) A[N+i+1]; A[N+i+1] = (unsigned short) result; result = result >> 16; RESULT= &A[i]; result += L_ACC ( (unsigned long) B[i] + ((unsigned long) B[i+1] << 16),C,N); } return ((unsigned long)result); } unsigned long L_ADD (unsigned short A, unsigned short B, unsigned short carry_in, long N); unsigned long L_INC (unsigned short A, unsigned short B, long N); void BIG_PSQ (unsigned short A,unsigned short B,unsigned long N) { register long i=0L; unsigned long result = 0L; #ifdef vms ots$move5(zero, (unsigned char )&zero, (unsigned char)zero, (N+N) sizeof(unsigned short), A); #else BIG_ZERO (A,N+N); #endif if (N & 1L) { RESULT= &A[1]; A[N] = BIG_ACC (B[0],&B[1],N-1); i= 1; } for (;i<N-1;i=i+2) { RESULT= &A[i+i+2]; A[N+i+2]= L_ACC ( (unsigned long) B[i] + ((unsigned long) B[i+1] << 16), &B[i+2],N-i-2); } L_ADD (A,A,0,N+N); i= 0; if (N & 1L) { result = ((unsigned long)B[0]) * ((unsigned long)B[0]); result += (unsigned long) A[0]; A[0] = (unsigned short) result; result = result >> 16; result += (unsigned long) A[1]; A[1] = (unsigned short) result; result = result >> 16; i= 1; } for (;i<N;i=i+2) /* add in trace B[i] * B[i] / { if (result) result= L_INC (&A[i+i],result,4); RESULT= &A[i+i]; result+= L_ACC ( (unsigned long) B[i] + ((unsigned long) B[i+1] << 16), &B[i],2); } / A[i+i+2] = (unsigned short) result; / } void s_mod(unsigned short Q, unsigned short C, unsigned j, unsigned k) { register unsigned long result= 0L; register unsigned long scale,div_hold,dem; unsigned short save,save1; unsigned long i,m,big; if (j-k>=0) { if (k) { save1= Q[j+2]; save= Q[j+1]; Q[j+1]= 0; Q[j+2]= 0; dem= ((unsigned long) C[k] <<16) + (unsigned long) C[k-1]; m= j-k; if ((m & 1)==0) { scale= L_SCALE (&Q[j+3],dem,0,&big); if (scale) { result= L_DCC(&Q[m],scale,C,k+1); } m= m-1; }; for (;m>=1;m=m-2) { if ( (short) result >= 0 ) { scale= L_SCALE (&Q[m+k+2],dem,0,&big); if (big) { if (scale) { L_SUB(&Q[m+1],C,0,k+1); result= Q[m+k+1]; if ( (short) result >= 0 ) scale= L_SCALE (&Q[m+k+2],dem,0,&big); else scale= 0; } else scale= scale-1L; } if (scale) { result= L_DCC(&Q[m-1],scale,C,k+1); } } else { scale= N_SCALE (&Q[m+k+2],dem,0,&big); if (big) { if (scale) { L_ADD(&Q[m+1],C,0,k+1); result= Q[m+k+1]; if ( (short) result < 0 ) scale= N_SCALE (&Q[m+k+2],dem,0,&big); else scale= 0; } else scale= scale-1L; } if (scale) { RESULT= &Q[m-1]; result= 0xFFFFFFFFL +(unsigned long) L_ACC(scale,C,k+1); } scale= -scale; Q[m+k+2]= 0; Q[m+k+3]= 0; } } if ( (short) Q[k+1] < 0 ) { do { Q[k+1]+= (unsigned short)L_ADD(Q,C,0,k+1); } while ( (short) Q[k+1] < 0 ); Q[k+2]= 0; Q[k+3]= 0; } else { result= ((unsigned long) Q[k] << 16) + (unsigned long) Q[k-1]; if (result >= dem) { do { result= L_SUB(Q,C,0,k+1); } while ( result !=0 ); L_ADD(Q,C,0,k+1); } } Q[j+1]= save; Q[j+2]= save1; } else / k==0 / { result= BIG_SMOD(Q,C[0],j+1); for (i=1; i<=j; i++) Q[i] = 0; Q[0]= (unsigned short) result; } } } void t_mod(unsigned short Q, unsigned short C, unsigned j, unsigned k) { register unsigned long result= 0L; register unsigned long scale,div_hold,dem; unsigned short save,save1; unsigned long i,m,mem,big; if (j-k>=0) { if (k) { save1= Q[j+2]; save= Q[j+1]; Q[j+1]= 0; Q[j+2]= 0; mem= 0; dem= ((unsigned long) C[k] <<16) + (unsigned long) C[k-1]; if ((dem & 0x80000000L)==0) { mem= 15-short_log2(dem >> 16); dem= (dem << mem) + (C[k-2] >> 16-mem); } m= j-k; if ((m & 1)==0) { scale= L_SCALE (&Q[j+3],dem,mem,&big); if (scale) { result= L_DCC(&Q[m],scale,C,k+1); } m= m-1; }; for (;m>=1;m=m-2) { if ( (short) result >= 0 ) { scale= L_SCALE (&Q[m+k+2],dem,mem,&big); if (big) { if (scale) { L_SUB(&Q[m+1],C,0,k+1); result= Q[m+k+1]; if ( (short) result >= 0 ) scale= L_SCALE (&Q[m+k+2],dem,mem,&big); else scale= 0; } else scale= scale-1L; } if (scale) { result= L_DCC(&Q[m-1],scale,C,k+1); } } else { scale= N_SCALE (&Q[m+k+2],dem,mem,&big); if (big) { if (scale) { L_ADD(&Q[m+1],C,0,k+1); result= Q[m+k+1]; if ( (short) result < 0 ) scale= N_SCALE (&Q[m+k+2],dem,mem,&big); else scale= 0; } else scale= scale-1L; } if (scale) { RESULT= &Q[m-1]; result= 0xFFFFFFFFL +(unsigned long) L_ACC(scale,C,k+1); } scale= -scale; Q[m+k+2]= 0; Q[m+k+3]= 0; } } if ( (short) Q[k+1] < 0 ) { do { Q[k+1]+= (unsigned short)L_ADD(Q,C,0,k+1); } while ( (short) Q[k+1] < 0 ); Q[k+2]= 0; Q[k+3]= 0; } else { result= ((unsigned long) Q[k] << 16) + (unsigned long) Q[k-1]; if (mem) { result= (result << mem) + (unsigned long) (Q[k-2] >> 16-mem); } if (result >= dem) { do { result= L_SUB(Q,C,0,k+1); } while ( result !=0 ); L_ADD(Q,C,0,k+1); } } Q[j+1]= save; Q[j+2]= save1; } else / k==0 / { result= BIG_SMOD(Q,C[0],j+1); for (i=1; i<=j; i++) Q[i] = 0; Q[0]= (unsigned short) result; } } } void t_div(unsigned short Q, unsigned short D , unsigned short C, unsigned j, unsigned k) { register unsigned long result= 0L; register unsigned long scale,div_hold,dem; unsigned short save,save1; unsigned long i,m,mem,big; if (j-k>=0) { if (k) { save1= D[j+2]; save= D[j+1]; D[j+1]= 0; D[j+2]= 0; mem= 0; dem= ((unsigned long) C[k] <<16) + (unsigned long) C[k-1]; if ((dem & 0x80000000L)==0) { mem= 15-short_log2(dem >> 16 ); dem= (dem << mem) + (C[k-2] >> 16-mem); } m= j-k; if ((m & 1)==0) { scale= L_SCALE (&D[j+3],dem,mem,&big); if (scale) { result= L_DCC(&D[m],scale,C,k+1); } Q[m]= (unsigned short) (scale); m= m-1; }; for (;m>=1;m=m-2) { if ( (short) result >= 0 ) { scale= L_SCALE (&D[m+k+2],dem,mem,&big); if (big) { if (scale) { L_INC(&Q[m+1],1,1+j-(k+m)); L_SUB(&D[m+1],C,0,k+1); result= D[m+k+1]; if ( (short) result >= 0 ) scale= L_SCALE (&D[m+k+2],dem,mem,&big); else scale= 0; } else scale= scale-1L; } if (scale) { result= L_DCC(&D[m-1],scale,C,k+1); } Q[m]= (unsigned short) (scale >> 16); Q[m-1]= (unsigned short) (scale); } else { scale= N_SCALE (&D[m+k+2],dem,mem,&big); /* printf("\nscale = %0lx big = %0lx \n",scale,big); / if (big) { if (scale) { L_DEC(&Q[m+1],1,1+j-(k+m)); L_ADD(&D[m+1],C,0,k+1); result= D[m+k+1]; if ( (short) result < 0 ) scale= N_SCALE (&D[m+k+2],dem,mem,&big); else scale= 0; } else scale= scale-1L; } if (scale) { L_DEC(&Q[m+1],1,1+j-(k+m)); RESULT= &D[m-1]; result= 0xFFFFFFFFL +(unsigned long) L_ACC(scale,C,k+1); } scale= -scale; Q[m]= (unsigned short) (scale >> 16); Q[m-1]= (unsigned short) (scale); D[m+k+2]= 0; D[m+k+3]= 0; } / printf("\nscale = %0lx \n",scale); for (i= -2;i<=k+1;i++) printf("%0lx",D[m+k-i]); printf("\n");/ } if ( (short) D[k+1] < 0 ) { do { D[k+1]+= (unsigned short)L_ADD(D,C,0,k+1); L_DEC(Q,1,1+j-k); } while ( (short) D[k+1] < 0 ); D[k+2]= 0; D[k+3]= 0; } else { result= ((unsigned long) D[k] << 16) + (unsigned long) D[k-1]; if (mem) { result= (result << mem) + (unsigned long) (D[k-2] >> 16-mem); } if (result >= dem) { result= L_SUB(D,C,0,k+1); if ( result ==0 ) L_ADD(D,C,0,k+1); else L_INC(Q,1,1+j-k); } } D[j+1]= save; D[j+2]= save1; } else / k==0 / { result= BIG_SDIV(Q,D,C[0],j+1); for (i=1; i<=j; i++) D[i] = 0; D[0]= (unsigned short) result; } } } #else unsigned long BIG_ACC ( unsigned short B, unsigned short C, unsigned long N) { #ifdef inline unsigned short result = 0; if (!B) return (0); asm push ds; asm les di, RESULT; asm lds si, C; asm mov bx,0; asm mov cx,B; BIG_ACC_LOOP: asm mov ax,cx; asm mul WORD PTR [bx+si]; asm add ax, result; asm adc dx, 0; asm add WORD PTR es:[bx+di],ax; asm adc dx, 0; asm mov result,dx; asm add bx,2; asm mov dx, WORD PTR [N]; asm shl dx,1; asm cmp bx,dx; asm jl BIG_ACC_LOOP; asm pop ds; return result; #else register unsigned long result = 0L; register long i; if (B==0) return (0); for (i=0;i<N;i++) { result += B * ((unsigned long) (C+i)); result += ((unsigned long) RESULT[i]); RESULT[i] = (unsigned short) result; result = result >> 16; } return ((unsigned short)result); #endif } unsigned long BIG_DCC (unsigned short A, unsigned short B, unsigned short C, unsigned long N) { unsigned long result = 1L; unsigned long div_hold = 0L; unsigned long i; #ifdef inline asm push ds; asm les di, A; asm lds si, C; asm mov bx,0; BIG_DCC_LOOP: asm mov ax,B; asm mul WORD PTR [bx+si]; asm add ax, WORD PTR [div_hold]; asm adc dx, 0; asm mov WORD PTR [div_hold],dx; asm xor dx, dx; asm not ax; asm mov cx, WORD PTR [result]; asm add cx, WORD PTR es:[bx+di]; asm adc dx,0 asm add cx, ax asm adc dx,0 asm mov WORD PTR es:[bx+di], cx; asm mov WORD PTR [result],dx; asm add bx,2; asm mov dx, WORD PTR [N]; asm shl dx,1; asm cmp bx,dx; asm jl BIG_DCC_LOOP; asm mov ax, WORD PTR [div_hold]; asm xor dx, dx; asm not ax; asm mov cx, WORD PTR [result]; asm add cx, WORD PTR es:[bx+di]; asm adc dx,0 asm add cx, ax asm adc dx,0 asm mov WORD PTR es:[bx+di], cx; asm sub dx, 1; asm mov WORD PTR [result],dx; asm mov WORD PTR [result+2],dx; asm pop ds; #else for (i=0;i<N;i++) { div_hold+= (unsigned long) B (unsigned long) C[i]; result += (unsigned long) A[i]; result += ((unsigned short) (~ (div_hold) & WMASK)); A[i] = (unsigned short) result; result = result >> 16; div_hold = div_hold >> 16; } result += (unsigned long) A[N]; result += ((unsigned short) (~ (div_hold) & WMASK)); A[N] = (unsigned short) result; result= (result>>16)-1L; #endif return(result); } unsigned long L_ADD (unsigned short A, unsigned short B, unsigned short carry_in, unsigned long N) { #ifdef inline1 asm push ds; asm push es; asm les di, A; asm lds si, B; asm mov bx,0; asm mov ax,carry_in; asm mov dx, WORD PTR [N]; asm mov cx, dx asm shl dx,1; asm and cx, 3; asm jz L_ADD_0; asm sub cx, 2 asm jz L_ADD_2; asm jl L_ADD_1; asm L_ADD_3: asm xor cx,cx; asm add ax, WORD PTR [bx+si]; asm adc cx, 0; asm add WORD PTR es:[bx+di],ax; asm adc cx, -1 asm mov cx, 0; asm mov bx,-2; asm jmp L_ADD_LOOP_3; L_ADD_2: asm xor cx, cx; asm add ax, WORD PTR [bx+si]; asm adc cx, 0; asm add WORD PTR es:[bx+di],ax; asm adc cx, -1 asm mov cx, 0; asm mov bx,-4; asm jmp L_ADD_LOOP_2; L_ADD_1: asm xor cx,cx; asm add ax, WORD PTR [bx+si]; asm adc cx, 0; asm add WORD PTR es:[bx+di],ax; asm adc cx, 0; asm mov bx,-6; asm jmp L_ADD_LOOP_1; L_ADD_0: asm cmp bx,dx; asm jge L_ADD_EXIT; asm xor cx,cx; asm add ax, WORD PTR [bx+si]; asm adc cx, 0; asm add WORD PTR es:[bx+di],ax; asm adc cx, -1 asm mov cx, 0; asm jmp L_ADD_LOOP_0; L_ADD_LOOP: asm add cx, -1; asm mov cx, 0; asm mov ax, WORD PTR [bx+si]; asm adc WORD PTR es:[bx+di],ax; L_ADD_LOOP_0: asm mov ax, WORD PTR [bx+si+2]; asm adc WORD PTR es:[bx+di+2],ax; L_ADD_LOOP_3: asm mov ax, WORD PTR [bx+si+4]; asm adc WORD PTR es:[bx+di+4],ax; L_ADD_LOOP_2: asm mov ax, WORD PTR [bx+si+6]; asm adc WORD PTR es:[bx+di+6],ax; asm adc cx, 0; L_ADD_LOOP_1: asm add bx,8; asm cmp bx,dx; asm jl L_ADD_LOOP; L_ADD_EXIT: asm pop es; asm pop ds; return ((long)_CX); #else long t; unsigned long i; t = (unsigned long) carry_in << 16; for (i=0; i<N; i++) { t= (unsigned long)A[i] + (unsigned long)B[i] + (unsigned long)(t>>16); A[i] = (unsigned short) t; } t= t >> 16; return (t); #endif } unsigned long L_INC (unsigned short A, unsigned short B, unsigned long N) { long t; unsigned long i; #ifdef inline1 asm push ds; asm les di, A; asm mov bx,0; asm mov ax,B; asm mov dx, WORD PTR [N]; asm mov cx, dx asm shl dx,1; asm and cx, 3; asm jz L_INC_0; asm sub cx, 2 asm jz L_INC_2; asm jl L_INC_1; asm L_INC_3: asm xor cx,cx; asm add WORD PTR es:[bx+di],ax; asm mov bx,-2; asm jmp L_INC_LOOP_3; L_INC_2: asm xor cx, cx; asm add WORD PTR es:[bx+di],ax; asm mov bx,-4; asm jmp L_INC_LOOP_2; L_INC_1: asm xor cx,cx; asm add WORD PTR es:[bx+di],ax; asm adc cx, 0; asm mov bx,-6; asm jmp L_INC_LOOP_1; L_INC_0: asm cmp bx,dx; asm jge L_INC_EXIT; asm xor cx,cx; asm add WORD PTR es:[bx+di],ax; asm jmp L_INC_LOOP_0; L_INC_LOOP: asm add WORD PTR es:[bx+di],cx; L_INC_LOOP_0: asm adc WORD PTR es:[bx+di+2],0; L_INC_LOOP_3: asm adc WORD PTR es:[bx+di+4],0; L_INC_LOOP_2: asm adc WORD PTR es:[bx+di+6],0; asm mov cx, 0; asm adc cx, 0; L_INC_LOOP_1: asm jz L_INC_EXIT; asm add bx,8; asm cmp bx,dx; asm jl L_INC_LOOP; L_INC_EXIT: asm pop ds; return((long) _CX); #else t = (unsigned long) B; for (i=0; i<N && t; i++) { t= (unsigned long)A[i] + t; A[i] = (unsigned short) t; t= t >> 16; } return (t); #endif } unsigned long L_DEC (unsigned short A, unsigned short B, unsigned long N) { #ifdef inline1 asm push ds; asm les di, A; asm mov bx,0; asm mov ax,B; asm mov dx, WORD PTR [N]; asm mov cx, dx asm shl dx,1; asm and cx, 3; asm jz L_DEC_0; asm sub cx, 2 asm jz L_DEC_2; asm jl L_DEC_1; asm L_DEC_3: asm sub WORD PTR es:[bx+di],ax; asm mov bx,-2; asm jmp L_DEC_LOOP_3; L_DEC_2: asm sub WORD PTR es:[bx+di],ax; asm mov bx,-4; asm jmp L_DEC_LOOP_2; L_DEC_1: asm xor cx,cx; asm sub WORD PTR es:[bx+di],ax; asm adc cx, 0; asm mov bx,-6; asm jmp L_DEC_LOOP_1; L_DEC_0: asm cmp bx,dx; asm jge L_DEC_EXIT; asm sub WORD PTR es:[bx+di],ax; asm jmp L_DEC_LOOP_0; L_DEC_LOOP: asm sub WORD PTR es:[bx+di],cx; L_DEC_LOOP_0: asm sbb WORD PTR es:[bx+di+2],0; L_DEC_LOOP_3: asm sbb WORD PTR es:[bx+di+4],0; L_DEC_LOOP_2: asm sbb WORD PTR es:[bx+di+6],0; asm mov cx, 0; asm adc cx, 0; L_DEC_LOOP_1: asm jz L_DEC_EXIT; asm add bx,8; asm cmp bx,dx; asm jl L_DEC_LOOP; L_DEC_EXIT: asm pop ds; return((long)_CX); #else long t; unsigned long i; if (A[0] <B) { A[0]= A[0]-B; for (i=1;(i<N-1) && (A[i]==0);i++) A[i]--; if (i==N-1) return 1; A[i]--; return 0; } else A[0]= A[0]-B; return (0); #endif } unsigned long L_SUB (unsigned short A, unsigned short B, unsigned short carry_in, unsigned long N) { #ifdef inline1 asm push ds; asm push es; asm push di; asm push si; asm les di, A; asm lds si, B; asm mov bx,0; asm mov ax,carry_in; asm mov dx, WORD PTR [N]; asm mov cx, dx asm shl dx,1; asm and cx, 3; asm jz L_SUB_0; asm sub cx, 2 asm jz L_SUB_2; asm jl L_SUB_1; asm L_SUB_3: asm xor cx,cx; asm add ax, WORD PTR [bx+si]; asm adc cx, 0; asm sub WORD PTR es:[bx+di],ax; asm adc cx, -1 asm mov cx, 0; asm mov bx,-2; asm jmp L_SUB_LOOP_3; L_SUB_2: asm xor cx, cx; asm add ax, WORD PTR [bx+si]; asm adc cx, 0; asm sub WORD PTR es:[bx+di],ax; asm adc cx, -1 asm mov cx, 0; asm mov bx,-4; asm jmp L_SUB_LOOP_2; L_SUB_1: asm xor cx,cx; asm add ax, WORD PTR [bx+si]; asm adc cx, 0; asm sub WORD PTR es:[bx+di],ax; asm adc cx, 0; asm mov bx,-6; asm jmp L_SUB_LOOP_1; L_SUB_0: asm cmp bx,dx; asm jge L_SUB_EXIT; asm xor cx,cx; asm add ax, WORD PTR [bx+si]; asm adc cx, 0; asm sub WORD PTR es:[bx+di],ax; asm adc cx, -1 asm mov cx, 0; asm jmp L_SUB_LOOP_0; L_SUB_LOOP: asm add cx, -1 asm mov cx, 0; asm mov ax, WORD PTR [bx+si]; asm sbb WORD PTR es:[bx+di],ax; L_SUB_LOOP_0: asm mov ax, WORD PTR [bx+si+2]; asm sbb WORD PTR es:[bx+di+2],ax; L_SUB_LOOP_3: asm mov ax, WORD PTR [bx+si+4]; asm sbb WORD PTR es:[bx+di+4],ax; L_SUB_LOOP_2: asm mov ax, WORD PTR [bx+si+6]; asm sbb WORD PTR es:[bx+di+6],ax; asm adc cx, 0; L_SUB_LOOP_1: asm add bx,8; asm cmp bx,dx; asm jl L_SUB_LOOP; L_SUB_EXIT: asm pop si; asm pop di; asm pop es; asm pop ds; asm xor cx, 1; return((long)_CX); #else long t= 0L; unsigned long i; if (carry_in==0) t = 1L; for (i=0;i<N;i++) { t += ((unsigned long) A[i]) + ((unsigned long) (~B[i] & 0xFFFF )); A[i] = (unsigned short) t; t = t >> 16; } return t; #endif } unsigned short BIG_PSQ (unsigned short A,unsigned short B,unsigned long N) /* uses the fact that (a+b)2 = a2 +2ab + b*2 for three vs four muls / { register unsigned long i; unsigned long result = 0L; #ifdef vms ots$move5(zero, (unsigned char )&zero, (unsigned char)zero, (N+N) sizeof(unsigned short), A); #else BIG_ZERO (A,N+N); #endif RESULT= &A[1]; for (i=0;i<N-1;i++) { A[N+i] = BIG_ACC (B[i],&B[i+1],N-i-1); RESULT+= 2; } L_ADD (A,A,0,N+N); for (i=0;i<N;i++) /* add in B[i] * B[i] / { result += ((unsigned long)B[i]) ((unsigned long)B[i]); result += (unsigned long) A[i+i]; A[i+i] = (unsigned short) result; result = result >> 16; result += (unsigned long) A[i+i+1]; A[i+i+1] = (unsigned short) result; result = result >> 16; } A[i+i] = (unsigned short) result; return (unsigned short) (result >> 16); } unsigned long BIG_PART_MPY (unsigned short A, unsigned short B, unsigned short C, unsigned long N) / A = B * C / { register long i; register unsigned long result = 0L; RESULT= A; for (i=0;i<N;i++) { result += BIG_ACC (B[i],C,N); result += A[N+i]; A[N+i] = (unsigned short) result; result = result >> 16; RESULT++; } return ((unsigned long)result); } unsigned long B_PART_MPY (unsigned short A, unsigned short B, unsigned short C, unsigned long M, unsigned long N) /* A = B * C / { register long i; register unsigned long result = 0L; RESULT= A; for (i=0;i<M;i++) { result += BIG_ACC (B[i],C,N); result += A[N+i]; A[N+i] = (unsigned short) result; result = result >> 16; RESULT++; } return ((unsigned long)result); } void t_mod(unsigned short Q, unsigned short C, unsigned j, unsigned k) { register unsigned long result= 0L; register unsigned long scale,div_hold,temp,dem,b; unsigned short save, a; unsigned i,m,mem; if (j>=k) { if (k) { save= Q[j+1]; Q[j+1]= 0; mem= 0; dem= (unsigned long) C[k]; if (dem < 0x8000) { mem= 15-short_log2(dem); dem= (unsigned long) C[k-1]+ (dem << 16); dem= dem >> 16-mem; } for (m= j-k+1;m>0;m--) { temp = ( (unsigned long) Q[m+k] << 16) + (unsigned long) Q[m+k-1]; if (mem) { temp= (temp << mem) + (unsigned long) (Q[m+k-2] >> 16-mem); } if ( (short) result >= 0 ) { #ifdef inline asm mov dx, WORD PTR [temp+2]; asm xor bx, bx; asm mov ax, WORD PTR [temp]; asm mov cx, WORD PTR [dem]; asm cmp dx, cx; asm jb not_big; asm sub dx, cx; asm mov bx, 1; not_big: asm mov WORD PTR [scale+2], bx asm div cx; asm mov WORD PTR [scale], ax; #else scale= (unsigned long) temp / dem; #endif if (scale) { if (scale >=0x10000) { scale = scale & 0xFFFF; if (scale) { L_SUB(&Q[m],C,0,k+1); result= Q[m+k]; if ( (short) result >= 0 ) { temp = ( (unsigned long) Q[m+k] << 16) + (unsigned long) Q[m+k-1]; if (mem) { temp= (temp << mem) + (unsigned long) (Q[m+k-2] >> 16-mem); } #ifdef inline asm mov dx, WORD PTR [temp+2]; asm xor bx, bx; asm mov ax, WORD PTR [temp]; asm mov cx, WORD PTR [dem]; asm cmp dx, cx; asm jb not_big_1; asm sub dx, cx; asm mov bx, 1; not_big_1: asm mov WORD PTR [scale+2], bx asm div cx; asm mov WORD PTR [scale], ax; #else scale= (unsigned long) temp / dem; #endif } else scale= 0; } else scale= scale-1L; } if (scale) /* result= BIG_DCC(&Q[m],(unsigned short)scale,C,k+1);/ { div_hold= 0; result= 1L; a= &Q[m-1]; #ifdef inline asm push ds; asm les di, a; asm lds si, C; asm mov bx,0; TMOD_DCC_LOOP: asm mov ax,WORD PTR [scale]; asm mul WORD PTR [bx+si]; asm add ax, WORD PTR [div_hold]; asm adc dx, 0; asm mov WORD PTR [div_hold],dx; asm xor dx, dx; asm not ax; asm mov cx, WORD PTR [result]; asm add cx, WORD PTR es:[bx+di]; asm adc dx,0 asm add cx, ax asm adc dx,0 asm mov WORD PTR es:[bx+di], cx; asm mov WORD PTR [result],dx; asm add bx,2; asm mov dx, k; asm shl dx,1; asm cmp bx,dx; asm jle TMOD_DCC_LOOP; asm mov ax, WORD PTR [div_hold]; asm xor dx, dx; asm not ax; asm mov cx, WORD PTR [result]; asm add cx, WORD PTR es:[bx+di]; asm adc dx,0 asm add cx, ax asm adc dx,0 asm mov WORD PTR es:[bx+di], cx; asm sub dx, 1; asm mov WORD PTR [result],dx; asm mov WORD PTR [result+2],dx; asm pop ds; #else b= scale & WMASK; for (i=0;i<k+1;i++) { div_hold+= b (unsigned long) C[i]; result += (unsigned long) a[i] + (unsigned long) ((unsigned short) (~div_hold)); a[i] = (unsigned short) result; result = result >> 16; div_hold = div_hold >> 16; } result += (unsigned long) a[k+1]; result += (unsigned long) ((unsigned short) (~div_hold)); a[k+1] = (unsigned short) result; result= (result>>16)-1L; #endif } } } else { temp= -temp; #ifdef inline asm mov dx, WORD PTR [temp+2]; asm xor bx, bx; asm mov ax, WORD PTR [temp]; asm mov cx, WORD PTR [dem]; asm cmp dx, cx; asm jb not_big_2; asm sub dx, cx; asm mov bx, 1; not_big_2: asm mov WORD PTR [scale+2], bx asm div cx; asm mov WORD PTR [scale], ax; #else scale= temp / dem; #endif if (scale) { if (scale >=0x10000) { scale = scale & 0xFFFF; if (scale) { L_ADD(&Q[m],C,0,k+1); result= Q[m+k]; if ( (short) result < 0 ) { temp = ( (unsigned long) Q[m+k] << 16) + (unsigned long) Q[m+k-1]; if (mem) { temp= (temp << mem) + (unsigned long) (Q[m+k-2] >> 16-mem); } temp= -temp; #ifdef inline asm mov dx, WORD PTR [temp+2]; asm xor bx, bx; asm mov ax, WORD PTR [temp]; asm mov cx, WORD PTR [dem]; asm cmp dx, cx; asm jb not_big_3; asm sub dx, cx; asm mov bx, 1; not_big_3: asm mov WORD PTR [scale+2], bx asm div cx; asm mov WORD PTR [scale], ax; #else scale= (unsigned long) temp / dem; #endif } else scale= 0; } else scale= scale-1L; } if (scale) { result= Q[m+k]; RESULT= &Q[m-1]; result+= (unsigned long) BIG_ACC(scale,C,k+1); Q[m+k]= (unsigned short) result; } } Q[m+k+1]= 0; } } if ( (short) Q[k+1] < 0 ) do { Q[k+1]+= (unsigned short)L_ADD(Q,C,0,k+1); } while ( (short) Q[k+1] < 0 ); else { temp = ( (unsigned long) Q[k+1] << 16) + (unsigned long) Q[k]; if (mem) { temp= (temp << mem) + (unsigned long) (Q[k-1] >> 16-mem); } if (temp >= dem) { do { result= L_SUB(Q,C,0,k+1); } while ( result !=0 ); L_ADD(Q,C,0,k+1); } } Q[j+1]= save; } else /* k==0 / { result= BIG_SMOD(Q,C[0],j+1); for (i=1; i<=j; i++) Q[i] = 0; Q[0]= (unsigned short) result; } } } void t_div(unsigned short Q, unsigned short D, unsigned short C, unsigned j, unsigned k) { register unsigned long result= 0L; register unsigned long scale,temp,dem; unsigned short save; unsigned i,m,mem; if (j>=k) { if (k) { save= D[j+1]; D[j+1]= 0; mem= 0; dem= (unsigned long) C[k]; if (dem < 0x8000) { mem= 15-short_log2(dem); dem= (unsigned long) C[k-1]+ (dem << 16); dem= dem >> 16-mem; } for (m= j-k+1;m>0;m--) { temp = ( (unsigned long) D[m+k] << 16) + (unsigned long) D[m+k-1]; if (mem) { temp= (temp << mem) + (unsigned long) (D[m+k-2] >> 16-mem); } if ( (short) result >= 0 ) { scale= (unsigned long) temp / dem; if (scale) { if (scale >=0x10000) { scale = scale & 0xFFFF; if (scale) { L_INC(&Q[m],1,j-(k+m)); L_SUB(&D[m],C,0,k+1); result= D[m+k]; if ( (short) result >= 0 ) { temp = ( (unsigned long) D[m+k] << 16) + (unsigned long) D[m+k-1]; if (mem) { temp= (temp << mem) + (unsigned long) (D[m+k-2] >> 16-mem); } scale= temp / dem; } else scale=0; } else scale= scale-1L; } if (scale) result= BIG_DCC(&D[m-1],(unsigned short)scale,C,k+1); } Q[m-1]= (unsigned short) scale; } else { temp= -temp; scale= temp / dem; if (scale) { if (scale >=0x10000) { scale = scale & 0xFFFF; if (scale) { L_DEC(&Q[m],1,j-(k+m)); L_ADD(&D[m],C,0,k+1); result= D[m+k]; if ( (short) result < 0 ) { temp = ( (unsigned long) D[m+k] << 16) + (unsigned long) D[m+k-1]; if (mem) { temp= (temp << mem) + (unsigned long) (D[m+k-2] >> 16-mem); } temp= -temp; scale= temp / dem; } else scale= 0; } else scale= scale-1L; } if (scale) { L_DEC(&Q[m],1,j-(k+m)); result= D[m+k]; RESULT= &D[m-1]; result+= (unsigned long) BIG_ACC(scale,C,k+1); D[m+k]= (unsigned short) result; } } Q[m-1]= -(unsigned short) scale; D[m+k+1]= 0; } } if ( (short) D[k+1] < 0 ) do { D[k+1]+= (unsigned short)L_ADD(D,C,0,k+1); L_DEC(Q,1,1+j-k); } while ( (short) D[k+1] < 0 ); else { temp = ( (unsigned long) D[k+1] << 16) + (unsigned long) D[k]; if (mem) { temp= (temp << mem) + (unsigned long) (D[k-1] >> 16-mem); } if (temp >= dem) { result= L_SUB(D,C,0,k+1); if (result==0) D[k+1]+= (unsigned short)L_ADD(D,C,0,k+1); L_INC(Q,1,1+j-k); } } D[j+1]= save; } else /* k==0 / { result= BIG_SDIV(Q,D,C[0],j+1); for (i=1; i<=j; i++) D[i] = 0; D[0]= (unsigned short) result; } } } void s_mod(unsigned short Q, unsigned short C, unsigned j, unsigned k) { register unsigned long result= 0L; register unsigned long scale,div_hold,temp,dem,b; unsigned short save, a; unsigned i,m; if (j>=k) { if (k) { save= Q[j+1]; Q[j+1]= 0; dem= (unsigned long) C[k]; for (m= j-k+1;m>0;m--) { temp = ( (unsigned long) Q[m+k] << 16) + (unsigned long) Q[m+k-1]; if ( (short) result >= 0 ) { #ifdef inline asm mov dx, WORD PTR [temp+2]; asm xor bx, bx; asm mov ax, WORD PTR [temp]; asm mov cx, WORD PTR [dem]; asm cmp dx, cx; asm jb not_big; asm sub dx, cx; asm mov bx, 1; not_big: asm mov WORD PTR [scale+2], bx asm div cx; asm mov WORD PTR [scale], ax; #else scale= (unsigned long) temp / dem; #endif if (scale) { if (scale >=0x10000) { scale = scale & 0xFFFF; if (scale) { L_SUB(&Q[m],C,0,k+1); result= Q[m+k]; if ( (short) result >= 0 ) { temp = ( (unsigned long) Q[m+k] << 16) + (unsigned long) Q[m+k-1]; #ifdef inline asm mov dx, WORD PTR [temp+2]; asm xor bx, bx; asm mov ax, WORD PTR [temp]; asm mov cx, WORD PTR [dem]; asm cmp dx, cx; asm jb not_big_1; asm sub dx, cx; asm mov bx, 1; not_big_1: asm mov WORD PTR [scale+2], bx asm div cx; asm mov WORD PTR [scale], ax; #else scale= (unsigned long) temp / dem; #endif } else scale= 0; } else scale= scale-1L; } if (scale) /* result= BIG_DCC(&Q[m],(unsigned short)scale,C,k+1);/ { div_hold= 0; result= 1L; a= &Q[m-1]; #ifdef inline asm push ds; asm les di, a; asm lds si, C; asm mov bx,0; SMOD_DCC_LOOP: asm mov ax,WORD PTR [scale]; asm mul WORD PTR [bx+si]; asm add ax, WORD PTR [div_hold]; asm adc dx, 0; asm mov WORD PTR [div_hold],dx; asm xor dx, dx; asm not ax; asm mov cx, WORD PTR [result]; asm add cx, WORD PTR es:[bx+di]; asm adc dx,0 asm add cx, ax asm adc dx,0 asm mov WORD PTR es:[bx+di], cx; asm mov WORD PTR [result],dx; asm add bx,2; asm mov dx, k; asm shl dx,1; asm cmp bx,dx; asm jle SMOD_DCC_LOOP; asm mov ax, WORD PTR [div_hold]; asm xor dx, dx; asm not ax; asm mov cx, WORD PTR [result]; asm add cx, WORD PTR es:[bx+di]; asm adc dx,0 asm add cx, ax asm adc dx,0 asm mov WORD PTR es:[bx+di], cx; asm sub dx, 1; asm mov WORD PTR [result],dx; asm mov WORD PTR [result+2],dx; asm pop ds; #else b= scale & WMASK; for (i=0;i<k+1;i++) { div_hold+= b (unsigned long) C[i]; result += (unsigned long) a[i] + (unsigned long) ((unsigned short) (~div_hold)); a[i] = (unsigned short) result; result = result >> 16; div_hold = div_hold >> 16; } result += (unsigned long) a[k+1]; result += (unsigned long) ((unsigned short) (~div_hold)); a[k+1] = (unsigned short) result; result= (result>>16)-1L; #endif } } } else { temp= -temp; #ifdef inline asm mov dx, WORD PTR [temp+2]; asm xor bx, bx; asm mov ax, WORD PTR [temp]; asm mov cx, WORD PTR [dem]; asm cmp dx, cx; asm jb not_big_2; asm sub dx, cx; asm mov bx, 1; not_big_2: asm mov WORD PTR [scale+2], bx asm div cx; asm mov WORD PTR [scale], ax; #else scale= temp / dem; #endif if (scale) { if (scale >=0x10000) { scale = scale & 0xFFFF; if (scale) { L_ADD(&Q[m],C,0,k+1); result= Q[m+k]; if ( (short) result < 0 ) { temp = ( (unsigned long) Q[m+k] << 16) + (unsigned long) Q[m+k-1]; temp= -temp; #ifdef inline asm mov dx, WORD PTR [temp+2]; asm xor bx, bx; asm mov ax, WORD PTR [temp]; asm mov cx, WORD PTR [dem]; asm cmp dx, cx; asm jb not_big_3; asm sub dx, cx; asm mov bx, 1; not_big_3: asm mov WORD PTR [scale+2], bx asm div cx; asm mov WORD PTR [scale], ax; #else scale= (unsigned long) temp / dem; #endif } else scale= 0; } else scale= scale-1L; } if (scale) { result= Q[m+k]; RESULT= &Q[m-1]; result+= (unsigned long) BIG_ACC(scale,C,k+1); Q[m+k]= (unsigned short) result; } } Q[m+k+1]= 0; } } if ( (short) Q[k+1] < 0 ) do { Q[k+1]+= (unsigned short)L_ADD(Q,C,0,k+1); } while ( (short) Q[k+1] < 0 ); else { temp = ( (unsigned long) Q[k+1] << 16) + (unsigned long) Q[k]; if (temp >= dem) { do { result= L_SUB(Q,C,0,k+1); } while ( result !=0 ); L_ADD(Q,C,0,k+1); } } Q[j+1]= save; } else /* k==0 / { result= BIG_SMOD(Q,C[0],j+1); for (i=1; i<=j; i++) Q[i] = 0; Q[0]= (unsigned short) result; } } } void s_div(unsigned short Q, unsigned short D, unsigned short C, unsigned j, unsigned k) { register unsigned long result= 0L; register unsigned long scale,temp,dem; unsigned short save; unsigned long i,m; if (j>=k) { if (k) { save= D[j+1]; D[j+1]= 0; dem= (unsigned long) C[k]; for (m= j-k+1;m>0;m--) { temp = ( (unsigned long) D[m+k] << 16) + (unsigned long) D[m+k-1]; if ( (short) result >= 0 ) { scale= (unsigned long) temp / dem; if (scale) { if (scale >=0x10000) { scale = scale & 0xFFFF; if (scale) { L_INC(&Q[m],1,j-(k+m)); L_SUB(&D[m],C,0,k+1); result= D[m+k]; if ( (short) result >= 0 ) { temp = ( (unsigned long) D[m+k] << 16) + (unsigned long) D[m+k-1]; scale= temp / dem; } else scale=0; } else scale= scale-1L; } if (scale) result= BIG_DCC(&D[m-1],(unsigned short)scale,C,k+1); } Q[m-1]= (unsigned short) scale; } else { temp= -temp; scale= temp / dem; if (scale) { if (scale >=0x10000) { scale = scale & 0xFFFF; if (scale) { L_DEC(&Q[m],1,j-(k+m)); L_ADD(&D[m],C,0,k+1); result= D[m+k]; if ( (short) result < 0 ) { temp = ( (unsigned long) D[m+k] << 16) + (unsigned long) D[m+k-1]; temp= -temp; scale= temp / dem; } else scale= 0; } else scale= scale-1L; } if (scale) { L_DEC(&Q[m],1,j-(k+m)); result= D[m+k]; RESULT= &D[m-1]; result+= (unsigned long) BIG_ACC(scale,C,k+1); D[m+k]= (unsigned short) result; } } Q[m-1]= -(unsigned short) scale; D[m+k+1]= 0; } } if ( (short) D[k+1] < 0 ) do { D[k+1]+= (unsigned short)L_ADD(D,C,0,k+1); L_DEC(Q,1,1+j-k); } while ( (short) D[k+1] < 0 ); else { temp = ( (unsigned long) D[k+1] << 16) + (unsigned long) D[k]; if (temp >= dem) { result= L_SUB(D,C,0,k+1); if (result==0) D[k+1]+= (unsigned short)L_ADD(D,C,0,k+1); L_INC(Q,1,1+j-k); } } D[j+1]= save; } else /* k==0 / { result= BIG_SDIV(Q,D,C[0],j+1); for (i=1; i<=j; i++) D[i] = 0; D[0]= (unsigned short) result; } } } #endif unsigned short two_strassen(unsigned short CC, unsigned short A, unsigned short B, unsigned long M); unsigned short signed_part_mult(unsigned short CC, unsigned short A, unsigned short B, unsigned short temp, unsigned long M, unsigned long N) { unsigned long t, s; unsigned short X, Y, sign_x, sign_y; unsigned long i,j; X = temp; Y = &temp[M]; i= N/2; #ifdef vms ots$move3(i * sizeof(unsigned short), &A[M], X); #else // memcpy( (char )X, (char )&A[M], (int)(i * sizeof(unsigned short)) ); for (j=0; j<i; j++) X[j] = A[M+j]; #endif t= L_SUB(X,A,0,i) << 16; #ifdef vms ots$move3(i * sizeof(unsigned short), B, Y); #else // memcpy( (char )Y, (char )B, (int)(i * sizeof(unsigned short)) ); for (j=0; j<i; j++) Y[j] = B[j]; #endif s= L_SUB(Y,&B[M],0,i) << 16; if ((i) < M ) { t = (t >> 16) + (unsigned long) (~A[i] & 0x0000ffff); X[i] = t & 0x0000ffff; s = (s >> 16) + (unsigned long) B[i] + (unsigned long)(0x0000ffff); Y[i] = s & 0x0000ffff; } sign_x = (t - 0x00010000L) >> 16; sign_y = (s - 0x00010000L) >> 16; if (M<=split) t= BIG_PART_MPY(CC,X,Y,M); else t= two_strassen(CC, X, Y, M); if (sign_y) { t+= L_SUB(&CC[M],X,0,M); } if (sign_x) { t+= L_SUB (&CC[M],Y,0,M); } if (sign_y \| sign_x) t= t-1; t= t+ (unsigned long) CC[M+M]; CC[M+M]= (unsigned short) t; return (unsigned short) (t >> 16); } unsigned short add_two_strassen(unsigned short CC, unsigned short A, unsigned short B, unsigned short temp, unsigned short carry, unsigned long M, unsigned long N) { unsigned long t; unsigned long i; #ifdef vms ots$move5(zero, (unsigned char )&zero, (unsigned char)zero, (N+N) sizeof(unsigned short), temp); #else BIG_ZERO(temp,N+N); #endif if (M<=split) t= BIG_PART_MPY(temp,A,B,M); else t= two_strassen(temp, A, B, M); carry+= L_ADD(CC,temp,0,N+N); t= L_ADD(&CC[N],temp,0,N); t = t + (unsigned long)CC[N+N] + (unsigned long) carry + (unsigned long)temp[N]; CC[N+N] = (unsigned short)t; t= L_ADD(&CC[N+N+1],&temp[N+1],(unsigned short) (t >> 16),N-1); return (unsigned short) (t); } unsigned short two_strassen(unsigned short CC, unsigned short A, unsigned short B, unsigned long M) { unsigned short lo; unsigned long t; unsigned short carry; unsigned long i; unsigned long m = M - (M / 2); /* M must be a power of 2 / t= 0; { lo = (unsigned short ) BIG_ALLOC(m+m+2); if (lo==NULL) { printf("\n fail to getspace in two_strassen m = %ld\n",m); exit(1); } ; /* 1 more word for the sign / t= add_two_strassen(CC, A, B, lo, 0, m, m); carry= add_two_strassen(&CC[m], A+m, B+m, lo, t, M-m, m); t= signed_part_mult(&CC[m], A, B, lo, m, M); if ((short)t <0 ) for (i=1;(i<=m) && t;i++) { if (CC[m+M+i] != 0) t = 0; CC[m+M+i]--; } else for (i=1;(i<=m) && t;i++) { CC[m+M+i]++; if (CC[m+M+i]) t = 0; } BIG_FREE(lo); } return (unsigned short) carry; } void strassen(unsigned short CC, unsigned short A, unsigned short B, unsigned long M) { unsigned m= BIG_LENW(A,M),n= BIG_LENW(B,M),i; i= m; if (i<n) i= n; #ifdef vms ots$move5(zero, (unsigned char )&zero, (unsigned char)zero, (M+M) sizeof(unsigned short), CC); #else BIG_ZERO(CC,M+M); #endif if (i<=split) BIG_PART_MPY(CC,A,B,i); else { if (i==m) { two_strassen(CC,A,B,n); B_PART_MPY(CC+n,A+n,B,m-n,n); } else { two_strassen(CC,A,B,m); B_PART_MPY(CC+m,B+m,A,n-m,m); } // two_strassen(CC,A,B,i); / } } unsigned short two_squ_strassen(unsigned short CC, unsigned short A, unsigned long M); unsigned short signed_squ(unsigned short CC, unsigned short A, unsigned long M, unsigned long N) { unsigned long t; unsigned short X, sign_x; unsigned long i,j; X = (unsigned short ) BIG_ALLOC(M); if (X==NULL) { printf("\n fail to getspace in signed_squ M = %ld\n",M); exit(1); } ; i= N/2; t = 0x00010000L; #ifdef vms ots$move3(i * sizeof(unsigned short), A, X); #else // memcpy( (char )X, (char )A, (int)(i * sizeof(unsigned short)) ); for (j=0; j<i; j++) X[j] = A[j]; #endif t= L_SUB(X,&A[M],0,i) << 16; if ((i) < M ) { t = (t >> 16) + (unsigned long) A[i] + (unsigned long)(0x0000ffff); X[i] = t & 0x0000ffff; } sign_x = (t - 0x00010000L) >> 16; if (sign_x) { unsigned short carry = 1; for (i=0;i<M;i++) { X[i] = ~X[i] + carry; if (X[i]) carry = 0; } } if (M<=(split)) BIG_PSQ(CC,X,M); else { #ifdef vms ots$move5(zero, (unsigned char )&zero, (unsigned char)zero, (M+M) sizeof(unsigned short), CC); #else BIG_ZERO(CC,M+M); #endif two_squ_strassen(CC,X,M); } BIG_FREE(X); return 0; } unsigned short add_two_squ_strassen(unsigned short CC, unsigned short A, unsigned short temp, unsigned short carry, unsigned long M, unsigned long N) { unsigned long t; unsigned long i; #ifdef vms ots$move5(zero, (unsigned char )&zero, (unsigned char)zero, (N+N) * sizeof(unsigned short), temp); #else BIG_ZERO(temp,N+N); #endif if (M<=(split)) BIG_PSQ(temp,A,M); else { two_squ_strassen(temp, A, M); } carry+= L_ADD(CC,temp,0,N+N); t= L_ADD(&CC[N],temp,0,N); t = t + (unsigned long)CC[N+N] + (unsigned long) carry + (unsigned long)temp[N]; CC[N+N] = (unsigned short)t; t= L_ADD(&CC[N+N+1],&temp[N+1],(unsigned short) (t >> 16),N-1); return (unsigned short) (t); } unsigned short two_squ_strassen(unsigned short CC, unsigned short A, unsigned long M) { unsigned short lo; unsigned long t; unsigned short carry; unsigned long i; unsigned long m = M - (M / 2); t= 0; { lo = (unsigned short ) BIG_ALLOC(m+m+2); if (lo==NULL) { printf("\n fail to getspace in two_squ_strassen m = %ld\n",m); exit(1); } ; /* 1 more word for the sign / t= add_two_squ_strassen(CC, A, lo, 0, m, m); carry= add_two_squ_strassen(&CC[m], A+m, lo, t, M-m, m); signed_squ(lo, A, m, M); t= L_SUB(&CC[m],lo,0,m+m); t= (unsigned long) CC[m+m+m] + t -1; CC[m+m+m] = t & 0x0000ffff; t= (t >> 16); if ((short)t <0 ) for (i=1;(i<=m) && t;i++) { if (CC[m+m+m+i] != 0) t = 0; CC[m+m+m+i]--; } } BIG_FREE(lo); return (unsigned short) carry; } void strassen_squ(unsigned short CC, unsigned short A, unsigned long M) { unsigned m = BIG_LENW(A,M); if (m<=(split)) { BIG_PSQ(CC,A,M); } else { #ifdef vms ots$move5(zero, (unsigned char )&zero, (unsigned char)zero, (M+M) * sizeof(unsigned short), CC); #else BIG_ZERO(CC,M+M); #endif two_squ_strassen(CC,A,m); } } unsigned MOD_EXP(unsigned short A,unsigned short B, unsigned short C,unsigned short D,unsigned long N) /* A = B*C (MOD D) / { unsigned short TAB, RESULT, ACC, s, t, h, m; short CLEN, W; short power, mask; unsigned long ii, shift=0; unsigned long dem; unsigned long i,j,k; unsigned long T = BIG_LENW(D,N); unsigned stat = 0; RESULT = BIG_ALLOC(T+T+2); ACC = BIG_ALLOC(T+T+2); m = BIG_ALLOC(T); TAB = BIG_ALLOC( T 17 ); /* SPACE FOR TABLE / if (TAB==NULL) { printf("Allocation failed\n"); return(-1); }; k=T-1; dem= D[k]; if ((dem & 0x8000)==0) { while ((dem & 0x8000L) == 0 ) { dem = dem << 1; shift= shift +1; } } if (shift) { BIG_LEFT_SHIFT(m,D,shift,k+1); } else BIG_COPY(m,D,T); / PRECOMPUTE SMALL (SIZE 2W) TABLE OF POWERS OF B / CLEN = BIG_LENGTH(C,N); if (CLEN < 4) W = 1; else if (CLEN < 16) W = 2; else if (CLEN < 64) W = 3; else W = 4; power= (1 << W); BIG_CONST(TAB,1,T); /* ZEROTH POWER IS ONE / BIG_COPY(TAB+T,B,T); / FIRST POWER IS B / t= TAB+T+T; for (i=2; i < power; i++) { if (i & 1) { strassen(t,t-T,B,T); } else { if (T<=(split)) { BIG_PSQ(t,TAB+((i/2)T),T); } else strassen_squ(t,TAB+((i/2)T),T); } for (j=(T+T)-1;j>0 && t[j]==0;j--); s_mod(t,m,j,k); t= &t[T]; } / LOOP OVER ELEMENTS OF EXPONENT C IN APPROPRIATE RADIX / power = 0; mask = 1 << ((CLEN) % 16); t= RESULT; s= ACC; ii = CLEN+1; do { ii--; power = power << 1; if (C[ii/16] & mask) power = power + 1; if (mask == 1) mask = 0x8000; else mask = (mask >> 1) & 0x7FFF; } while ((ii) && (power < (1<<(W-1)))); BIG_COPY(s,TAB+(power)T,T); power = 0; while (ii) { ii = ii-1; if (T<=(split)) { BIG_PSQ(t,s,T); } else strassen_squ(t,s,T); for (j=(T+T)-1;j>0 && t[j]==0;j--); s_mod(t,m,j,k); h= s; s= t; t= h; power = power << 1; if (C[ii/16] & mask) power = power + 1; if (mask == 1) mask = 0x8000; else mask = (mask >> 1) & 0x7FFF; if ((ii==0) \|\| (power >= (1<<(W-1)))) { if (power) { strassen(t,TAB+(power)T,s,T); for (j=(T+T)-1;j>0 && t[j]==0;j--); s_mod(t,m,j,k); power = 0; h= s; s= t; t= h; } } } if (N-T) #ifdef vms ots$move5(zero, (unsigned char )&zero, (unsigned char)zero, (N-T) * sizeof(unsigned short), &A[T]); #else BIG_ZERO(&A[T],N-T); #endif if (shift) for (j=(T)-1;j>0 && s[j]==0;j--); t_mod(s,D,j,k); BIG_COPY(A,s,T); stat = 0; exitlabel: #ifndef stack_mem BIG_FREE(TAB); BIG_FREE(m); BIG_FREE(ACC); #endif BIG_FREE(RESULT); return(stat); } unsigned BIG_UNEXP(unsigned short M, / OUTPUT MESSAGE size 2PSIZE words / unsigned short C, / INPUT `CIPHERTEXT' size 2PSIZE / unsigned short NN,/ INPUT MODULUS size 2PSIZE / unsigned short PP,/ FIRST PRIME size PSIZE / unsigned short QQ,/* SECOND PRIME; size PSIZE / unsigned short DP,/* decryption exponent mod P size PSIZE / unsigned short DQ,/* decryption exponent mod Q size PSIZE / unsigned short CR,/* CRT coef (inverse of Q mod P) / / CR has length PSIZE / unsigned long PSIZE) / LENGTH OF PRIMES IN WORDS / / decrypt ciphertext C into message M using Chinese remainder / { unsigned short t1,t2,t3,u2,u3; unsigned stat = 0; unsigned j,k,qq_len,pp_len,len; for (pp_len=PSIZE-1;pp_len>0 && PP[pp_len]==0;pp_len--); for (qq_len=PSIZE-1;qq_len>0 && QQ[qq_len]==0;qq_len--); j= pp_len; if (qq_len>j) j= qq_len; t1 = BIG_ALLOC(j+j+1); t2 = BIG_ALLOC(j+j+1); if (t2==NULL) { printf("Allocation failed\n"); return(-1); }; #ifdef vms ots$move5(zero, (unsigned char )&zero, (unsigned char)zero, (j+j+1-pp_len) sizeof(unsigned short), &t1[pp_len]); ots$move5(zero, (unsigned char )&zero, (unsigned char)zero, (j+j+1-qq_len) sizeof(unsigned short), &t2[qq_len]); ots$move5(zero, (unsigned char )&zero, (unsigned char)zero, (PSIZE+PSIZE-j-j) sizeof(unsigned short), &M[j+j]); #else BIG_ZERO(&t1[pp_len],j+j+1-pp_len); BIG_ZERO(&t2[qq_len],j+j+1-qq_len); BIG_ZERO(&M[j+j],PSIZE+PSIZE-j-j); #endif u2 = BIG_ALLOC(j+1); u3 = BIG_ALLOC(j+1); if (u3==NULL) { printf("Allocation failed\n"); return(-1); }; for (len=(PSIZE+PSIZE)-1;len>0 && C[len]==0;len--); if (j>=len) { #ifdef vms ots$move5(zero, (unsigned char )&zero, (unsigned char)zero, (j+1-len) sizeof(unsigned short), &u3[len]); ots$move5(zero, (unsigned char )&zero, (unsigned char)zero, (j+1-len) sizeof(unsigned short), &u2[len]); #else BIG_ZERO(&u3[len],j+1-len); BIG_ZERO(&u2[len],j+1-len); #endif } BIG_COPY(u3,C,len+1); t_mod(u3,QQ,len,qq_len); /u3=CmodQ / stat = MOD_EXP(t2,u3,DQ,QQ,qq_len+1); /t2=CDQmodQ / if (stat==0) { BIG_COPY(u2,C,len+1); /* /u2=C mod P / t_mod(u2,PP,len,pp_len); stat = MOD_EXP(t1,u2,DP,PP,pp_len+1); /t1=CDP modP / } if (stat==0) { k= (unsigned) L_SUB(t1,t2,0,j+1); if (k==0) L_ADD(t1,PP,0,j+1); strassen(u2,t1,CR,j+1); for (k=(j+j+2)-1;k>0 && u2[k]==0;k--); t_mod(u2,PP,k,pp_len); strassen(M,u2,QQ,j+1); L_ADD(M,t2,0,j+j+1); } #ifndef stack_mem BIG_FREE(u3); BIG_FREE(u2); BIG_FREE(t2); #endif BIG_FREE(t1); return(stat); }
2.46	core.h for data > 64k	RDVAX::GRIES		`Fri May 15 1992 19:43`	167
	extern unsigned short RESULT; void BIG_ERROR(unsigned count, char S); long set_stack (unsigned long size); void reset_stack (unsigned long size); unsigned short * BIG_ALLOC(unsigned long size); void BIG_FREE(unsigned short A); unsigned BIG_LENGTH(unsigned short A, unsigned long N); void BIG_CONST(unsigned short A,unsigned short V, unsigned long N); int BIG_CMP(unsigned short A,unsigned short B, unsigned long N); void BIG_ZERO (unsigned short A, unsigned long N); void BIG_COPY (unsigned short A,unsigned short B, unsigned long N); unsigned short BIG_LEFT_SHIFT (unsigned short A,unsigned short B, unsigned SHIFT, unsigned long N); unsigned short BIG_SMOD (unsigned short A,unsigned short V,unsigned long N); unsigned short BIG_SDIV (unsigned short Q, unsigned short A, unsigned short V, unsigned long N); unsigned long BIG_LENW (unsigned short A, unsigned long N); unsigned long BIG_ACC ( unsigned short B, unsigned short C, unsigned long N); unsigned long L_ACC ( unsigned long B, unsigned short C, unsigned long N); unsigned long BIG_PART_MPY (unsigned short A, unsigned short B, unsigned short C, unsigned long N); unsigned long L_ADD (unsigned short A, unsigned short B, unsigned short carry_in, unsigned long N); unsigned long L_INC (unsigned short A, unsigned short B, unsigned long N); unsigned short BIG_PSQ (unsigned short A, unsigned short B, unsigned long N); void s_mod(unsigned short Q, unsigned short C, unsigned j, unsigned k); void t_mod(unsigned short Q, unsigned short C, unsigned j, unsigned k); void t_div(unsigned short Q, unsigned short D, unsigned short C, unsigned j, unsigned k); unsigned long BIG_DCC (unsigned short A, unsigned short B, unsigned short C, unsigned long N); unsigned long L_ACC ( unsigned long B, unsigned short C, unsigned long N); unsigned long L_DCC (unsigned short A, unsigned long B, unsigned short C, unsigned long N); unsigned long L_ADD (unsigned short A, unsigned short B, unsigned short carry_in, unsigned long N); unsigned long L_INC (unsigned short A, unsigned short B, unsigned long N); unsigned long L_DEC (unsigned short A, unsigned short B, unsigned long N); unsigned long L_SUB (unsigned short A, unsigned short B, unsigned short carry_in, unsigned long N); unsigned short two_strassen(unsigned short CC, unsigned short A, unsigned short B, unsigned long M); unsigned short signed_part_mult(unsigned short CC, unsigned short A, unsigned short B, unsigned short temp, unsigned long M, unsigned long N); unsigned short add_two_strassen(unsigned short CC, unsigned short A, unsigned short B, unsigned short temp, unsigned short carry, unsigned long M, unsigned long N); unsigned short two_strassen(unsigned short CC, unsigned short A, unsigned short B, unsigned long M); void strassen(unsigned short CC, unsigned short A, unsigned short B, unsigned long M); unsigned short two_squ_strassen(unsigned short CC, unsigned short A, unsigned long M); unsigned short signed_squ(unsigned short CC, unsigned short A, unsigned long M, unsigned long N); unsigned short add_two_squ_strassen(unsigned short CC, unsigned short A, unsigned short temp, unsigned short carry, unsigned long M, unsigned long N); unsigned short two_squ_strassen(unsigned short CC, unsigned short A, unsigned long M); void strassen_squ(unsigned short CC, unsigned short A, unsigned long M); unsigned MOD_EXP(unsigned short A, unsigned short B, unsigned short C, unsigned short D, unsigned long N); unsigned BIG_UNEXP(unsigned short M, unsigned short C, unsigned short NN, unsigned short PP, unsigned short QQ, unsigned short DP, unsigned short DQ, unsigned short CR, unsigned long PSIZE);
2.47	alloc.h for vax	RDVAX::GRIES		`Fri May 15 1992 19:44`	22
	#ifdef vax #define far #define farmalloc malloc #define farfree free #define farcalloc calloc #define farcoreleft coreleft #else #ifdef mips #define far #define farcalloc calloc #define farmalloc malloc #define farfree free #define farcoreleft coreleft #else #include <alloc.h> #endif #endif #ifdef mips #include <malloc.h> #else #include <stdlib.h> #endif
2.48		RUSURE::EDP	Always mount a scratch monkey.	`Wed Jan 12 1994 13:47`	9
	I just heard that 2^859433-1 is prime. -- edp Public key fingerprint: 8e ad 63 61 ba 0c 26 86 32 0a 7d 28 db e7 6f 75 To get PGP, FTP /pub/unix/security/crypt/pgp23A.zip from ftp.funet.fi. For FTP access, mail "help" message to DECWRL::FTPmail or open Upsar::Gateways.
2.49		STAR::ABBASI	and the computer said mate in 23!	`Wed Jan 12 1994 17:43`	5
	i told MAPLE to factor this and left it thinking about it. i'll check on it again in few hours to see if this is really a prime. \nasser
2.50		CSC32::D_DERAMO	Dan D'Eramo, Customer Support Center	`Wed Jan 12 1994 18:34`	4
	There are faster tests for primality than to try to factor the number (see 2.5). Dan
2.51	Could take a while.	CADSYS::COOPER	Topher Cooper	`Wed Jan 12 1994 18:37`	7
	RE: .49 This has almost 259,000 digits. Record factorizations are in the few hundred digits. I think you will have to wait for more than a few hours. ;-) Topher
2.52	i stopped this experiement with MAPLE	STAR::ABBASI	and the computer said mate in 23!	`Wed Jan 12 1994 19:00`	5
	ok, thanks guys, i got tired of waiting for MAPLE to factor this plus and all my window sessions suddenly got very slow, so i went and and hit ^y. \nasser
2.53	if you've got the time...	CSC32::D_DERAMO	Dan D'Eramo, Customer Support Center	`Thu Jan 13 1994 16:09`	35
	Path: nntpd2.cxo.dec.com!pa.dec.com!decwrl!elroy.jpl.nasa.gov!usc!sol.ctr.columbia.edu!news.kei.com!eff!linus!linus.mitre.org!gauss!bs From: bs@gauss.mitre.org (Robert D. Silverman) Newsgroups: sci.math Subject: Re: new gigantic prime discovered? Date: Thu, 13 Jan 94 04:39:45 MST Organization: Research Computer Facility, MITRE Corporation, Bedford, MA Lines: 24 Message-ID: <2h3bu1$8dg@linus.mitre.org> References: <1994Jan12.174643.8129@galois.mit.edu> <2h22m1$bfh@linus.mitre.org> <CJJyLw.2MA@northshore.ecosoft.com> NNTP-Posting-Host: gauss.mitre.org In article <CJJyLw.2MA@northshore.ecosoft.com> ndm@northshore.ecosoft.com (Norman D. Megill) writes: :Here is a question about prime numbers that I've wondered about off and :on. : :Once a factor of a large composite number is found and displayed, you :can easily verify for yourself that it is composite with a few minutes :of calculation, even though it may have taken a hundred hours of :supercomputer time to find the factor. The role of the supercomputer :becomes irrelevant as soon as the factor is found. : :Is there any similar paradigm for large prime numbers; i.e., is it :possible to verify a claim that a certain number is prime, without :having a supercomputer as powerful as the one that found it? Or must we For Mersenne primes, they can indeed be verified quickly even on ordinary workstations. Using the Lucas-Lehmer test with FFT's, one could prove M859433 prime on a large workstation in perhaps 2 weeks. Richard Crandall has already done this. -- Bob Silverman These are my opinions and not MITRE's. Mitre Corporation, Bedford, MA 01730 "You can lead a horse's ass to knowledge, but you can't make him think"
2.54	If they want to convince you, they should factor n-1 for you.	WIBBIN::NOYCE	DEC 21064-200DX5 : 130 SPECint @ $36K	`Thu Jan 13 1994 17:50`	6
	These tests are made easier if the person who claims that n is prime also supplies a prime factorization of n-1 (or of n+1). This factorization serves as a "primality certificate", since you can use it to verify the primality without too much work. Since the factorization may include some large prime factors, they should probably include "primality certificates" for each of those factors, too, recursively...
2.55	Does "without too much work" mean "fits in a note"?	VMSDEV::HALLYB	Fish have no concept of fire	`Thu Jan 13 1994 18:44`	31
	> These tests are made easier if the person who claims that n is prime also > supplies a prime factorization of n-1 (or of n+1). This factorization serves > as a "primality certificate", since you can use it to verify the primality > without too much work. Can we see how this works in practice? Suppose the only prime numbers I'm willing to stipulate to are 2, 3, 5 and (what the heck) 7. Claim1: 10007 is prime. 10007 is "big" so I will supply you with the factors of N1-1: 10006 = 2 * 5003. Claim2: 5003 is prime. 5003 is "big", so here's a sub-certificate for N2-1: 5002 = 2 * 41 * 61 Claim3: 41 and 61 are prime. 41 and 61 are "big" so here are two sub-subcertificates: 40 = 2 * 2 * 2 * 5, a product of primes 60 = 2 * 2 * 3 * 5, a product of primes Now that we have all these certificates, how do we go about combining them to prove the father number is prime? John
2.56		3D::ROTH	Geometry is the real life!	`Thu Jan 13 1994 20:08`	9
	> Now that we have all these certificates, how do we go about combining > them to prove the father number is prime? I don't recall the details, but there was a paper somewhere like Mathematics of Computation titled "Every prime has a succinct certificate" that explained this. Probably it's in textbooks on computers and number theory nowadays and I could check one or two I have at home. - Jim
2.57	primality is in NP	CSC32::D_DERAMO	Dan D'Eramo, Customer Support Center	`Thu Jan 13 1994 21:48`	36
	The certificate would look like (10007, 5) / \ (2) (5003, 2) / \| \ (2) (41,6) (61,2) / \ / \| \ (2) (5) (2)(3)(5) The primes you accept as prime are by themselves, (2), (3), (5). The others are of the form (p,a) where p is the prime and a is a primitive root modulo p. That is, the powers a, a^2, a^3, ..., a^(p-1) (modulo p) run through each the numbers 1,2,3,...,p-1 exactly once, and only the last one a^(p-1) = 1 (modulo p). If p > 1 is prime then such an `a' exists, if p > 1 is not prime then such an `a' does not not exist. The factorization of p-1 comes into play in the verification that a really does have the stated property. If the p-1 powers a,a^2,...,a^(p-1) are not all distinct, then two have the same value, a^r = a^s modulo p for some r < s, which means a^(s-r) = 1 mod p. If r and s are least such that a^r = a^s mod p then (s-r) is the smallest k such that a^k = 1 mod p. Then if a^m = 1 mod p you must have k\|m. After you verify that a^(p-1) = 1 mod p, you only need to check the divisors of p-1 to show that there is no smaller k with a^k = 1 mod p. Just try a^((p-1)/q) for each prime divisor q of p-1, and if none of those is 1 mod p then a truly is a primitive root of p and p is prime. [I.e., if a^(p-1) = 1 mod p, and p-1 is a product of powers of the given primes q, and the q's really are all prime, and each a^((p-1)/q) is not 1 mod p, then p is prime.] Dan
2.58		WRKSYS::ARUMUGHAM		`Thu Jan 13 1994 23:00`	1
	Does anybody have source for checking very large primes?
2.59	2^859433 computed by CalReal, the result is in...	VAXCAP::KOSTAS	He is great who confers the most benefits.	`Thu Feb 03 1994 16:42`	15
	re. .49, .51, .52 I could not resist the temptation to see if CalReal can compute this new prime 2^859433-1, so here it is. After ~20h of elapsed time the results of 2^859433 are in the file: VAXCAP""::REV$:[KOSTAS.USERLIB]2_TO_859433.TXT; Now, who is going to check if this is correct? Or how does one compare two potentially different computational results of the same problem, especially when the answer is as large as this? Enjoy, Kostas
2.60		HANNAH::OSMAN	see HANNAH::IGLOO$:[OSMAN]ERIC.VT240	`Fri Feb 04 1994 13:00`	9
	Well, if the number is a power of 2, one possible sanity check on the result could be to ask calreal to convert the number to hex and print it out. It should be a single digit followed by all 0's. /Eric
2.61	I was asking for an independent observer/tool comparison	VAXCAP::KOSTAS	He is great who confers the most benefits.	`Fri Feb 04 1994 14:33`	10
	re. .-1 Eric, I hope humor was included in your last reply. Anyway, I was asking for some other tool to verify the result from calreal against the one from the supercomputer. If calreal is wrong then asking it to convert a the wrong decimal number to hex will not be usefull. /k
2.62	what a BIG number !	STAR::ABBASI	always give a check,it might be mate	`Fri Feb 04 1994 18:39`	7
	.59 thanks for this, i typed that file on the screen, i must admit this must be the biggest number i have ever seen, and probably will ever see in my whole life ! \nasser
2.63	Subtle humor?	FLOYD::YODER	MFY	`Mon Dec 19 1994 15:19`	7
	"These tests are made easier if the person who claims that n is prime also supplies a prime factorization of n-1 (or of n+1). This factorization serves as a 'primality certificate', since you can use it to verify the primality without too much work." Is this subtle humor? Surely a prime factorization of n+1 is not hard to come by when n is a Mersenne prime. :-)
2.64		CSC32::D_DERAMO	Dan D'Eramo, Customer Support Center	`Thu Dec 22 1994 02:27`	5
	re .-1, but in this case the Lucas-Lehmer test gives you the "certificate". If n is 2^p - 1, just compute the sequence LL(0), LL(1), ..., LL(p-2) of numbers mod n as in reply .5. Dan
2.65		RUSURE::EDP	Always mount a scratch monkey.	`Wed Sep 04 1996 17:11`	62
	Article 158181 of sci.math: From: caldwell@unix1.utm.edu (Chris Caldwell) Newsgroups: sci.math Subject: Re: 2^1257787-1 is prime!!! Organization: University of Tennessee Lines: 27 Landon Curt Noll (chongo@prime.corp.sgi.com) wrote: : largest known prime number 2^1257787-1 : See: http://reality.sgi.com/csp/ioccc/noll/prime/prime_press.html Perhaps he said it all, but he are a few more words: On 3 September 1996, Cray Research announced that once again Slowinski and Gage have set a new record by finding the prime 2^1257787-1 which has 378,632 digits. This is the largest known prime by far--the next largest has "only" 258,716 digits. It is also the 34th Mersenne prime to be discovered (though it might not be the 34th in order of size as the entire region below it has not been check). Looking at the graph of the largest known prime by year, we see this prime is roughly the size record we'd expect to find this year. The proof of this 378,632 digit number's primality (using the traditional Lucas-Lehmer test) took about 6 hours on one CPU of a CRAY T94 super computer. Richard Crandall independently verified the primality. See also http://www.utm.edu/research/primes/notes/1257787.html (a page on this prime) http://www.utm.edu/research/primes/ (lists of prime resources) http://www.utm.edu/research/primes/largest.html (the list of prime number records) Chris Caldwell (caldwell@utm.edu) Article 158190 of sci.math: From: caldwell@unix1.utm.edu (Chris Caldwell) Newsgroups: sci.math Subject: Re: 2^1257787-1 is prime!!! Organization: University of Tennessee Lines: 14 Coming so close: George Woltman who was 90% of the way through this very number when asked to check the result by Slowinski and Gage. According to the San Jose Mercury News article he said "It hurt for a few days, but I got over it." Woltman's program is available over the internet and will check this new prime in about 60 hours on a 90MhZ Pentium. Says alot about his program that it is so fast. You can get his software and join in the hunt at: http://ourworld.compuserve.com/homepages/justforfun/prime.htm Chris.