If you're seeing this message, it means we're having trouble loading external resources on our website.

Ако си зад уеб филтър, моля, увери се, че домейните *. kastatic.org и *. kasandbox.org са разрешени.

Основно съдържание

Степенуване по модул

Накрая ще разгледаме и свойството степенуване:
A^B mod C = ( (A mod C)^B ) mod C
Често искаме да изчислим A^B mod C за големи стойности на B.
За съжаление, A^B става много голямо дори за най-скромните стойности на B.

Например:

2^90 = 1 237 940 039 290 000 000 000 000 000
7^256 = 2 213 595 400 050 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 83 794 038 078 300 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 721 264 246 243 000 000 000 000 000
Заради тези големи стойности калкулаторите и компютрите ни връщат грешки поради препълване (overflow errors).
Дори и да не го направят, намирането на модула на тези големи числа ще отнеме много време.

Какво можем да направим, за да намалим размера на замесените числа и да направим изчисленията по-бързо?

Да речем, че искаме да изчислим 2^90 mod 13, но калкулаторът ни не може да поддържа числа, по-големи от 2^50.
Ето една проста стратегия разделяй и владей:
по-малки части
правилата за степенуване
2^90 = 2^50 * 2^40
mod C
всяка част
2^50 mod 13 = 1125899906842624 mod 13 = 4
2^40 mod 13 = 1099511627776 mod 13 = 3
свойства на умножението
за комбиниране на частите
2^90 mod 13 = (2^50 * 2^40) mod 13
2^90 mod 13 = (2^50 mod 13 * 2^40 mod 13) mod 13
2^90 mod 13 = ( 4 * 3 ) mod 13
2^90 mod 13 = 12 mod 13
2^90 mod 13 = 12

Как можем бързо да изчислим A^B mod C, ако В е на степен 2?

Как можем да изчислим 7^256 mod 13, като използваме калкулатор, който не може да поддържа числа, по-големи от 7^10 ?
Можем да разделим 7^256 на 25 части от 7^10 и 1 част от 7^6, но това няма да е много ефикасно.
Има и по-добър начин....

Искаш ли да се присъединиш към разговора?

Все още няма публикации.
Разбираш ли английски? Натисни тук, за да видиш още дискусии в английския сайт на Кан Академия.