Mike Hamburg diseñó una curva elíptica que él llama Ed448-Goldilocks . El prefijo Ed se refiere al hecho de que es una curva de Edwards . El número 448 se refiere al hecho de que la curva se encuentra sobre un campo primario donde la prima p tiene un tamaño de 448 bits. Pero ¿por qué Goldilocks ?
Golden primes and Goldilocks
El primo en este caso es
p = 2 448 ] – 1,
que tiene la misma forma que los números primos NIST . Hamburg dice en su artículo
Yo lo llamo el primo de "Ricitos de oro" porque su forma define la proporción de oro φ = 2 224 .
Esa frase me desconcertó. ¿Qué tiene esto que ver con la proporción de oro? No creo que exista una conexión directa con la proporción áurea (1 + √5) / 2, a menos que me esté faltando algo. Llama a p una primo de la proporción de oro por lo que entiendo que significa una prima de la forma
q 2 n
– q n – 1
donde la analogía con la proporción áurea es que la proporción del primer término con respecto al segundo es la misma que la relación del segundo con el tercero. En ese caso, creo que "primo geométrico" podría haber sido un nombre mejor, porque los términos están en una progresión geométrica.
Otra justificación para el término "Ricitos de oro" podría ser la alusión al cuento de hadas: el término medio 2 224 es "justo". Hamburg dice
Debido a que 224 = 32 * 7 = 28 * 8 = 56 * 4, este primer soporta aritmética rápida en la raíz 2 28 o 2 32 (en máquinas de 32 bits) o 2 56 (en máquinas de 64 bits). Con 16 extremidades de 28 bits, funciona bien en unidades vectoriales como NEON. Además, las implementaciones de radix-2 64 son posibles con mayor eficiencia que la mayoría de los números primos del NIST.
Multiplicación de Karatsuba
El título de este post es "Ricitos de oro y las tres multiplicaciones". vienen tres multiplicaciones? Es una alusión a un algoritmo para la multiplicación de precisión múltiple que le permite superar con tres multiplicaciones donde el enfoque más directo requeriría cuatro. El algoritmo se llama multiplicación de Karatsuba [1].
Hamburgo dice "La principal ventaja de un primo de la proporción áurea es la rápida multiplicación de Karatsuba" y eso si establecemos φ = 2 224 entonces
Nota que la primera línea en el lado derecho implica cuatro multiplicaciones, pero la línea inferior incluye tres. Dado que las variables representan números de 224 bits, eliminar una multiplicación a costa de una suma y una resta adicionales es un ahorro neto [2].
La línea más importante del cálculo anterior y la única que no es rutinaria , es el segundo. Ahí es donde entra la forma especial de p . Cuando se eliminan los términos comunes de ambos lados, el cálculo se reduce a mostrar que
lo que obviamente es cierto ya que p = φ² – φ – 1.
Curva Ed448-Goldilocks
Las curvas de Edwards solo tienen un parámetro libre d (además de la opción de campo) ya que tienen la forma
x ² + y ² = 1 + d x ² y ².
Hamburg eligió d = -39081 por las razones explicadas en el documento.
La mayoría de las curvas elípticas utilizadas en ECC funcionan actualmente en los campos principales de Orden 256 bits, proporcionando 128 bits de seguridad. La motivación para desarrollar Ed448 fue muy similar a la del desarrollo de P-384. Ambos trabajan en campos más grandes y, por lo tanto, proporcionan más bits de seguridad, 224 y 192 bits, respectivamente.
A diferencia de P-384, Ed448 es una curva segura [19459207] que significa que se presta para una implementación práctica segura. 19659003] Publicaciones relacionadas
[1] Aquí solo aplicamos el algoritmo de Karatsuba una vez. Podría aplicarlo de forma recursiva para multiplicar dos n -bit números en O ( n k ) tiempo, donde k = log [1945900021] ] 2 3 ≈ 1.86. Este algoritmo, descubierto en 1960, fue el primer algoritmo de multiplicación más rápido que O ( n ²).
[2] La suma y la resta son operaciones O ( n ). ¿Y qué hay de la multiplicación? Esa no es una pregunta fácil. No es peor que O ( n 1.68 ) en virtud del algoritmo de Karatsuba. De hecho, es O ( n log n ), pero solo para números poco grandes. Vea la discusión aquí . Pero en cualquier caso, la multiplicación es más lenta que la suma para los números de multiprecisión.
No comments:
Post a Comment