Imagínese que tengo una máquina de 64 bits y el entero más ancho disponible tiene una longitud de 64 bits con signo. No puedo usar BigInteger o bibliotecas similares por razones de rendimiento, y todos los cálculos que obtengo me darían un módulo$2^{64}$. Necesito elegir prime$p$ cerca de$2^{63}$ pero menos que$2^{63}$ (¿cuál sería, creo que elegir$2^{61}$ haría que mis cálculos sean más rápidos?) Y necesito implementar la multiplicación módulo$p$. ¿Hay algún algoritmo conocido para hacerlo?
Respuestas
¿Demasiados anuncios?
lhf
Puntos
83572
Si puede elegir un primo de 32 bits como módulo, entonces no necesita hacer nada especial. Si necesita un número primo cercano al máximo de 64 bits, entonces deberá implementar la multiplicación a mano. Pero esto no es complicado. Para multiplicar$a$ y$b$, escriba$a=a_1 \cdot 2^{32} + a_0$ y$b=b_1 \cdot 2^{32} + b_0$, con$0\le a_1,a_0,b_1,b_0 \lt 2^{32}$. Expanda cada término en$ab$, redúzcalos módulo$p$, agréguelos y reduzca el resultado módulo$p$.
DM8
Puntos
459
Si estás haciendo muchas multiplicaciones de números en tu primo, entonces vale la pena implementar la Reducción de Montgomery . Entiendo que está pensando en hacer cálculos mod$2^{61}-1$ pero no creo que pueda evitar al menos calcular de manera implícita un producto de 128 bits cuando multiplica dos números de este tamaño juntos.
Steg
Puntos
4835
Si está pensando en implementar una multiplicación de módulo de 64 bits en C, esta es la rutina más rápida que conozco. Esto supera todas las implementaciones algorítmicas debido a un truco de hardware: el tipo doble largo contiene los bits más significativos después de una multiplicación, mientras que un entero contiene los menos significativos.
if (a >= m) a %= m;
if (b >= m) b %= m;
long double x = a;
uint64_t c = x * b / m;
int64_t r = (int64_t)(a * b - c * m) % (int64_t)m;
return r < 0 ? r + m : r;
donde a, b y m son enteros sin signo de 64 bits. (Tenga en cuenta que m <$2^{63}$ es una necesidad)
