2026-04-27T12:51:08Zhttps://uvadoc.uva.es/oai/requestoai:uvadoc.uva.es:10324/581622023-01-12T20:03:37Zcom_10324_38col_10324_852
UVaDOC
advisor
Delgado de la Mata, Félix
author
González Pastor, Samuel
editor
Universidad de Valladolid. Facultad de Ciencias
2023-01-12T16:32:51Z
2023-01-12T16:32:51Z
2022
https://uvadoc.uva.es/handle/10324/58162
El problema de saber si un número es o no primo de manera eficiente fue durante bastantetiempo un problema abierto y clave desde varios puntos de vista, tanto de teoría de la complejidadcomo de la algoritmia matemática. El trabajo consistirá en revisar el trabajo de Agrawal, Kayal ySaxena (2002) desarrollando un algoritmo con complejidad polinómica que resolvía de formadefinitiva el conocido problema Primes is in P?. Un detalle relevante es que, desde el punto de vistapráctico, el algoritmo no es especialmente útil, ya que hay algoritmos probabilistas muy rápidos ypotentes que cubren las necesidades de aplicación.
spa
Attribution-NonCommercial-NoDerivatives 4.0 Internacional
El problema de primalidad está en P
info:eu-repo/semantics/bachelorThesis
77u/QUNVRVJETyBERSAgRURJQ0nDk04gRUxFQ1RSw5NOSUNBIFkgRElGVVNJw5NOIEVOIElOVEVSTkVUIAoKRWwgb2JqZXRpdm8gZnVuZGFtZW50YWwgZGVsIFJlcG9zaXRvcmlvIEluc3RpdHVjaW9uYWwgIGVzICBsYSBkaXZ1bGdhY2nDs24gZGUgbGEgUFJPRFVDQ0nDk04gQ0lFTlTDjUZJQ0EgCmRlIGxhIFVuaXZlcnNpZGFkICBkZSBWYWxsYWRvbGlkLCBwYXJhIGxvIGN1YWwgbGEgVW5pdmVyc2lkYWQgcG9uZSBsb3MgbWVkaW9zIHTDqWNuaWNvcyBuZWNlc2FyaW9zIG9mcmVjaWVuZG8gIHVuYSAgCmJhc2UgIGRlICBkYXRvcyAgYSB0ZXh0byBjb21wbGV0byB5IGVuIGZvcm1hdG8gZWxlY3Ryw7NuaWNvLCBhIHRyYXbDqXMgZGUgSW50ZXJuZXQsIGZhY2lsaXRhbmRvIGFzw60gCmxhIHZpc2liaWxpZGFkIHkgYWNjZXNvIGEgbGEgaW5mb3JtYWNpw7NuIGNpZW50w61maWNhIHkgdMOpY25pY2EuCgpQYXJhICBxdWUgIGVsIFJlcG9zaXRvcmlvIGRlIGxhIFVuaXZlcnNpZGFkIGRlIFZhbGxhZG9saWQgcHVlZGEgcmVwcm9kdWNpciAgeSAgY29tdW5pY2FyIHDDumJsaWNhbWVudGUgc3UgCmRvY3VtZW50byBlcyBuZWNlc2FyaW8gbGEgYWNlcHRhY2nDs24gZGUgbG9zIHNpZ3VpZW50ZXMgdMOpcm1pbm9zLgoKQWNlcHRhbmRvIGVzdGUgQWN1ZXJkbywgdXN0ZWQgIE1BTklGSUVTVEE6CgpQUklNRVJPOiBTZXIgIEVsIGF1dG9yIGRlIGVzdGUgVHJhYmFqbyB5IHRpdHVsYXIgZGUgbG9zIGRlcmVjaG9zIGRlICBwcm9waWVkYWQgIGludGVsZWN0dWFsLiAgTWFuaWZlc3RhbmRvICBxdWUgc29icmUgCmxhIG1pc21hIG5vIHRpZW5lIGNvbnRyYcOtZG9zIG5pIGNvbnRyYWVyw6EgY29tcHJvbWlzb3MgbyBncmF2w6FtZW5lcyBkZSBuaW5ndW5hIGVzcGVjaWUgIHF1ZSBhdGVudGVuIApjb250cmEgbG9zIGRlcmVjaG9zIHF1ZSBhIGxhIFVuaXZlcnNpZGFkIGxlIGNvcnJlc3BvbmRhbi4KU0VHVU5ETzogUXVlIGVsIGRvY3VtZW50byBlcyB1biB0cmFiYWpvIG9yaWdpbmFsIHN1eW8geSBxdWUgdGllbmUgZGVyZWNobyAgcGFyYSAgb3RvcmdhciAgIGxvcyBkZXJlY2hvcyBjb250ZW5pZG9zIAplbiBlc3RlIGFjdWVyZG8uIApEZWNsYXJhICBxdWUgIHN1IGRvY3VtZW50byBubyBpbmZyaW5nZSwgZW4gdGFudG8gZW4gY3VhbnRvIGxlIHNlYSBwb3NpYmxlICBzYWJlciwgIGxvcyAgZGVyZWNob3MgZGUgYXV0b3IgZGUgbmluZ3VuYSAKb3RyYSBwZXJzb25hIG8gZW50aWRhZC4KVEVSQ0VSTzogU2kgZWwgZG9jdW1lbnRvIGNvbnRpZW5lIG1hdGVyaWFsZXMgZGUgbG9zIGN1YWxlcyBubyB0aWVuZSBsb3MgIGRlcmVjaG8gIGRlICBhdXRvciwgIGRlY2xhcmEgIHF1ZSAgaGEgIG9idGVuaWRvCmVsIHBlcm1pc28gc2luIHJlc3RyaWNjacOzbiBkZWwgcHJvcGlldGFyaW8gZGUgbG9zIGRlcmVjaG8gZGUgYXV0b3IgcGFyYSBvdG9yZ2FyIGEgbGEgIFVuaXZlcnNpZGFkICBkZSAgVmFsbGFkb2xpZCwgIApsb3MgIGRlcmVjaG8gIHJlcXVlcmlkb3MgcG9yIGVzdGUgQWN1ZXJkbyAgeSAgcXVlICBlc2UgbWF0ZXJpYWwgIGN1eW9zICBkZXJlY2hvcyBzb24gZGUgdGVyY2Vyb3MgZXN0w6EgY2xhcmFtZW50ZSAgCmlkZW50aWZpY2FkbyB5ICByZWNvbm9jaWRvICBlbiBlbCB0ZXh0byBvIGNvbnRlbmlkbyBkZWwgZG9jdW1lbnRvIGVudHJlZ2Fkby4KQ1VBUlRPOiBTaSBlbCBkb2N1bWVudG8gc2UgYmFzYSBlbiB1bmEgb2JyYSBxdWUgaGEgc2lkbyBwYXRyb2NpbmFkYQpvIGFwb3lhZGEgcG9yIHVuYSBhZ2VuY2lhIHUgb3JnYW5pemFjacOzbiBkaWZlcmVudGUgZGUgbGEgVW5pdmVyc2lkYWQgZGUgVmFsbGFkb2xpZCBzZSBwcmVzdXBvbmUgcXVlIHNlIGhhIGN1bXBsaWRvIApjb24gY3VhbHF1aWVyIGRlcmVjaG8gZGUgcmV2aXNpw7puIHUgb3RyYXMgb2JsaWdhY2lvbmVzIHJlcXVlcmlkYXMgcG9yIGVzdGUgQWN1ZXJkby4KUVVJTlRPOiBSZWNvbm9jZXIgcXVlIGFjZXB0YW5kbyBlc3RlIEFjdWVyZG8sIGVmZWN0w7phIHVuYSAgY2VzacOzbiAKbm8gZXhjbHVzaXZhIGRlIGVzdGUgVHJhYmFqbyBhIGxhIFVuaXZlcnNpZGFkIGRlIFZhbGxhZG9saWQsICBjb24gY2Fyw6FjdGVyICBncmF0dWl0byB5ICBjb24gZmluZXMgZXhjbHVzaXZhbWVudGUgZGUgCmludmVzdGlnYWNpw7NuIHkgZG9jZW5jaWEsICBhc8OtICBjb21vICBsYSAgY2VzacOzbiBubyBleGNsdXNpdmEgZGUgIGxvcyBkZXJlY2hvcyBkZSByZXByb2R1Y2Npw7NuLCAKY29tdW5pY2FjacOzbiAgeSAgZGlzdHJpYnVjacOzbiAgZGUgIHN1ICB0cmFiYWpvIG11bmRpYWxtZW50ZSwgZW4gZm9ybWF0byBlbGVjdHLDs25pY28gcGFyYSBzdSBkaWZ1c2nDs24gCnDDumJsaWNhLiAKTGEgdGl0dWxhcmlkYWQgZGUgbG9zIGRlcmVjaG9zIGRlIGV4cGxvdGFjacOzbiBkZSBsYSBwcm9waWVkYWQgaW50ZWxlY3R1YWwgc29icmUgbGEgb2JyYSBwZXJ0ZW5lY2UgeSBzZWd1aXLDoSAKcGVydGVuZWNpZW5kbyBhbCBBdXRvci4KCkxhIFVuaXZlcnNpZGFkIGRlIFZhbGxhZG9saWQsIGVuIHZpcnR1ZCBkZWwgcHJlc2VudGUgQWN1ZXJkbyAKREVDTEFSQSBRdWU6CgpQUklNRVJPOiBBbGJlcmdhcsOhIGVuIGVsIHJlcG9zaXRvcmlvIGluc3RpdHVjaW9uYWwgZGUgbGEgVW5pdmVyc2lkYWQgZGUgIFZhbGxhZG9saWQgIGVzdGUgVHJhYmFqby4gU2luIHBlcmp1aWNpbyBkZSBxdWUgCmVuIHVuIGZ1dHVybywgY29uIGVsIG9iamV0aXZvIGRlIGNvbnNlZ3VpciB1bmEgbWF5b3IgZGlmdXNpw7NuLCBzZWEgcmVjb2dpZG8gdGFtYmnDqW4gZW4gb3Ryb3MgcmVwb3NpdG9yaW9zIHF1ZSAKcHVlZGFuIGNvbnN0aXR1aXJzZSBhIG5pdmVsIHJlZ2lvbmFsLG5hY2lvbmFsIG8gaW50ZXJuYWNpb25hbC4gClNFR1VORE86IExhIFVuaXZlcnNpZGFkIGRlIFZhbGxhZG9saWQgcG9uZHLDoSBhIGRpc3Bvc2ljacOzbiBkZSBzdXMgdXN1YXJpb3MgbGEgIFBST0RVQ0NJw5NOIENJRU5Uw41GSUNBIApwYXJhIGVsIHVzbyBwcml2YWRvIHkgZmluZXMgZGUgaW52ZXN0aWdhY2nDs24gIHkgIGRvY2VuY2lhICBhdW5xdWUgIG5vIGdhcmFudGl6YSBuaSBhc3VtZSBuaW5ndW5hIHJlc3BvbnNhYmlsaWRhZCAgcG9yICAKbGFzICBmb3JtYXMgIGVuICBxdWUgIGxvcyAgdXN1YXJpb3MgIGhhZ2FuIHBvc3Rlcmlvcm1lbnRlIHVzbyBkZSBzdSBUcmFiYWpvLgpURVJDRVJPOiBMYSBVbml2ZXJzaWRhZCBubyB0aWVuZSBsYSBpbnRlbmNpw7NuIGRlIGNlbnN1cmFyIG5pIHJldmlzYXIgZWwgVHJhYmFqbyBkZWwgYXV0b3IgeSBlbiBjb25zZWN1ZW5jaWEgc2Vyw6EgCmVsIGF1dG9yICByZXNwb25zYWJsZSBkZWwgY29udGVuaWRvIGRlIHN1IG9icmEuCkNVQVJUTzogRW4gZWwgcmVwb3NpdG9yaW8gaW5zdGl0dWNpb25hbCBkZSBsYSBVbml2ZXJzaWRhZCBkZSBWYWxsYWRvbGlkICBzZSBoYXLDoSBtZW5jacOzbiBleHByZXNhIGEgbG9zIHVzb3MgCmF1dG9yaXphZG9zIGRlIGxhIG9icmEsIGJham8gbGEgbGljZW5jaWEgQ3JlYXRpdmUgQ29tbW9ucyBzZWxlY2Npb25hZGFzIHBvciBlbCBhdXRvciBkZWwgVHJhYmFqby4KCkVsIHByZXNlbnRlIEFjdWVyZG8gZW50cmFyw6EgZW4gdmlnb3IgZW4gZXN0ZSBtb21lbnRvIHkgdGVuZHLDoSB1bmEgZHVyYWNpw7NuIGluZGVmaW5pZGEuIFNpbiBwZXJqdWljaW8gZGUgCmVzdGEgZHVyYWNpw7NuIGluZGVmaW5pZGEgaW5pY2lhbG1lbnRlIHBhY3RhZGEsIHNlIHBvZHLDoSBwb25lciBmaW4gYWwgcHJlc2VudGUgQWN1ZXJkbzogcG9yIHZvbHVudGFkIGRlIGxhcyBwYXJ0ZXMsIApwb3IgaW5jdW1wbGltaWVudG8gZGUgY3VhbHF1aWVyYSBkZSBsYXMgb2JsaWdhY2lvbmVzIGRlcml2YWRhcyBkZWwgQWN1ZXJkbywgcG9yIHZvbHVudGFkIGV4cHJlc2EgZGVsIEF1dG9yCkVuICBwcnVlYmEgZGUgY29uZm9ybWlkYWQsIGxhcyBwYXJ0ZXMgYWNlcHRhbiBlbCBwcmVzZW50ZSBBY3VlcmRvCgoKCgo=
URL
https://uvadoc.uva.es/bitstream/10324/58162/1/TFG-G5985.pdf
File
MD5
c772a8e799c9ecc5b00bb12be0d7d2be
389599
application/pdf
TFG-G5985.pdf