La exponenciación es una operación muy utilizada en la criptografía de clave pública. ¿Cuál de las siguientes opciones es el límite superior más estricto en el número de multiplicaciones requeridas para calcular b n mod m,0≤b,n≤m ?
(A) O(logn)
(B) O(√n)
(C) O(n/logn)
(D) O(n)
Respuesta: (A)
Explicación:
Este problema se puede resolver usando el paradigma Divide and Conquer
Algoritmo:
Binary_exp(b,n) // Compute bn mod m
{
if(n == 0)
Return 1;
Else if(n == 1)
Return b mod m;
Else
{
Half = Binary_exp(b,n/2);
if(n%2 == 0) // n is even
Return (Half*Half) mod m;
Else // n is odd
Return (((Half*Half) mod m)*n) mod m;
}
}
La relación de recurrencia para calcular la complejidad temporal del algoritmo anterior es
T(n) = T(n/2) + constante = (log2n)
Esta solución es aportada por Pranjul Ahuja .
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA