Cálculo del número de puntos racionales de curvas elípticas sobre cuerpos finitos

Vista sencilla de ítem
dc.contributor.advisorZuñiga, Wilson
dc.contributor.authorEspinosa Chavarria, Desiderio
dc.contributor.authorGonzález Umaña, Hernando
dc.coverage.campusUNAB Campus Bucaramangaspa
dc.coverage.spatialBucaramanga (Santander, Colombia)spa
dc.coverage.temporal2002spa
dc.date.accessioned2024-07-29T16:16:34Z
dc.date.available2024-07-29T16:16:34Z
dc.date.issued2002
dc.degree.nameMagíster en en Ciencias Computacionalesspa
dc.description.abstractSe presentan los componentes teóricos que tienen que ver con el cálculo del número de puntos de una curva elíptica de característica prima diferente de 2, usando el conocido algoritmo de Schoof [23] y [24], Los métodos utilizados como parte de este algoritmo son: La algoritmia basada en el denominado símbolo de Legendre, el cual nos permite hacer un conteo casi manual de dichos puntos, pero que solo aplica a números pequeños (menores a 12 bits). El segundo método algorítmico, basado en el teorema de Hasse, hace uso fundamentalmente de tres cosas. Se hizo uso de una implementación hecha en C++ por Mike Scott en junio 1999, y liberada en la Internet con características de dominio público, siempre y cuando sean utilizadas con fines académicos y/o de investigación. A esta implementación se le realizaron las modificaciones necesarias, para que permitiera.spa
dc.description.abstractenglishThe theoretical components that have to do with the calculation of the number of points of an elliptic curve with a prime characteristic different from 2 are presented, using the well-known Schoof algorithm [23] and [24]. The methods used as part of this algorithm are : The algorithm based on the so-called Legendre symbol, which allows us to do an almost manual count of said points, but which only applies to small numbers (less than 12 bits). The second algorithmic method, based on Hasse's theorem, fundamentally makes use of three things. An implementation made in C++ by Mike Scott in June 1999 was used, and released on the Internet with public domain features, as long as they are used for academic and/or research purposes. The necessary modifications were made to this implementation to allow it.spa
dc.description.degreelevelMaestríaspa
dc.description.learningmodalityModalidad Presencialspa
dc.description.sponsorshipInstituto Tecnológico de Estudios Superiores de Monterrey (ITESM)spa
dc.description.tableofcontentsCapítulo 1. Introducción_____________________________________________________ 7 1.1 Marco teórico______________________________________________________9 1.2 Resumen ________________________________________________________ 10 1.2.1 Componente matemática_________________________________________ 10 1.2.2 Componente compiitacional_______________________________________11 1.3 Conclusiones_____________________________________________________ 13 1.4 Recomendaciones_________________________________________________ 14 Capítulo 2. Preliminares____________________________________________________ 15 2.1 Teoría de números________________________________________________ 15 2.1.1 Teorema fundamental de la aritmética______________________________ 15 2.1.2 Máximo común divisor (inccl) 15 2.1.3 Algoritmo de Euclídes__________________________________________ 15 2.2 Grupos__________________________________________________________ 16 2.2.1 Teorema de Lagrange___________________________________________ 16 2.2.2 Homomorfismo de grupos_______________________________________ 17 2.3 Campos Finitos___________________________________________________ 18 2.3.1 Congruencias_________________________________________________ 18 2.3.2 Campo______________________________________________________ 19 2.4 Residuos Cuadráticos______________________________________________ 19 2.4.1 Congruencia Lineal ____________________________________________ 19 2.4.2 Teorema chino del residuo_______________________________________ 19 2.4.3 Teorema de Wilson_____________________________________________ 20 2.4.4 Símbolo de Legcndre___________________________________________ 20 2.4.5 Ley de Reciprocidad Cuadrática___________________________________21 2.4.6 El Símbolo de Jacobi.__________________________________________ 21 Capítulo 3. Planos proyectivos y afines_______________________________________23 3.1 Espacios vectoriales________________________________________________23 3.2 Coordenadas Proyectivas___________________________________________ 25 Capítulo 4. Criptografía de curvas elípticas______________________________________30 4.1 Introducción a las curvas elípticas__________________________________ ____ 30 Capítulo 5. Algoritmo de Schoof_______________________________________________40 5.1 El inorfismo de Frobenius ___________________________________ _______40 5.2 Los polinomios división____________________________________________ 41 5.3 El Teorema de Hasse_______________________________________________42 5.4 Valores propios del inorfismo de Frobenius____________________________43 5.5 El algoritmo de Schoof_____________________________________________ 44 Capítulo 6. Documentación algoritmo de Sclioof_________________________________ 51 6.1 Algoritmo de Sclioof_______________________________________________ 51 6.2 Algoritmo de Legendre_____________________________________________51 6.3 Programa de conteo de puntos_____________________________________ 54 Capitulo 7. Interfase gráfica de usuario_____________________________________ 99 7.1 Guía de Instalación________________________________________________ 99 7.1.1 Compilación de programas_______________________________________ 99 7.1.2 Ejecución del sistema___________________________________________ 100 7.2 Configuración del sistema__________________________________________100 7.3 Guía del usuario _ _______________________________________________ 101 7.3.1 Procesos______________________________________________________ 103 7.3.1.1 Schoof______________________________________________________ 104 7.3.1.2 SEA_______________________________________________________ 109 7.3.1.3 Salir________________________________________________________ 111 7.3.2 Consultas_____________________________________________________ 112 7.3.2.1 Ver Sclioof__________________________________________________ 114 7.3.2.2 Ver SEA ____________________________________________________ 115 7.3.2.3 Parámetros Schoof____________________________________________ 116 7.3.2.4 Parámetros SEA___________________________________________ ___ 117 7.3.2.5 Log Schoof__________________________________________________ 118 7.3.2.Ó Log SEA______________________________________________________ 119 7.3.3 Opciones___________________________________________________ __ 120 7.3.3.1 Acerca de______________ _ ____________________________________ 121 7.3.3.2 Reiniciar BD___________________ ______________________________ 122 7.3.4 Salida________________________________________________________ 123 Capítulo 8. Documentación técnica__________ ________________________________ 125 8.1 Interface gráfica___________________________________________________ _ 125 8.1.1 Archivos de interface __________________________________________ 125 8.1.2 Estructuras de clases y métodos__________________________________ 129 8.1.3 Diagrama de Clases (Figura 36.)_________________________________ 152 8.1.4 Modelado arquitectónico - Despliegue (Figura 37.) 153 8.1.5 Modelado de comportamiento - Diagrama de actividad Schoof (Figura 38.) 8.2 Cálculo del conteo_________________________________________________156 8.2.1 Archivos de cabecera____________________________________________156 8.2.2 Funciones internas_____________________________________________ 158 8.2.3 Funciones externas___________________________________________ 161 Capítulo 9. Presentación de resultados_____________________________________ 166 9.1 Cálculos y resultados______________________________________________166 9.1.1 Plataforma computacional______________________________________ 166 9.1.2 Módulos primo pequeños_______________________________________ 166 9.1.3 Módulos primo grandes________________________________________ 167 9.2 Observaciones___________________________________________________ 175 9.3 Conclusiones____________________________________________________ 177 9.4 Recomendaciones_________________________________________________178 Bibliografía_______________________________________________________________ 180spa
dc.identifier.reponamereponame:Repositorio Institucional UNABspa
dc.identifier.repourlrepourl:https://repository.unab.edu.cospa
dc.identifier.urihttp://hdl.handle.net/20.500.12749/25771
dc.publisher.facultyFacultad Ingenieríaspa
dc.publisher.grantorUniversidad Autónoma de Bucaramanga UNABspa
dc.publisher.programMaestría en Ciencias Computacionalesspa
dc.relation.referencesA.J. Menezes, P.C. van Oorschot, S.A. Vanstone, Handbook of Applied Cryptography, CRC press, Boca Ratón, Florida, 1996.spa
dc.relation.referencesBlake, I. F., Seroussi, G., Smart, N.P., Elliptic Curves in Cryptography, volumen 265 ofLondon Mathematical Socicty Lecture Notes Series. Cambridge Univcrsity Press, 1999.spa
dc.relation.referencesCouveignes, J.M., Dccaghe, L. and Morain F. Isogeny cicles and the Schoof-Elkies Atkin algorithm. L’École Polytechnique, Laboratoire D’Informatique, CNRS, Palaiseau, August, 1996spa
dc.relation.referencesCouveignes, J.M. and Morain F. Schoof’s algorithm and Isogeny cicles, Springer Vcrlag, LNCS 877, 1994.spa
dc.relation.referencesCurrent Public-Key Cryptography Systems, Certicom, Misissauga, Ontario, 1997.spa
dc.relation.referencesDeytcl, H.M. and Dcytel, P.J., How to program C++. Prcntice Hall, Third editions, 1995.spa
dc.relation.referencesDeytel, H.M. and Deytcl, P.J., Java how to program. Prenticc Hall, Third editions, 1995spa
dc.relation.referencesGarms, J. and Somerficld, D., Professional Java Security. Wrox Press Ltda. 2001spa
dc.relation.referencesGoldwasser, S.; Bellare, M., Lecture Notes on Cryptography, MIT, Cambridge, 1997.spa
dc.relation.referencesHerstein, I.N., Topics in Algebra. University of Chicago, 1975spa
dc.relation.referencesKoblitz N., A Course in number Theory and Cryptography, Springer-Verlag, New York, 1994spa
dc.relation.referencesLercier, R. and Morain, F., Counting points on elliptic curves over F? using Coveignes’s algorithm, 1995spa
dc.relation.referencesLercier, R. and Morain F., Counting the number of points on elliptic curves over fmite fields: strategies and Performance. 79 - 94, EUROCRYPT 95, 1995spa
dc.relation.referencesLercier, R., Finding Good Random Elliptic Curves for Cryptosystems Defined over F2 ",Laillé, 1998.spa
dc.relation.referencesLercier, R., Algorithmique des courbes elliptiques dans les corps finís. Thése, L’Ecole Polytechnique, Laboratoire D’Infonnatique, CNRS, Paris, June, 1997.spa
dc.relation.referencesMenezes, A. and Jurisic, A., Elliptic Curves and Cryptography.spa
dc.relation.referencesMenezes, A., Elliptic Curve Public Key Cryptosystem, Kluwer Acadcmic Publishers, Dordrecht, 1993.spa
dc.relation.referencesMenezes, A. Vanstone., Zucherato, R., Counting points on elliptic curves over F¡', 1992spa
dc.relation.referencesM.I.R.A.C.L. Uscrs Manual, Shanius Software Ltd. January 2002spa
dc.relation.referencesMorain, F. Calcul du nombre de points sur une courbe elliptique dans un corps finí: aspects algorithmiques. J.Théorie des nombres de Bourdeaux, 7, 255-282,1995.spa
dc.relation.referencesPalmer, G., Java Progranuner ’s Reference. Wrox Press Ltda. 2001spa
dc.relation.referencesSaeki, M., Elliptic curve Cryptosystems, School of Computer Science. McGill univcrsity, Montreal, February, 1997.spa
dc.relation.referencesSchoof, R., Counting points on elliptic curves over finito fields, 1994.spa
dc.relation.referencesSchoof, R., Elliptic curves over finóte fields and (he computation of square roots modp. Mathematics Computation, 44(170): 483-494, April 1985.spa
dc.relation.referencesSchoof, R., Counting points on Elliptic curves overfinite fields. journal de Théorie des Nombres de Bourdeaux 7: 219-254, 1995spa
dc.relation.referencesSilverman, J., The arithmetic of elliptic curves, Springer-Verlag, New York, 1994.spa
dc.relation.referencesVon York, E., Elliptic Curves Over Finite Fields, George Masón Univcrsity, May 7, 1992.spa
dc.rights.accessrightsinfo:eu-repo/semantics/openAccessspa
dc.rights.creativecommonsAtribución-NoComercial-SinDerivadas 2.5 Colombia*
dc.rights.localAbierto (Texto Completo)spa
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/2.5/co/*
dc.subject.keywordsComputer sciencesspa
dc.subject.keywordsSystems engineerspa
dc.subject.keywordsMathspa
dc.subject.keywordsComputingspa
dc.subject.keywordsTheoremsspa
dc.subject.keywordsPolynomialsspa
dc.subject.keywordsAlgorithmsspa
dc.subject.keywordsRational points (Geometry)spa
dc.subject.keywordsArithmetic algebraic geometryspa
dc.subject.keywordsCurves ellipticspa
dc.subject.keywordsAlgebraic curvesspa
dc.subject.lembCiencias computacionalesspa
dc.subject.lembIngeniería de sistemasspa
dc.subject.lembPuntos racionales (Geometría)spa
dc.subject.lembGeometría algebraica aritméticaspa
dc.subject.lembCurvas elípticasspa
dc.subject.lembCurvas algebraicasspa
dc.subject.proposalMatemáticasspa
dc.subject.proposalComputaciónspa
dc.subject.proposalTeoremasspa
dc.subject.proposalPolinomiosspa
dc.subject.proposalAlgoritmosspa
dc.titleCálculo del número de puntos racionales de curvas elípticas sobre cuerpos finitosspa
dc.title.translatedCalculation of the number of rational points of elliptic curves on finite bodiesspa
dc.type.coarhttp://purl.org/coar/resource_type/c_bdcc
dc.type.coarversionhttp://purl.org/coar/version/c_ab4af688f83e57aaspa
dc.type.driverinfo:eu-repo/semantics/masterThesis
dc.type.hasversioninfo:eu-repo/semantics/acceptedVersion
dc.type.localTesisspa
dc.type.redcolhttp://purl.org/redcol/resource_type/TM

Archivos

Bloque original

Mostrando 1 - 1 de 1
Miniatura
Nombre:
2002_Tesis_Desiderio_Espinosa.pdf
Tamaño:
38.49 MB
Formato:
Adobe Portable Document Format
Descripción:
Tesis
Descargar

Bloque de licencias

Mostrando 1 - 1 de 1
Miniatura
Nombre:
license.txt
Tamaño:
829 B
Formato:
Item-specific license agreed upon to submission
Descripción:
Descargar

Colecciones

Maestría en Ciencias Computacionales