| Revista: | Computación y sistemas |
| Base de datos: | PERIÓDICA |
| Número de sistema: | 000360121 |
| ISSN: | 1405-5546 |
| Autores: | Maitra, Subhamoy1 Subba Rao, Y.V2 Stanica, Pantelimon3 Gangopadhyay, Sugata4 |
| Instituciones: | 1Indian Statistical Institute, Applied Statistics Unit, Calcuta, Bengala Occidental. India 2University of Hyderabad, School of Mathematics, and Computing Informatics Sciences, Gachbowli, Hyderabad. India 3Naval Postgraduate School, Graduate School of Engineering and Applied Sciences, Monterey, California. Estados Unidos de América 4Indian Institute of Technology, Mathematics Department, Roorkee, Uttarakhand. India |
| Año: | 2009 |
| Periodo: | Ene-Mar |
| Volumen: | 12 |
| Número: | 3 |
| Paginación: | 253-266 |
| País: | México |
| Idioma: | Inglés |
| Tipo de documento: | Artículo |
| Enfoque: | Experimental, aplicado |
| Resumen en español | En este artículo se discute el problema de cómo encontrar soluciones no triviales al problema de congruencia de la criba cúbica, esto es, soluciones a la ecuación: x3 = y2z (mod p), donde x,y, z < y x3 ≠ y2z. Las soluciones a este problema resultan útiles para resolver el problema del logaritmo discreto o el de factorización entera cuando se utiliza el método de index calculus. Además del evidente interés criptográfico, este problema tiene también relevancia desde el punto de vista de la teoría elemental de números. Aunque no logramos resolver totalmente el problema, sí pudimos identificar ciertas subclases de primos donde el problema puede ser resuelto en tiempo polinomial en logp. Asimismo, extendimos la idea de cribado de Reyneri e identificamos algunas clases en donde el problema puede ser resuelto en tiempo constante. Los diseñadores de cripto–esquemas deben evitar utilizar cualquiera de los primos contenidos en los casos aquí detectados |
| Resumen en inglés | In this paper we discuss the problem of finding nontrivial solutions to the Cubic Sieve Congruence problem, that is, solutions of x3 = y2z (mod p), where x,y,z < and x3 ≠ y2z. The solutions to this problem are useful in solving the Discrete Log Problem or factorization by index calculus method. Apart from the cryptographic interest, this problem is motivating by itself from a number theoretic point of view. Though we could not solve the problem completely, we could identify certain sub classes of primes where the problem can be solved in time polynomial in log p. Further we could extend the idea of Reyneri's sieve and identify some cases in it where the problem can even be solved in constant time. Designers of cryptosystems should avoid all primes contained in our detected cases |
| Disciplinas: | Ciencias de la computación, Matemáticas |
| Palabras clave: | Matemáticas aplicadas, Criptografía, Problema del logaritmo discreto, Números primos, Congruencia de criba cúbica |
| Keyword: | Computer science, Mathematics, Applied mathematics, Cryptography, Discrete log problem, Prime numbers, Cubic sieve congruence |
| Texto completo: | Texto completo (Ver HTML) |
