Encontrando números primos grandes con approach matemático-computacional

Si estás de un smartphone no se verán los símbolos, probablemente quieras verlos así que haz click aquí

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

Teorema de Riemann-Roch y divisores en criptografía (Parte 1: campos de funciones y gavillas sobre variedades)

En criptografía muchos han visto que se estudian las curvas elípticas y menos frecuentemente las curvas hiperelípticas, algunos recordarán la estructura de grupo que se le da a una curva elíptica $latex C$ con la usual regla de intersección de una recta con la curva haciendo uso abusivo del teorema de Bézout para fundamentar la estructura de grupo que hay en sus puntos, que más formalmente, es la estructura de grupo que hay en las clases de divisores formados por las sumas formales de ideales máximos de todos los subanillos del campo de funciones de $latex \mathbb{K}(C)$, este grupo es el grupo de Picard de orden 0 de la curva $latex C$ que es:

 $latex Pic^0(C) = Div^0(C)/Prin(C) \cong \mathbb{J}(C)$.

Esta manera de ver las cosas NO es para complicar lo ya existente, sino es con propósitos de poder exprimir más la teoría que lo respalda para poder investigarlo mejor y generalizarlo a otras curvas no elípticas.

La estructura de grupo de manera inocente o usual se puede ver en muchos textos pobres en matemáticas pero tal vez ricos en aplicaciones criptográficas como esto:

El propósito de este post será el poder resumirte la teoría que hay detrás.


Comencemos con unas definiciones, voy a suponer que quien me lee está familiarizado con la topología de Zariski la cual está definida por los conjuntos algebraicos como cerrados, de hecho estas definiciones son las interesantes para la topología de Zariski, y con esto pueden demostrar fácilmente las propiedades de espacio topológico.

Definición (ceros):
Sea $latex A:= \mathbb{K}[x_1,...,x_n]$ el anillo de polinomios en $latex n$ variables sobre el campo algebraicamente cerrado $latex \mathbb{K}$ y $latex J \subset \mathbb{K}[x_1,...,x_n]$ un ideal, entonces definimos el conjunto de ceros del ideal $latex J$ como:

$latex V(J):=\lbrace P\in \mathbb{A}^{n}_{\mathbb{K}} \mid f(P)=0$     $latex \forall f\in J\rbrace$


Definición (variedad afín): Un subconjunto $latex X\subset \mathbb{A}^n_{\mathbb{K}}$ es un conjunto algebraico (variedad afín) en el espacio afín $latex \mathbb{A}^n_{\mathbb{K}}$ si existe un $latex T\subset \mathbb{K}[x_1,...,x_n]$ tal que:

$latex X=V(T)$

Decimos que $latex X$ es un cerrado de Zariski, en la topología dada a  $latex \mathbb{A}^n_{\mathbb{K}}$.

Veámos primero lo que es el anillo de coordenadas de una variedad.

Definición (función polinomial en la variedad V): Una función polinomial es un mapeo $latex f:V \rightarrow \mathbb{K}$ tal que existe un $latex F\in \mathbb{K}[x_1,...,x_n]$ con $latex f(P)=F(P)$  $latex \forall P\in V$

Este polinomio $latex F$ no está únicamente determinado por los valores que toma en $latex V$ o sea si tenemos $latex F,G\in \mathbb{K}[x_1,...,x_n]$:


$latex F\mid_{V}=G\mid_{V} \Leftrightarrow (F-G)\mid_{V}=0 \Leftrightarrow F-G\in I(V)$

Donde:

$latex I(V):=\lbrace f\in \mathbb{K}[x_1,...,x_n] \mid f(P)=0$    $latex \forall P\in V\rbrace$



Esta definición de función polinomial y su relación de igualdad con otros polinomios, huele a una relación de equivalencia, por lo que vamos a suponer que lo es y se deja a quien lee para que lo demuestre y tenemos que:

Denotaremos ahora a $latex V$ como el conjunto algebraico $latex V(I)$ donde $latex I$ es ideal de $latex \mathbb{K}[x_1,...,x_n]$

Definición (anillo de coordenadas de una variedad): Un anillo de coordenadas de una variedad $latex V$ es:

$latex \mathbb{K}[V]:=\mathbb{K}[x_1,...,x_n]/I(V)$

Este anillo sabemos que es un dominio entero si $latex I(V)$ es un ideal primo, y esto naturalmente sucede si $latex V$ es irreducible , es decir no es union de otros cerrados de zariski


De lo anterior sobre funciones polinomiales y la última definición se puede demostrar que:

$latex K[V]=\lbrace f \mid f:V\rightarrow \mathbb{K}$ es una función polinomial $latex \rbrace$

Cabe notar que se le llama anillo de coordenadas porque las funciones que te dan la i-ésima coordenada de los elementos de $latex V$, $latex x_i$ son las generadoras de $latex \mathbb{K}[V]$

Es fácil ver que $latex \mathbb{K}[ \mathbb{A}^n_{\mathbb{K}}]=\mathbb{K}[x_1,...,x_n]$ y que el anillo $latex \mathbb{K}[V]$ juega el papel para $latex V$ como $latex \mathbb{K}[x_1,...,x_n]$ para $latex \mathbb{A}^n_{\mathbb{K}}$

Observaciónes sobre lo anterior con respecto a la topología de Zariski en $latex \mathbb{A}^n_{\mathbb{K}}$.

• Los ideales primos de $latex \mathbb{K}[V]$ están en correspondencia 1:1 con irreducibles $latex W\subset V$
• Los ideales máximos de  $latex \mathbb{K}[V]$ están en correspondencia 1:1 con los puntos de $latex V$
• Los ideales radicales de $latex \mathbb{K}[V]$ están en correspondencia 1:1 con los cerrados $latex W\subset V$

Definición (campo de funciones de V): El campo de funciones de $latex V$ es el campo de fracciones de $latex \mathbb{K}[V]$ y es denotado por $latex \mathbb{K}(V)$, las $latex f\in \mathbb{K}(V)$ se llaman funciones racionales sobre $latex V$

Definición (función regular en P): Una función $latex f\in \mathbb{K}(V)$ y $latex P\in V$ se dice que es regular en $latex P$ si $latex f=\frac{g}{h}$ con $latex h(P)\neq 0$, y definimos:

$latex dom(f):=\lbrace P\in V \mid f$ es regular en $latex P\rbrace$

Proposición: El conjunto:

$latex V_f:=\lbrace P\in V\mid f(P)\neq 0\rbrace$

es un abierto de $latex V$


Teorema: 

• $latex dom(f)$ es abierto y denso en $latex V$
• $latex dom(f)=V\Leftrightarrow f\in \mathbb{K}[V]$
• $latex V_g\subset dom(f) \Leftrightarrow f\in \mathbb{K}[V][1/g]$

Ahora, entraremos a un concepto central, para poder analizar una variedad localmente... para esto sabemos que un anillo local sólo tienen un ideal máximo, y tenemos que la siguiente definición

Definición (anillo de funciones regulares): El anillo de funciones regulares de $latex V$ localizado en el punto $latex P\in V$ es:

$latex O_{V,P}:=\lbrace f\in \mathbb{K}(V)\mid f$ es regular en $latex P\rbrace$

Es fácil demostrar que esto es en efecto un subanillo de $latex  \mathbb{K}(V)$ y que su único ideal máximo no deberá tener unidades por lo que su ideal máximo es:

$latex m_{P}:=\lbrace f/g \in \mathbb{K}(V)\mid f(P)=0, g(P)\neq 0 \rbrace$

Ahora vamos a la últma parte de este blog donde discutiremos la estructura de gavilla de una variedad

Estructura de gavilla de una variedad

Tenemos que el anillo $latex O_{V,P}$ es local y es un subanillo de $latex \mathbb{K}(V)$ y su ideal máximo es $latex m_{P}$, es fácil relacionar a $latex O_{V,P}$ con $latex \mathbb{K}[V]$ ya que con localización puedes demostrar que:

$latex \hat{m}_P=\lbrace f\in \mathbb{K}[V]\mid f(P)=0\rbrace=I(\lbrace P \rbrace)+I(V)\subset \mathbb{K}[V]$

Es máximo y:

$latex O_{V,P}=\mathbb{K}[V]_{\hat{m}_P}$


Es decir que $latex O_{V,P}$ es la localización del anillo de coordenadas de $latex V$ en el ideal máximo $latex \hat{m}_P$

Ahora vamos a definir el concepto final:

Definición-Teorema (estructura de gavilla en $latex O_{V}(U)$, germen y fibra ): Para todo abierto $latex U \subset V$ tenemos:

$latex O(U):=O_{V}(U):=\lbrace f\in \mathbb{K}(V) \mid f$ es regular en $latex U \rbrace$

Es una $latex \mathbb{K}-$álgebra con $latex O_{V}(\emptyset):=\lbrace 0 \rbrace$

Todos los $latex O_{V}(U)$ con $latex U\subset V$ forman una gavilla $latex O_V$ bajo la restricción de homomorfismos usual y el anillo $latex O_{V,P}$ es una fibra de la gavilla $latex O_V$  y los elementos $latex f\in O_{V,P}$ se les llama gérmenes de funciones y:

$latex O(V)=\mathbb{K}[V]$


La teoría de gavillas da una estructura rica a una variedad, en este caso , puede ser el de una curva elíptica o hiperelíptica

Saludos

Eduardo Ruiz Duarte (beck)
Twitter: @toorandom

Criptografía asimétrica combinatoria-algebraica no usual con bases de Gröbner

Siempre me ha gustado investigar estructuras algebraicas con el fin de poder ver si puedo sumergir criptografía asimétrica dura ahí, generalmente ésta basada en el problema de logaritmo discreto en curvas algebraicas; considero que es mi área favorita de trabajo y posiblemente a lo que me vaya a dedicar el resto de mi vida, pero aquí vamos a ver algo diferente que podría o no ser seguro en su implementación pero no deja de ser interesante.


Primero vamos a analizar un caso particular de un esquema de cifrado con polinomios y luego veremos cómo generalizarlo y definiendo con bases de Gröbner.

Vamos a utilizar cualquier $latex \mathbb{F}-algebra$ de tipo finito, i.e. finitamente generada, con grado de trascendencia $latex n$ veamos cómo funciona esto.

Construcción del algoritmo de cifrado:

Sea $latex \mathbb{F}$ un campo finito y $latex T=\lbrace t_{i}\rbrace_{i=1}^{n}$ un conjunto de variables.


Queremos que $latex A$ reciba un mensaje $latex m\in \mathbb{F}$ de $latex B$ cifrado.

• $latex A$ va a escoger un vector aleatorio $latex y\in \mathbb{F}^{n}$ como llave privada

• $latex A$ escoge polinomios como llave pública $latex P=\lbrace q_j \rbrace \subseteq \mathbb{F}[T]$ tal que $latex q_j(y)=0$ $latex \forall j$

         Es fácil generar polinomios con los ceros que necesitamos, por ejemplo si
         ya tenemos la llave privada $latex y$ tomas $latex q_j = \hat {q}_j - \hat{q}_j(y)$ con $latex \hat{q}_j \in \mathbb{F}[T]$.
         Lo que no es tan fácil es escogerlos seguros y álgebraicamente independientes, pero hay métodos.

•  $latex B$ quiere mandar el mensaje $latex m\in \mathbb{F}$ a $latex A$ por lo que se toma un elemento del ideal generado por la llave pública $latex P$ que es $latex (P) \subset \mathbb{F}[T]$:

   $latex p = \displaystyle \sum { h_j q_j } $

En otras palabras escoge $latex \lbrace h_j \rbrace \subset \mathbb{F}[T]$ y genera el polinomio $latex p$

• $latex B$ le manda a $latex A$ el polinomio multivariable        

$latex c=p+m$


Este esquema de cifrado funciona ya que $latex A$ va a poder obtener $latex m\in \mathbb{F}$ ya que conoce los ceros de los generadores del ideal $latex (P)\in \mathbb{F}[T]$ por lo tanto conoce los ceros de $latex p$ independientemente de los $latex \lbrace h_j \rbrace$ , por lo que usando su llave privada $latex y$ tenemos que $latex A$ puede calcular fácilmente

$latex c(y)=p(y)+m=m$


Nota que este esquema de cifrado es probabilístico y no determinístico, i.e. en cada
ocasión que se cifra $latex m$ es diferente ya que depende de los elementos del ideal de la llave pública que se tomen.

Su seguridad también depende de los ceros del conjunto algebraico generado por $latex B$, en este caso cada cero sería $latex y=(y_1,y_2,...,y_n)$ y cualquier cero en la intersección de las hipersuperficies funcionaría, su seguridad depende de la solución de sistemas de ecuaciones algebraicos no lineales de grado arbitrario , es decir, en dimensión grande y con un número grande de polinomios generadores independientes del ideal de la llave pública, es POSIBLE tener criptografía segura, digo posible porque no se ha demostrado que su solución NO sea en tiempo polinomial, pero creo que podría ser más seguro si usamos la teoría de bases de Gröbner.

Generalización:

Veamos unas definiciones que vienen de la teoría de bases de Gröbner para poder intentar una generalización, las cuales incluyen la reducción módulo otro polinomio multivariable, donde los monomios deberán estar ordenados bajo cierto orden lexicográfico.

Definición (módulo polinomio multivariable): Decimos que $latex f$ reduce a $latex h$ módulo $latex g$ parcialmente si $latex a_{i}X^{i}$ es un monomio de $latex f$ que es divisible por el término líder de $latex g$ ,$latex lt(g)$ (líder bajo el órden con el que organicemos nuestros polinomios como el lexicográfico por grado) y que sucede que:

$latex h=f-\frac{a_{i}X^{i}}{lt(g)}g$

Donde escribimos que $latex f \equiv h \bmod g$

Definición (módulo un conjunto de polinomios): Sea $latex G=\lbrace g_1,...,g_l \rbrace \subset \mathbb{F}[T]$ y sea $latex f\in \mathbb{F}[T]$, entonces decimos que $latex f$ se reduce a $latex h$ módulo $latex G$ ($latex f \equiv h \bmod G$) si tenemos la sucesión $latex h_0=f, ..., h_k=h$ tal que $latex h_j \equiv h_{j+1} \bmod g$ para algún $latex g\in G$

Definición (base de Gröbner): Sea $latex F=\lbrace g_1, ..., g_l \rbrace \subset \mathbb{F}[T]$ un conjunto finito de polinomios en $latex m=|T|$ variables e $latex I\subset \mathbb{F}[T]$ el ideal generado por $latex F$, decimos que $latex F$ es una base de Gröbner para el ideal $latex I$ si para todo $latex 0\neq f\in I$ se tiene que $latex lt(g_k)\mid lt(f)$ para algún $latex g_k\in F$


Teorema: F es una base de Gröbner para un ideal $latex I\subset \mathbb{F}[T]$ $latex \Leftrightarrow$ $latex \forall f \in I$ $latex f\equiv 0 \bmod F$

Con este último teorema nos resulta TRIVIAL el poder construir ideales aleatorios (finitos, anillos noetherianos) y su base de Gröbner asociada.

Regresando al esquema de cifrado original y rehaciéndolo con esto:

$latex A$ escoge una base de Gröbner $latex G=\lbrace g_1,...,g_l\rbrace$ de un ideal $latex I \subset \mathbb{F}[T]$, la llave privada de $latex A$ es $latex G$.

Sea $latex S\subset \mathbb{F}[T]$ el conjunto de TODOS los polinomios que no pueden ser reducidos módulo $latex G$ (ve las definiciones anteriores), este $latex S$ realmente sería el conjunto de representantes del anillo $latex \mathbb{F}[T]/I$ como ya se lo habrán imaginado, ahora supón que $latex S$ es público, aunque $latex G$ no lo sea, tenemos que todo mensaje $latex m \in \mathbb{F}$ es un elemento de $latex S$.

Un ejemplo:


 Sea $latex T=\lbrace t_1,...,t_n\rbrace$ y $latex y \in \mathbb{F}^n$ un punto secreto, $latex A$ toma como base de gröbner $latex G=\lbrace t_1-y_1, ..., t_n - y_n\rbrace$  en este caso tenemos que $latex S=\mathbb{F}[T]/(G)\cong \mathbb{F}$ es el campo de las constantes.

Ahora $latex A$ escoge un conjunto como llave pública $latex P=\lbrace q_j \rbrace \subset I=(G)$, esto es fácil ya que  podría tomar un $latex \hat{q}_j\in \mathbb{F}[T]$ arbitrario y calcular $latex q_j = \hat{q}_j - \overline{q}_j$ donde $latex \overline{q}_j \in S$ y $latex \hat{q}_j \equiv \overline{q}_j \bmod G$

Consideremos el ideal $latex J=(P)$ y $latex m\in S$, entonces $latex B$ le cifrará a $latex A$ el mensaje $latex m$ escogiendo al azar un elemento de $latex J$, ya que la llave pública de $latex A$ es $latex P$ y $latex J=(P)$:

$latex p=\displaystyle \sum h_{j}q{j} \in J$

$latex B$ le manda a $latex A$ $latex c=p+m$

$latex A$ al recibir $latex c$ sólo tendría que reducirlo módulo la base de Gröbner $latex G$ 

En este ejemplo cuando $latex G=\lbrace t_i - y_i \rbrace$ sería el caso particular que vimos en el principio.


Esta criptografía es rara y no es usada ni considerada AÚN SEGURA debido a que falta demostrar que tan dificil es el problema en términos de complejidad.


Espero les haya gustado

Eduardo Ruíz Duarte (beck)
@toorandom

Álgebra de votaciones para procesos electorales

Últimamente se ha hecho una modita el rechazar elecciones electrónicas por razones las cuales siento que carecen de fundamentos.

Hice una presentación la cual no fue del todo aprovechada ya que donde lo iba a exponer no sirvió el proyector, pero tambien expongo un punto de vista distinto al usual para realizar votaciones electrónicas (con criptografía y no con solo contadores electrónicos y cables), como valor agregado obviamente salvarás millones de árboles.

En el documento no toco temas socio-políticos los cuales son los que causan polémica, sino tres algoritmos necesarios para

poder realizar un proceso electoral electrónico.

Este documento puede ser un poco complicado, así que a manera de resumen explico los tres algoritmos:


1.Zero-Knowledge: Este algoritmo permitirá a una persona A poderle demostrar a B que A conoce un secreto "s" y B quedará totalmente convencido de que "s" existe pero sin que A haya revelado s, solamente a B se le revelara la veracidad de la existencia de "s". (Se utiliza el problema de logaritmo discreto), un poco mas técnico, el algoritmo podrá mostrarle a B que A posee una llave que abre un mensaje sin que el mensaje sea revelado ni la llave.
Un ejemplo que luego ocupo para explicar es: "¿Cómo puedo convencerte de que realmente si tengo la receta de la coca-cola para que me la pagues primero y luego te la de?"

2. Shamir threshold: Este algoritmo permitirá que N personas tengan un "pedazo" de secreto "s" y que si k personas (k menor que s) se juntan puedan reconstruir el secreto "s" de tal manera que los pedazos de secreto nunca podrán construirse a partir k-1 personas.

Por ejemplo, imaginen que una bóveda es de 10 personas, pero por alguna extraña razón quieren que si se juntan cualesquiera 3 personas de esos 10 puedan abrirla. La bóveda tiene un password y este solo se puede construir cuando se juntan 3 personas y no menos. (Este algoritmo utiliza polinomios de Lagrange)


3. Diffie-Hellman

¿Cómo podemos negociar una llave secreta dos personas aunque haya un tercero oyendo TODA nuestra negociación?
Esto utiliza logaritmo discreto.

Y por ultimo utilizando Elgamal se simula un esquema de votación de en el conjunto {-1,1} (si o no) , esto es suficiente ya que si hay mas candidatos es como hacer (a,b) o c es ( (a,b), c) (suma directa) .


Como les digo, aquí no discuto la honradez o la educación de la banda para poder votar, sino que hipotéticamente es posible y es seguro.

Con este esquema los votantes podrían hacer lo siguiente:

1. Checar que su voto realmente fue contado
2. Checar que su voto fue contado por quién ellos eligieron
3. Sufragio total, solo el votante puede verificar el punto 2 (todo esto protegido con criptografía asimétrica y certificados)
4. Los votantes pueden contar los votos y quedar convencidos de que el conteo no fué truqueado

A diferencia de los esquemas habituales (Brasil , Australia, Estados Unidos) , con criptografía se pueden asegurar cosas.

y no solamente incrementar un contador como lo ha sido en esos paises. Con criptografía se puede hacer que realmente el voto sea secreto, efectivo y robusto ante tramposos.


Les dejo la liga: aquí


Saludos Eduardo Ruiz Duarte (beck)