Recientemente me vi en la necesidad de encontrar algunos números primos grandes de la forma $latex (3*8^n)-1$ por una cuestión de un problema de geometría aritmética y primality testing, quiénes creo que se podrían interesar en esto fueron en Facebook Esteban Gutierrez y Manuel López Michelone quiénes comentaron sobre esto, un análisis rápido te dice que ese número es primo para $latex n\in \lbrace 1,2,6,72,1092,5687 \rbrace$ pero otro análisis no tan rápido que hice fue para descubrir $latex n=17129$, estos número para el ojo inocente parecerían inofensivos, pero para $latex n=17129$ nos encontramos con un número de 16,000 dígitos aproximadamente, y ahora mi workstation está checando $latex >n=35000$ que son como 32,000 dígitos decimales, es decir 105,000 bits, tardándose aproximadamente 30 minutos por cada thread (hice 32 POSIX-threads) entonces me arroja aproximadamente 32 resultados cada media hora, y el tiempo sube por cada iteración logarítmicamente, así que si sigo así pronto comenzará a tardar horas, el código lo voy a publicar ahorita, así que encontrarán las ligas al final de este post para que lo corra cualquier linuxero, o mejor decir... "POSIXERO" ya que toda el api que uso al final es POSIX compliant y para manejar números grandes y hacer aritmética uso BN (Bignum) de OpenSSL que considero es lo más rápido ya que se usa en la industria, el código detecta tus procesadores y usa TODOS, así que tomalo en cuenta con el nice, tiene macros para funcionar en OSX (Apple) ya que pthread_set_affinity_np() y CPU_SET funcionan diferente.
La pregunta matemática sería:
¿Existen una cantidad infinita de números primos de esta forma?
Ahora explicaré cómo lo hice para que sea lo más óptimo que se me pudo ocurrir.
1. Construir número optimamente
$latex (3*8^n)-1$ lo podemos fabricar en binario en vez de calcularlo, con esto nos evitamos muchos ciclos del procesador
Por un lado tenemos que $latex 8^n=2^{3n}$ y $latex 2^m=1000...000B$ con $latex m$ $latex 0$'s eso significa que $latex 8^n$ tiene $latex 3n$ ceros y un $latex 1$ al principio, después multiplicar por $latex 3$ es lo mismo que sumar $latex 3$ veces $latex 1000...000B$ el cual será el número $latex 11000...000B$ con $latex 3n$ ceros y restar $latex 1$ será negar todos los ceros y el segundo $latex 1$ por lo que va a quedar $latex (3*8^n)-1=10111...111B$ donde el número de $latex 1$'s menos significativos es $latex 3n$ , con esto ya no tenemos que calcular exponenciación que es muy costosa.
2. Ignorar números que nos harán perder el tiempo
Sucede MUY frecuentemente que $latex (3*8^n)-1$ es múltiplo de $latex 5$ , esto es fácil verlo
ya que si $latex 3*8^n$ termina en $latex 6$ o $latex 1$ entonces $latex (3*8^n)-1$ es múltiplo de $latex 5$, pero no puede terminar en $latex 1$ porque $latex 3*8^n$ es par, y para que termine en $latex 6$ como $latex 8^n$ termina en $latex 8,4,2,6,8,4,2,6,8,...$ (en ese orden comenzando con n=1) nos interesa saber cuándo $latex 8^n$ termina en $latex 2$ para que $latex 3*8^n$ termine en $latex 6$ y por consiguiente $latex (3*8^n)-1$ sea múltiplo de $latex 5$.
Un chequeo rápido y respaldado por la propiedad inductiva en los número naturales sobre $latex n$ tenemos que $latex 8^n$ termina en $latex 2$ si $latex n=3,7,11,15$ es decir si $latex n=4t-1$ y más computacionalmente si $latex n\equiv 3 \mod 4$ o más humano "si $latex n-3$ es múltiplo de $latex 4$" entonces esto nos dice que podemos eliminar automáticamente 25% de todos los exponentes al checar $latex (3*8^n)-1$ ya que serán múltiplos de $latex 5$
3. Optimizar test de primalidad y utilizar números más familiares para una computadora
Una vez construido el número, y filtrados los exponentes que hacen trivialmente compuesto al número, necesitamos ver que lo que tenemos en efecto sea un número primo.
Para hacer esto nos auxiliaremos en el pequeño teorema de Fermat el cual lo escribo diferente a Fermat para que se entienda dice:
Teorema de Fermat
Si $latex p$ es primo y $latex mcd(p,a)=1$ $latex \Rightarrow$ $latex a^p - a$ es múltiplo de $latex p$
Equivalente
Si $latex p$ es primo y $latex mcd(p,a)=1$ $latex \Rightarrow$ $latex a^{p-1} \equiv 1 \bmod p$
Esto es lo mejor que tenemos y lo peor es que existe la posibilidad de un "falso positivo"
ya que el teorema aquí ya supone que $latex p$ es primo, es decir estamos checando una propiedad que tiene un número primo siempre, pero podría tenerla otro número también ya que el teorema no es un "si y sólo sí" $latex \Leftrightarrow$ , pero para nuestra fortuna, los números que cumplen la propiedad de Fermat y no son primos son "strong pseudo-primes" , "Fermat Liars" y son raros, de hecho yo prefiero Números de Carmichael quién fue el que los estudió y para nuestra fortuna, no hay tantos y son raros, y si nos toparamos con un "posible primo" , cambiamos la $latex a$ del teorema de Fermat y volvemos a probar y si también se cumple la congruencia, es ya casi un hecho que lo que tenemos es primo.
Pero bueno aún podemos optimizar MÁS , vamos a optimizar el teorema de Fermat, ya que como pueden ver... vamos a tener que elevar un número (en mi caso 2) a la $latex x$ donde $latex x$ es un número de más de 30 mil dígitos, módulo es número de 30 mil dígitos... afortunadamente existen algoritmos para hacer esto en tiempo logarítmico pero aún así es tardado, así que si podemos eliminar más ciclos sería bueno.
Tenemos que $latex x=(3*8^n)-1$ nunca es el número primo $latex 2$ así que podemos suponer que es impar sin ningún problema , por un lado tenemos que $latex a^{x-1} \equiv 1 \bmod x \Leftrightarrow a^{x-1} -1 \equiv 0 \bmod x$ si $latex x$ es primo, ahora, $latex x-1=2k$ es decir es par, entonces $latex a^{x-1}-1 = a^{2k}-1 = (a^k -1)(a^k + 1) \equiv 0 \bmod x$ (diferencia de cuadrados), como $latex k=\frac{x-1}{2}$ entonces tenemos que $latex (a^{\frac{x-1}{2}}-1)(a^{\frac{x-1}{2}}+1) \equiv 0 \bmod x$ lo que significa que para que se cumpla Fermat, tiene que suceder que $latex a^{\frac{x-1}{2}}\equiv 1$ ó $latex -1 \bmod x$ donde $latex -1\equiv x-1 \bmod x$ y con esto reducimos 1 ciclo más en la exponenciación modular que es muy costosa, y usamos $latex a=2$ ya que la exponenciación por 2 sólo es shifting a la izquierda, y usando 2 es hermoso para el algoritmo de exponenciación modular porque la complejidad
$latex o(3kn^{1.585})$ (Multiplicación Karasuba y reducción Montgomery para mod_exp hasta donde sé que usa BN de OpenSSL) esperada baja considerablemente teniendo muchos 0's en su expresión lo que reduce pasos (por eso la $latex o(g[n]))$ y no la $latex O(g[n]))$), donde $latex 3k$ es el número de bits de $latex x$ (nota aquí que la $latex n$ representa la variable de complejidad y no el exponente), y con eso hemos encontrado los primos que mencioné al principio.
Espero opiniones, source code aquí
Eduardo Ruíz Duarte
twitter: @toorandom
Por Morbo aquí les dejo el más grande que he encontrado, tardó 3 minutos en 1 thread. el cual es $latex (3*8^{17129})-1$ el cual tiene 51,388 bits .
32026423315381466050277915530786335800393823366890894981259290036648161553494994617558347456939958845983080809781780843277379143842511321157300439716316621258468518963948059640880521931439098619360470902127202739263724498727354638561114775469410152002760785630729882805025686247898899808911618409162136670680087277684487378095087887490583145258613139912396900825975697214682477274814156070359889110867811362193110348467393951992492345402056332383241386444305433601523085645869776811285646919087537466338016988423008766811472396005675392998881736916741912590189429331612837325373810452416030933831306867192676710269198951414458490437515264053051733873759760089225408336099284078093859455689148594434825613934497979781554179399202461221624253778300943176804460380502043924360948006335930676276227451427823493631843987911309636588431232386671032205960984005755897461961694816343511105402244581305974926489787769176727530282950574991748927557944410793100152205427813737629867224719749629559616541154571702402344007533555385071678935056951177266337611794442895925353683999178922756717467868112921444235536843814816587988381808259378763566339936575469133821904985670022768297621487042685072937645035397418762898088879966518834617431717616238160653229933317675561804324889864152610093010599664552103022407658203362826225135467122903372349775404454265894274031612183834433948175013815731731843768742711463425691140151259964862216909975488504743216033971257070468582283917816001081411729083210816836157717534301930744010414980424399802727757779067704711766548222713340284109481557728641051371992861091880789035561130198577315011688318769929786698521625431301832480788848469161536541203402106348915684835706031086198583470841503903548287043913330764995542582104558499052946524398642023915418094252775225135009392516216639788849081686649422414816420666524703609315132700144025576596698848194947599190340291543335651139477044320381872498206346425778242974783028340973498127326252357750612335602225108453954123859141624811742539990879575619773935510158546410141054095024924790241748920937072243685910974276469625883231365286281146397745282169224983577575852655025299677792623835241690537842870710528349067292463062257545894983725514137453620357976030228008635191305568411517021214777322011903026859601083554815240483942419038213153965732868181464332882027463093394450027202039114912743513771018541173505400069482374254318086098853632651567194952960545899057851574317234825560325729148747127013748646167661011675033243786731813402924344723783663066299906756407070530905173417647177285662615563890874013554204722859804826783319723895173795270908631147615754087439314263020476261354882689909166015907511051623119212879465867556909644440100632138353562083646966088393779513894343599588950053243809581940981833880678424982730382004328421941439072636800592877300140048085384317222361179303861645355317608391899423839079837905186750572454810469022406363372588948686204901139113299980435620209872045747933603059130972696653746953604532417492903736570671296699105655923819429995588811467179873672852431251204448040809915863163514335540089427059903930482164420870043452193744616222493706789929016164765070777799153453961045107726915484605407070139659338306471198522417856040168525001743452798331018200032516982674115924542207247561332705748100446483628681758170277861279289599258673198185708528378663459785909178096390845218020629053192057841759202932782309711814026123607150376911940748135836533906883752444763036721353897269880408805386078398045366480484951224112577584082675114895273853399084137327610229509328970706333462386945933615225142344089090446121520471032079274695108327379700854569636711391422529411618554876423454704114335714668077792468687086576736091448314825802520170346995090349720987439473605228224586805882340461196462558836145583970685095961833008585739864656363328302986709618224658592061790170440213776071852284933724917317499943202018446618210793294932831097623750797416246378349485892742882242489517967732592792481355599182598675646982241076442612020185511034050637482303910568507849800434585110875928913264144917561728507483873787584779156636819491649231469052768465384827615887208338319057096162237372005045429022403914234522895948109125618822616830011877945500320746041816052399512404707120200149549307311742265568523260555270588190891088146372739404374609532572772005797711009523114710103299579557147452176909952118545682110695102391553837852971501889513088222486987723921202415262209457238513791459203972870093386953048894801746214435712103477352922752928791906655786957516121929344278692478022077201558938914429157414192182892992028571663350174293119784111516284937872290882995528284151163236783105238160116300616254926975435140120536460294894410442753982342285715596774450547688510540950609379199176038748244276624271511162021898465702381739554745903292368453929023793055915664947937134935491330980718736217997428692810379092480664406511201873764269913663647020985956314161402000383439218120742135271552526071319102832539386295104448025731371374719348527163508063409657644511483601027063141269736285818775573658317881599404287364002332020457775029972569361743675624369268068117893284658209857784788545339202829190234333573510725635332114732388415720177686698830992999310828225254838530442450211498457933037804583792899416998160092466471334917779332924285621209393547865615433381452726968988212217944363239160938499077454607308202875136763555648760496640998480414396908114196518199386149585672336456043989071695238312288960081259962428139207487337862311363664235353355741056558668800464140710661218731996083813228309464181512824198473099835338147549021620784938152526403884390915371010004103078720376198785754267231632364475196249423028430296607633185992949806664821669508769010395593020867265768241356602352619944658174291464218293290651513925863985300257092863217772635441366596007681209046202751531928654365904486480637896037524609924560756737487555941653455392568655608180047527596306525572672891104374795309986323951969131709938262130944930794116800383445065248433923593381063574380087876957452711241937139283341986739106521622406898428983948046724085183024676505731621744665800497853221066191995732134553165719198648689135257528892602964255853707448817858352523437863421426102418117389544983206042308860683466269434657391645604299058196009634534319799146142598318942762623665930578733123571550032271299551114477333140685887321380068779030520881901530995711544355981117803607975968517499227648018428854655983473350493961762777920029051990792375397413824629029725111324189020468036861701447775824977257286314969930798035433627722690476216793743259593862757494785251530728454141362285932172007019448646822993271982444067467511428273397361690368237878111466206232963438330207726200080194611554342535208143831928801129239615572665628913222777854337631162257572382401793069038204155873152194648221501879285765056884379731159884546949750078461272929585042335506924134975880741347636497891449035978435021137529059174101402963872488774055561871763906005995523112899268150145675230528838855491232516570415185657872854886290162991073611832895236728088095860213006479909366614293585377658649333618462661081337250855184818048918280095216771124919354017900316074686948848666096561888434199822022864315541727689104723180042673931538717736387214138023901177682380480573112291135017398314529185431570271124814738098761072609216606999034113642258974107978719402360004973983466905902220813267671856406327086943579910433158637016416320152392435734326402865259058273022480138148188943021020384024506061902144679691028765137048209827552145995276652839943973336959426861497791033259830231723590523648498835822832310074455043040176962529346513059433633982359304138147553887485074486267391219132827142128335706403319422134084444025461591415872438467681229654425434633494593254114591133359674756811870187942825563687040492646952300630610982000264767473553602225155962233169190888460758352343896019871785984159532458130055709200931106493045763269590995530937189497063631830785082964079799523231260807321064954724345171548330473944837948003158443648883656429657821491956256504263890572005938508038381077649008380039581215475512164674386754377503163134803108273243041775665133283203530877641413091640784342349226191942006609524592938809381209539984692931251689753565266660069225820293301694201093380755714940533267406389212538472737345389920939638830120261737007640910540478856973611235739472554054732492599378321173386948659654872894505995568627052612775511578286760509286861768721974406755260200693773145017206683870773831784040386709044145859000178680454409827037232424821580153078526733906602635501448413155506471616532000380246549340334416808898434387410310767186271678651657125956330997135514287078037552835249014425147171712299257324870293646478104446879005854587240740583374971104742080118407293376250478292379654435036077102162699707316802765421226043298626360886593259957682295399635161319003729817233310836488878679452228196539460170236747951470219093715468757201428276567346844650203948349754588389125473669983324294915461031237867790032803164212486116627265051342591429261672735326004971500809554757104809198941710250369014929980399788042439092012739807413496910294722408654685906467188445652852679463510111588848714966994012633053111140523488797686496074404075035403032823629222238696411817644483300212092444148203586311124377532534089957832358357772985060452544714354695728594506029245228474290363244268026739022540462324210220094777074046735835916531079392171548754284909023490741942672576020109502086289324949189131229866882158751044579431073510058638580112970399400848012598667869946183555382577600203193941610086977918428282164298924318017243031208758208540683610170253540720335918689087434714730194564568976981777204445322986698373283390613470588168852889384592420528734963148995278955127941606122747080059367271673385322580445859123918237395666091441934678389289512890922392344993878800705035425791621906338667172499766162845453799509129825300440130012452422744967544346925837444005229552678073813615644879122257996997585678579511199674812593313238824764101761027353677321483720341880084732506793520846691464229711911399127721595694352403218401554932929595580588474107092800484536679906402882561774736289011712497922621582368337057910519632385879773294033551311658003580394298225128044755081583957070106775832608786270843701706632218236607363754573786689965846170399266338261414148862926960078807493024676636241821780944571096941752160727585488941102816572881758376655843234513616963008536787097251683013326148161450318083878017455643651554618261609966657262498344963281756373673269194825457120102335098430053525126126433050268325257610505256130462410397690925472067734961438549322304026644954794880041403058925796970496923953825506922111728360818654368875624837101641043903975798923440983174868771201734139437540847299331370990285604146267866907128889409552307757336422613848203004832657228332873404485085691176592522515171277306509004682948792277048468532631094588527157849361469770828540588429898016076708761086577687829794189995013320624862541504004344723993123491408236967534492449686611053666809249670558680801820699727271874125672980265867805587536003161611257602573879807891275145042611104947170932266106091329413068356104455079652564819613052988898269750866283631671361118418750456959898175596314235967214072736323242812555211430437013788931433823216158115282033550906925064093752025137605666797295274782995312635995982152649414790767022457876214220333912735265753742268349688660929764774270479063514369370861571597970542022613471507522362653019693799529912763689666033819469364626587974886877639192115375028613651480474237164637235577738383600508857173217109336525549418866366010878280531299766307762080753760829697569168773083049209471459983537669269749153891301730779513444000645411763110787536847848686483217045928561483760722316598284514141270858839546812101630071239179032956638848984251827861941056826930437770466758033287498621544428023782166008169892843744703334403973198509454469653826983957736270787015555281492220757292858206568385304706192386416009657097062675214919086924216423433082063409209311813441547525266882033030668389112810244305096535177323575119407014819701961205635561634299118583642973681614473867812760938254926147367318960324585092493458614097308885022089170245855482501639479877016629089888620237451538542215959748191190996154872699122004208858124356425712289922851204949134411296871871505058976506035287831568373306323310695563258651236862057327569996796911418552990931961498290680579647629977698154027601737797565070075670436437896473389755670610648189530779671896891147235752619825335341831322815436136245747406230116513486353562601815554701725083110004688886614174662693748369757301146366654631875732233511601846261172108525514149644247885971023535804115307394827643499777188215486121755438199799974589394310076094346886917173548688179362619895779807540625016179427636036019351588403299774724856215195371747489704244497091701187959447220506739300275179481331762578140018563599145933801046835852603238159978903048913593666079142988674647257869565599811291804268574482598601239002812924615248443546197951688030321300760876091551080394357570206848563007174933062203385569468701074474453445181914471929569957932053554812974962824730533730321134981872742052460822465894315329796485647981106519209011070672227096921158799879437700574304848454981802421492286924451866419782080313978740292819201278161706224217725190371403757643026425623517826097611507643390259047590959932320545975284905982569652107326483812384715289985015459922154716822488321689550299263619341284113403436700781861588646420485438604540704027253441622650851675586492071210226532484984591013815461270342863783178683556187689063539912330972619666981892869317909270155819553452716936453676065787164609958676345722669724366516240566266437213654002248924605767519825524209815555833816522154978528910130474700299093317031044211046499872477143240327616617922983636426879957616855080920171289624631399643044926826859302733475147604311961190699077188429263949513452638462772625523478131071010133683582732987635966888334444166545133327777444950723754056816509592356504697117206941441165086849098972184037539794426671844030825833598853963114053824272932540517635711466482759453660721092062140898635239403909145540034949144004169612367460203691048738979781621164967729498632571736651022575485003412715989505615918816044598119400139330568417038172877563337999983250824731788378825900711541921702608288945567177423468793416752642938061266551297859681355577376381057215722300869238366170358650342498421330507990183857556924897965345058959140779958958539450309245045806703864539795637542958885985702987995937529239296860784907341981603308133066795374351314700910108776438125912477798323517153710396153185384044296997650774166602334305686826095686072735997307216804515717706691064830830039274370337931442167526341392075205171338884374247627205672231641873433802187192310055109876868922197752744289994593440764759961686774526545765501935087092519809508864042914699268218861038321472400274858274379127887774609639024710710010354246368036753163679085955338782446481692502409390267529445980102117063380633877777427298698152522242904231639473660870716516498037296215852813557422423482411368716331820788501942447761707086086382920195423676221267291530130105693483847048880634760003583
No comments:
Post a Comment