Análisis de distribución de primos con representaciones binarias signadas cortas
Jhonatan Perera Angulo
|
Texto completo de la Tesis 
Video del evento 
Resumen
La generación de números primos es un tema de mucha importancia para la mayoría de los esquemas de llave pública, y en ocasiones no recibe la atención que merece. Estudiamos la generación de números primos grandes con pocos dígitos signados en su representación binaria, con el propósito de hacer efi cientes las operaciones aritméticas y fortalecer la robustez de protocolos criptográficos. Algunas de las maneras en que se puede medir la calidad de los algoritmos generadores de números primos tienen que ver con la velocidad, propiedades estadísticas, el número de bits aleatorios que se consume para producir un número primo, etc. En este trabajo nos centramos principalmente en la velocidad en términos de la complejidad computacional, aunque desarrollamos tambien resultados relativos a propiedades estadísticas. Nosotros abordamos el problema de diseñar e implementar un algoritmo efi ciente que genere números primos dados dos parámetros: n, la cantidad de bits del número que se generara, y k, la cantidad de bits signados encendidos que dicho número tendrá. Dados los parametros n y k se definen de manera formal el conjunto de expresiones así como el conjunto de enteros a los que pertenecen estos números primos en que estamos interesados. Desde el 2001 han sido definidos y analizados dichos conjuntos, y se ha utilizado el Teorema de los Números Primos para estimar algunas de sus propiedades estadísticas. Los trabajos más recientes que abordan este tema, proponen algunas fórmulas para calcular las cardinalidades de los conjuntos de expresiones definidas por los parametros n y k, sin embargo, los resultados presentados fueron obtenidos mediante conjeturas e interpolación de datos y no se tienen demostraciones formales de dichas conjeturas. En este trabajo diseñamos e implementamos un algoritmo generador de números primos que, bajo ciertas hipótesis que más adelante estableceremos, es de orden O(n2). Además desarrollamos la teoría necesaria para generalizar las fórmulas para calcular las cardinalidades de los conjuntos de expresiones que mencionamos, y aportamos un algoritmo al estado del conocimiento para calcular estas cardinalidades. También aportamos una aproximación teórica y una aproximación experimental al estado del conocimiento sobre la cantidad de números primos que están representados por alguna de las expresiones de finidas por los parámetros n y k.
Abstract
The prime numbers generation is very important for most public key schemes, and some times it does not receive the attention that it deserves. We deal with the problem of generating big prime numbers involving few non-zero digits in their binary signed expression, aiming to maintain efficient calculation and cryptographic protocols robustness. Some ways to measure the accuracy of the prime numbers generation algorithms has to do with the speed, statistics properties, number of random bits that consume to produce a prime number, etc. In this work we focus mainly in the speed in terms of the computational complexity, though we too develop results relative to statistics properties. We tackle the problem of design and implement an efficient algorithm that generate prime numbers given two parameters: n, the amount of bits of the number that will be generated, and k, the amount of set signed bits that this number will have. Given the parameters n and k we de fine in a formal way the set of expressions as well as the set of integers to which the prime numbers we are interested in belong. Since 2001 have been de fined and analyzed those sets, and the Prime Number Theorem has been used to estimate some of their statistics properties. The most recent works that tackle this topic, propose some formulas to calculate the cardinalities of the sets of expressions defi ned by the parameters n and k, however, the results presented were obtained by conjectures and data interpolation and there are no formal proofs of these conjectures. In this work we design and implement a prime number generator algorithm that, under certain assumptions that we stablish later, is of order O(n2). In addition we develop the necessary theory to generalize the formulas to calculate the cardinalities of the sets of expressions that we mentioned, and we contribute with an algorithm to the state of the art to calculate these cardinalities. We also provide a theoretical approximation and an experimental approximation to the state of the art about the amount of prime numbers that are represented by some of the expressions de fined by the parameters n and k.
