Soluciones no Triviales al Problema de Congruencia de Criba Cúbica: x 3 y 2 z mod p

Subhamoy Maitra, Y. V. Subba Rao, Pantelimon Stanica, Sugata Gangopadhyay

Resumen


EN ESTE ARTÍICULO 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 < P 1 2 Y X3 6= 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 LOG P. 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.

Palabras clave


Congruencia de criba cúbica; problema del logaritmo discreto; números primos

Texto completo:

PDF


Contacto:
Oscar Zavala