Tuesday, February 10, 2015

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



Monday, February 09, 2015

Complejos de de Rham y cohomología (Derivaciones parte 1/4)

Esta es una especie de continuación de un post donde traté de llegar desde el cálculo hasta la cohomología de de Rham utilizando rotacional, divergencia y gradiente (De Rham), pero es hora de hacerlo formalmente, y para ello necesitaremos imaginarnos unos espacios que se llaman diferenciales de Kähler, antes hablé de diferenciales y k-formas diferenciales , pero lo retomaremos, el punto de este post será poder usar la cohomología de de Rham para saber si una curva hiperelíptica sobre un campo finito es segura criptográficamente hablando calculando el número de elementos de su jacobiana el cuál nos dice sobre su seguridad de acuerdo a su factorización, y para esto utilizaremos el teorema del punto fijo de Lefschetz sobre el morfismo de Frobenius en característica 0 p-ádico (lift a $latex \mathbb{Q}_p$) definido en el primer grupo de cohomología de una subálgebra de de Rham, para eso primero veremos como construir toda el álgebra de de Rham usando diferenciales de Kähler.

Pero antes de todo esto necesitamos empezar con los preliminares, que serán el concepto de derivacion en cualquier álgebra.


Derivaciones en un punto

La derivada en dirección de un vector tangente $latex v$ a un punto $latex p\in \mathbb{R}^n$ de una función $latex f\in C^{\infty}(\mathbb{R}^n)$ es un número real:

$latex D_v(f):=\sum_{i=1}^n x_i(v) \frac{\partial f}{\partial x_i}(p)$

Donde $latex x_i$ son las coordenadas en $latex \mathbb{R}^n$ y $latex x_i(v)=v_i$ (i-ésimo componente de $latex v$)

Para todo vector tangente $latex v$ a un punto $latex p\in \mathbb{R}^n$ tenemos que la derivada direccional en $latex p$ nos da un mapeo de espacios vectoriales

$latex D_v:C^{\infty}_p\rightarrow \mathbb{R}$


que manda $latex f$ definida en $latex p$ a un número real, en general la función $latex D_v$ está definida como:

$latex D_v=\sum x_i(v) \frac{\partial}{\partial x^{i}}\mid_p$


Tenemos que $latex \forall v\in T_p(\mathbb{R}^n)$ hay un $latex D_v$ y todos cumplen la regla de Leibniz, es decir $latex D_v(fg)=(D_vf)g(p)+f(p)D_vg$.

Todos los mapeos $latex \mathbb{R}$-lineales $latex D:C^{\infty}_p\rightarrow \mathbb{R}$ que satisfacen la regla de Leibniz son derivaciones en $latex p$  y denotamos a todas las derivaciones en $latex p$ como $latex \mathbb{D}_p(\mathbb{R}^n)$ y de hecho este espacio es un espacio vectorial ya que dos derivaciones sumadas en el mismo punto es una derivación, y como es $latex \mathbb{R}$-lineal no pierden la propiedad de Leibniz al multiplicarlas por un escalar, entonces por ahora ya tenemos que TODAS las derivadas direccionales en $latex p$ son todas las derivadas en $latex p$ por lo que tenemos un mapeo.


$latex \phi:T_p(\mathbb{R}^n)\rightarrow \mathbb{D}_p(\mathbb{R}^n)$
$latex v\mapsto D_v=\sum x_i(v) \frac{\partial}{\partial x^{i}}\mid_p$


Como $latex D_v$ es lineal en $latex v$ , el mapeo $latex \phi$ es un mapeo de espacios vectoriales, faltaría ver qué sucede con las constantes, es decir que si $latex D\in \mathbb{D}_p(\mathbb{R}^n)$ entonces si $latex c\in\mathbb{R}$ entonces $latex D(c)=0$ pero esto se sigue que la linealidad y la regla de Leibniz haciendo que $latex c=1c$.

Función $latex \delta$ de Kronecker

Ésta es una función muy útil para la notación
$latex \delta_j^i=\left\{\begin{array}{11} 1&\mbox{if } i=j\\ 0 & \mbox{if }i \neq j \end{array}\right$

Ahora, tenemos que es fácil demostrar que $latex \phi$ definido previamente es un isomorfismo, es decir $latex T_p(\mathbb{R}^n) \cong \mathbb{D}_p(\mathbb{R}^n)$ ya que si procedemos naturalmente al suponer que $latex D_v=0$ para algún $latex v\in T_p(\mathbb{R}^n)$ entonces $latex 0=D_v(x_j)=\sum_i v^i \frac{\partial}{\partial x_i}\mid_p x_j = \sum_i x_i(v)\delta_i^j = x_j(v)$ y entonces $latex v=0$ lo que nos dice que $latex \phi$ es inyectiva.

Aquí la función $latex \delta$ nos ayuda a eliminar las parciales en las variables que no son iguales al índice con notación más limpia, la suprayectividad la pueden demostrar ustedes.

Lo que sucede aquí es que para todo vector tangente a $latex p$ tenemos una derivación en $latex p$ entonces si ambos son espacios vectoriales, uno de puntos... y otro de derivaciones, lo más natural es identificar sus bases estándares, si $latex \lbrace e_1,e_2,...,e_n \rbrace$ es base de $latex T_p(\mathbb{R}^n)$ entonces bajo este isomorfismo tenemos que:

$latex \phi(e_i) = \sum_i \delta_i^j \frac{\partial}{\partial x_i}\mid_p=\frac{\partial}{\partial x_i}$

Por lo que: 

$latex \bigg \lbrace \frac{\partial}{\partial x_1}\mid _p,..., \frac{\partial}{\partial x_n}\mid_p\bigg\rbrace$ genera al espacio vectorial $latex \mathbb{D}_p(\mathbb{R}^n)$ y es su base estándar.

Con esto nos conviene denotar a los vectores $latex v\in T_p(\mathbb{R}^n)$ tangentes a $latex p$ más explícitamente en términos de la base de $latex \mathbb{D}_p(\mathbb{R}^n)$ los cuales son puntos $latex v=\sum v_i e_i = \sum x_i(v) e_i = (v_1,...,v_n)$ como:

$latex v=\sum v_i \frac{\partial}{\partial x_i}\mid_p$


Campos vectoriales

Si $latex U\subset \mathbb{R}^n$ es un abierto un campo vectorial $latex X$ es una función que asigna a $latex p\in U$ un vector tangente $latex X_p \in T_p(\mathbb{R})^n$, este vector $latex X_p$ en términos de la base $latex \bigg \lbrace \frac{\partial}{\partial x_j}\mid_p \bigg \rbrace$ es:

$latex X_p=\sum a_i(p) \frac{\partial}{\partial x_i}\mid_p = (a_1,...,a_n)$ 

con $latex p\in U$, $latex a_i\in C^\infty(U)$, $latex a_i(p)\in \mathbb{R}$ 

Podemos omitir la $latex p$ en este caso y decir que el campo vectorial $latex X=\sum a_i \partial/\partial x_j$ 

Ejemplos típicos:

$latex X=\frac{-y}{\sqrt{x^2+y^2}}\frac{\partial}{\partial x}+\frac{x}{\sqrt{x^2+y^2}}\frac{\partial}{\partial y}= \bigg ( \frac{-y}{\sqrt{x^2+y^2}},\frac{x}{\sqrt{x^2+y^2}} \bigg )$

y

$latex Z=\frac{x\partial}{\partial x} + \frac{-y\partial}{\partial y}=(x,-y)$

Es importante la notación como punto y la de vector para que noten la base y la importancia del operador $latex \partial/\partial x_i$

Aquí están los dos campos vectoriales dibujados en $latex \mathbb{R}^2\setminus \lbrace 0 \rbrace$ y $latex \mathbb{R}^2$ respectivamente, ustedes vean la definición y el dibujo.





Entonces un campo vectorial $latex X=\sum a_i \partial/\partial x_j$ nos permite "mover" la $latex p\in U\subset \mathbb{R}^n$  , podemos multiplicar cualquier función $latex f\in C^{\infty}(U)$ por un campo vectorial $latex X$ y aún así seguir teniendo un campo vectorial ya que $latex fX=\sum (fa^i)\partial/\partial x_i$ es un campo vectorial $latex C^\infty$ en $latex U$ por lo que podemos sumarlos y multiplicar por 'escalares' del anillo $latex C^\infty(U)$ entonces tenemos que todos los campos vectoriales en $latex U$ los denotamos por $latex \mathfrak{X}(U)$ es un $latex C^\infty(U)-$módulo 


Derivaciones a partir de campos vectoriales

Vamos a definir más derivaciones ahora a partir de esto.

Sea $latex X \in \mathfrak{X}(U)$ con $latex U\subset \mathbb{R}^n$ y sea $latex f\in C^{\infty}(U)$ definimos la función $latex Xf$ en $latex U$ como:

$latex (Xf)(p)=X_pf = \sun a_i(p)\frac{\partial f}{\partial x_i}(p)$   $latex \forall p\in U$

sin la $latex p$ tenemos que la función es $latex Xf=\sum a_i \frac{\partial f}{\partial x_i}$
donde se ve claramente que $latex Xf\in C^\infty(U)$ , por lo que podemos definir a el campo vectorial $latex X$ como una función que mapea funciones a funciones

$latex X:C^{\infty}(U)\rightarrow C^\infty(U)$
$latex f\mapsto Xf$


Como podemos intuirlo este mapeo para todo campo vectorial cumple la regla de Leibniz es decir

$latex X(fg)=(Xf)g+fXg$

Ya que puntualmente se cumplirá la regla de Leibniz si ustedes lo verifican.

Una derivación en el álgebra $latex C^\infty(U)$ sobre  $latex \mathbb{R}$ es un mapeo $latex \mathbb{R}$-lineal
$latex D:C^{\infty}(U)\rightarrow C^{\infty}(U)$ tal que $latex D(ab)=(Da)b+aDb$ donde $latex a,b\in C^{\infty}(U)$ .

Todas las derivaciones de $latex C^{\infty}(U)$ están cerradas bajo suma y multiplicaciones escalar por lo que forma un espacio vectorial el cual lo llamamos $latex Der(C^{\infty}(U))$ y esto funciona con cualquier álgebra, no sólo con las funciones infinito diferenciales, por lo que tenemos el siguiente mapeo


$latex \Phi:\mathfrak{X}(U)\rightarrow Der(C^{\infty}(U))$
$latex X\mapsto [f\mapsto Xf]$

Esto como imaginarán es un isomorfismo lo que quiere decir es que todos los campos vectoriales de un abierto $latex U$ pueden ser identificados con derivaciones del álgebra $latex C^{\infty}(U)$.