Heurísticas de búsqueda y algoritmos constructivos para enteros maximamente idempotentes
Autores: Fagin, Barry
Idioma: Inglés
Editor: MDPI
Año: 2021
Acceso abierto
Artículo científico
2021
Heurísticas de búsqueda y algoritmos constructivos para enteros maximamente idempotentes
Categoría
Gestión y administración
Subcategoría
Gestión de la tecnología y la inovación
Palabras clave
Enteros libres de cuadrados
Claves RSA
Función totiente de Carmichael
Enteros idempotentes
Semiprimos
Enteros maximamente idempotentes
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 1
Citaciones: Sin citaciones
El trabajo previo estableció el conjunto de enteros libres de cuadrados n con al menos una factorización n=p¯q¯ para la cual p¯ y q¯ son claves RSA válidas, ya sean primos o compuestos. Estos enteros son exactamente aquellos con la propiedad (n)(p¯-1)(q¯-1), donde es la función totiente de Carmichael. Nos referimos a estos enteros como idempotentes, porque aZn,ak(p¯-1)(q¯-1)+1na para cualquier entero positivo k. Este conjunto se conocía inicialmente por contener solo los semiprimos, y luego se amplió para incluir algunos de los números de Carmichael. Un trabajo reciente del autor proporcionó la formulación explícita para el conjunto, mostrando que incluye números que no son ni semiprimos ni números de Carmichael. Los números en esta última categoría no habían sido analizados previamente en la literatura. Si bien solo los semiprimos tienen propiedades criptográficas útiles, los enteros idempotentes merecen ser estudiados por derecho propio, ya que se encuentran en la frontera de problemas difíciles en teoría de números y ciencias de la computación. Algunos enteros idempotentes, los enteros maximamente idempotentes, tienen la propiedad de que todas sus factorizaciones son idempotentes. Discutimos su estructura aquí, heurísticas para ayudar a encontrarlos y algoritmos de teoría de grafos que se pueden utilizar para construir ejemplos de tamaño arbitrario.
Descripción
El trabajo previo estableció el conjunto de enteros libres de cuadrados n con al menos una factorización n=p¯q¯ para la cual p¯ y q¯ son claves RSA válidas, ya sean primos o compuestos. Estos enteros son exactamente aquellos con la propiedad (n)(p¯-1)(q¯-1), donde es la función totiente de Carmichael. Nos referimos a estos enteros como idempotentes, porque aZn,ak(p¯-1)(q¯-1)+1na para cualquier entero positivo k. Este conjunto se conocía inicialmente por contener solo los semiprimos, y luego se amplió para incluir algunos de los números de Carmichael. Un trabajo reciente del autor proporcionó la formulación explícita para el conjunto, mostrando que incluye números que no son ni semiprimos ni números de Carmichael. Los números en esta última categoría no habían sido analizados previamente en la literatura. Si bien solo los semiprimos tienen propiedades criptográficas útiles, los enteros idempotentes merecen ser estudiados por derecho propio, ya que se encuentran en la frontera de problemas difíciles en teoría de números y ciencias de la computación. Algunos enteros idempotentes, los enteros maximamente idempotentes, tienen la propiedad de que todas sus factorizaciones son idempotentes. Discutimos su estructura aquí, heurísticas para ayudar a encontrarlos y algoritmos de teoría de grafos que se pueden utilizar para construir ejemplos de tamaño arbitrario.