Рубрики

ВОРОТА | Gate IT 2007 | Вопрос 17

Экспонирование является широко используемой операцией в криптографии с открытым ключом. Какая из следующих опций является самой жесткой верхней границей для числа умножений, необходимых для вычисления b n mod m, 0≤b, n≤m?
(A) O (logn)
(B) O (√n)
(C) O (n / logn)
(D) O (n)

Ответ: (А)
Объяснение:

Эту проблему можно решить с помощью парадигмы «разделяй и властвуй»

Алгоритм:


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;

}

}          

Отношение повторения для вычисления временной сложности приведенного выше алгоритма
T (n) = T (n / 2) + постоянная = (log2n)

Это решение предоставлено Пранджул Ахаджа .
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | Gate IT 2007 | Вопрос 17

0.00 (0%) 0 votes