Question

QI live output with explanation O LET A=2 20 LET B = (A *100) MOD 30 30 Print B Kort 40 END​

Answer 1

Answer:

A^B mod C = ( (A mod C)^B ) mod C

Often we want to calculate A^B mod C for large values of B.

Unfortunately, A^B becomes very large for even modest sized values for B.

For example:

2^90 = 1237940039285380274899124224

7^256 = 2213595400046048155450188615474945937162517050260073069916366390524704974007989996848003433 83794038078279445526231260759886736342594056001485602786638194645895120583737911647366324673350968 0721264246243189632348313601

These huge values cause our calculators and computers to return overflow errors.

Even if they didn't, it would take a long time to find the mod of these huge numbers directly.

What can we do to reduce the size of terms involved and make our calculation faster?

Suppose we want to calculate 2^90 mod 13, but we have a calculator that can't hold any numbers larger than 2^50.

Here is a simple divide and conquer strategy:

smaller parts

exponent rules

2^90 = 2^50 * 2^40

mod C

each part

2^50 mod 13 = 1125899906842624 mod 13 = 4

2^40 mod 13 = 1099511627776 mod 13 = 3

multiplication properties

combine the parts

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

How can we calculate A^B mod C quickly if B is a power of 2 ?

How could we calculate 7^256 mod 13 using a calculator that can't hold numbers larger than 7^10 ?

We could split 7^256 into 25 parts of 7^10 and 1 part of 7^6, but this wouldn't be very efficient.