Anar al contingut

Récorts en logaritmos discrets

De L'Enciclopèdia, la wikipedia en valencià
45px|link=|alt=
El texto que sigue es una traducción defectuosa. Si quieres colaborar con Wikipedia, busca el artículo original y mejora esta traducción.
Copia y pega el siguiente código en la página de discusión del autor de este artículo: {{subst:Aviso mal traducido|Récorts en logaritmos discrets}} ~~~~

Categoría:Wikipedia:Traducciones para mejorar

Els récorts en logaritmos discrets són els millors resultats obtinguts fins a la data en la resolució del problema del logaritmo discret, consistent en trobar solucions de x per a l'equació gx = h, daus dos elements g i h pertanyents a un grup cíclico finito G. La dificultat de resoldre el problema és la base de la seguritat de numerosos sistemes criptográficos, entre ells el protocol Diffie-Hellman, el sifrat ElGamal, l'Algoritme de Firma Digital (DSA), o la criptografia de curves elíptiques. L'elecció més habitual de G utilisada en eixos algoritmes inclou el grup multiplicativo de sancers mòdul p, el grup multiplicativo d'un cos finito, i el conjunt de punts d'una curva elíptica sobre un cos finito.

Sancers mòdul p

[editar | editar còdic]

El 18 de juny de 2005, Antoine Joux i Reynald Lercier varen anunciar la computació d'un logaritmo discret mòdul un número primo fort de 130 dígits (431 bits) en tres semanes, utilisant per a això un ordenador HP AlphaServer GS1280 en 16 processadors a 1.15 GHz eixecutant un algoritme de garbell general del cos de números (GNFS).[1]

El 5 de febrer de 2007, va ser superat en l'anunci de Thorsten Kleinjung de la computació d'un logaritmo discret mòdul un número primo fort de 160 dígits (530 bits), usant de nou la garbell general del cos de números. La major part de la computació va ser realisada utilisant temps mort de CPU en varis ordenadors d'un clúster de computació en paralel.[2]

Cossos finitos

[editar | editar còdic]

El récort actual (a data de 2013) en un cos finito de característica 2 va ser anunciat per Antoine Joux el 21 de maig de 2013. El seu equip va ser capaç de computar logaritmos discrets en el cos de 26168 = (2257)24 elements usant per a això menys de 550 hores de CPU. Esta computació va ser realisada utilisant el mateix algoritme de càlcul amprat en la computació recent del cos en 24080 elements.[3]

Els récorts anteriors en cossos finitios de característica 2 varen ser anunciats per:

  • Robert Granger, Faruk Göloğlu, Gary McGuire, i Jens Zumbragel l'11 d'abril 2013. La nova computació tractava en el cos de 26120 elements i va demorar 749,5 hores de CPU.
  • Antoine Joux el 22 de març de 2013. Va utilisar el mateix algoritme[4] per a cossos de característica chicoteta que en l'anterior computació del cos de 21778 elements. Es va computar en el cos en 24080 elements, representat com una extensió de grau 255 del cos en 216 elements, utilisant per a això menys de 14100 hores de CPU.[5]


  • Robert Granger, Faruk Göloğlu, Gary McGuire, i Jens Zumbragel el 19 de febrer de 2013. Varen utilisar una nova variant de la garbell general del cos de números en un cos base de tamany mig, per a cossos binarios, per a computar un logaritmo discret en un cos de 21971 elements. Per a poder usar un cos base de tamany mig varen representar el cos com una extensió de grau 73 del cos de 227 elements. La computació va demorar 3132 hores de CPU en un clúster SGI Altix ICE 8200EX utilisant processadors de 6 núcleus Intel (Westmere) Xeon E5650.[6]
  • Antoine Joux l'11 de febrer de 2013. Utilisava un nou algoritme per a cossos de característica menuda. Es va computar en un cos de 21778 elements, representedo com una extensió de grau 127 del cos en 214 elements. El còmput es va realisar en menys de 220 hores de CPU.[7]

El récort actual (a data de 2013) per a un cos finito de característica 2 de grau primer va ser anunciat pel grup CARAMEL el 6 d'abril de 2013. Varen amprar la garbell general del cos de números per a computar un logaritmo discret en una cos de 2809 elements.[8] El récort anterior en un cos finito de característica 2 de grau primer va ser anunciat per Antoine Joux i Reynald Lercier el 23 de setembre de 2005. Varen amprar la garbell general del cos de números per a computar un logaritmo discret en un cos de 2613 elements. El còmput va demorar 17 dies en quatre nodos de 16 processadors, a 1.3 GHz cada u, del súper-ordenador Teranova, basat en el Itanium 2.[9]

El récort actual (a data de 2012) per a un cos de característica 3 va ser anunciat per una associació entre Fujitsu, NICT i l'equip de l'Universitat de Kyushu, que varen computar un logaritmo discret en el cos de 36 · 97 elements, de 923 bits de tamany,[10] amprant una variant de la garbell general del cos de números, superant aixina el récort anterior en el cos de 36 · 71 elements de 676 bits [11] per un ampli marge.


Respecte a cossos de característica de tamany "moderat", computació notables realisades en 2005 inclouen aquella sobre el cos de 6553725 elements (401 bits), anunciada el 24 d'octubre de 2005, i la del cos de 37080130 elements (556 bits), anunciada el 9 de novembre de 2005.[12] El récort actual (a data de 2013) per a un cos finito de característica "moderada" va ser anunciada el 6 de giner de 2013. L'equip ampre una nova variant de la garbell general del cos de números per al cas de cosins mijos per a computar un logaritmo discret en un cos de 3334135357 elements (un cos finito de 1425 bits).[13][14] S'havia amprat la mateixa tècnica unes semanes abans per a computar un logaritmo discret en un cos de 3355377147 elements (un cos finito de 1175 bits).[15]

Referències

[editar | editar còdic]
  1. ↑ Antoine Joux, “Discrete logarithms in GF(p) – 130 digits,” June 18, 2005, http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0506&L=nmbrthry&T=0&P=20.
  2. ↑ Thorsten Kleinjung, “Discrete logarithms in GF(p) – 160 digits,” February 5, 2007, http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0702&L=NMBRTHRY&P=R45&D=0&I=-3&T=0.
  3. ↑ Antoine Joux, "Discrete logarithms in GF(26168) [=GF((2257)24)]", May 21, 2013, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1305&L=NMBRTHRY&F=&S=&P=3034.
  4. ↑ Antoine Joux. A new index calculus algorithm with complexity $L(1/4+o(1))$ in very small characteristic, 2013, http://eprint.iacr.org/2013/095
  5. ↑ Antoine Joux, "Discrete logarithms in GF(24080)", Mar 22, 2013, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1303&L=NMBRTHRY&F=&S=&P=13682.
  6. ↑ Faruk Gologlu et al., On the Function Field Sieve and the Impact of Higher Splitting Probabilities: Application to Discrete Logarithms in 𝔽21971, 2013, http://eprint.iacr.org/2013/074.
  7. ↑ Antoine Joux, "Discrete logarithms in GF(21778)", Feb. 11, 2013, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1302&L=NMBRTHRY&F=&S=&P=2317.
  8. ↑ The CARAMEL group: Razvan Barbulescu and Cyril Bouvier and Jérémie Detrey and Pierrick Gaudry and Hamza Jeljeli and Emmanuel Thomé and Marion Videau and Paul Zimmermann, “Discrete logarithm in GF(2809) with FFS”, April 6, 2013, http://eprint.iacr.org/2013/197.
  9. ↑ Antoine Joux, “Discrete logarithms in GF(2607) and GF(2613),” September 23, 2005, http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0509&L=NMBRTHRY&P=R1490&D=0&I=-3&T=0.
  10. ↑ Kyushu University, NICT and Fujitsu Laboratories Achieve World Record Cryptanalysis of Next-Generation Cryptography, 2012, http://www.nict.go.jp/en/press/2012/06/PDF-att/20120618en.pdf.
  11. ↑ Takuya Hayashi et al., Solving a 676-bit Discrete Logarithm Problem in GF(36n), 2010, http://eprint.iacr.org/2010/090.
  12. ↑ A. Durand, “New records in computations over large numbers,” The Security Newsletter, January 2005, «Copia archivada». Archivat des d'el original, el 10 de juliol de 2011. Consultat el 30 de decembre de 2010..
  13. ↑ Antoine Joux, “Discrete Logarithms in a 1425-bit Finite Field,” January 6, 2013, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1301&L=NMBRTHRY&F=&S=&P=2214.
  14. ↑ Faster index calculus for the medium prime case. Application to 1175-bit and 1425-bit finite fields, Eprint Archive, http://eprint.iacr.org/2012/720
  15. ↑ Antoine Joux, “Discrete Logarithms in a 1175-bit Finite Field,” December 24, 2012, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1212&L=NMBRTHRY&F=&S=&P=13902.


Referències

[editar | editar còdic]


Obtingut de «https://www.lenciclopedia.org/w/index.php?title=Récorts_en_logaritmos_discrets&oldid=853418»