3. Potęgowanie modulo

Matura pokazowa marzec 2022 - Matura z informatyki: arkusze krok po kroku (Python)

**Zadanie 3. Potęgowanie modulo.** b = a^x mod M to reszta z dzielenia a^x przez M, np. 2^5 mod 7 = 32 mod 7 = 4. Działa tak potęgowanie w szyfrze RSA, gdzie liczby są ogromne, dlatego reszty bierze się po każdym mnożeniu: (p · q) mod M = ((p mod M) · (q mod M)) mod M. Wtedy liczby nigdy nie przekraczają M², a wynik się nie zmienia. Najprostszy sposób to x mnożeń. Program liczy przykłady z arkusza i pokazuje, ile mnożeń potrzeba dla x = 1000.

multiplications = 0


def power_slow(a, x, M):
    global multiplications
    b = 1 % M
    for _ in range(x):  # x mnożeń
        b = b * a % M
        multiplications = multiplications + 1
    return b


print(power_slow(2, 5, 7), power_slow(3, 3, 11), power_slow(10, 2, 13))
multiplications = 0
print(power_slow(3, 1000, 1000003))
print("mnożeń:", multiplications)

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Matura z informatyki: arkusze krok po kroku·Zaloguj się, aby zapisać postęp na koncie.