Մոդուլյար աստիճանացույց

Եվ վերջում արի ուսումնասիրենք աստիճան բարձրացնելու հատկությունը․

Հաճախ մենք ուզում ենք հաշվել A^B mod C-ն B-ի մեծ արժեքների համար։
Դժբախտաբար, A^B-ն հսկայական թիվ է նույնիսկ միջին մեծության B-երի համար։

2^90 = 1237940039290000000000000000

7^256 = 2213595400050000000000000000000000000000000000000000000000000000000000000000000000000000000 83794038078300000000000000000000000000000000000000000000000000000000000000000000000000000000000000 721264246243000000000000000

Այս ահռելի արժեքների պատճառով հաշվիչները կամ համակարգիչները կարող են հանգել գերլցման։
Նույնիսկ եթե չհանգեն, երկար ժամանակ կպահանջվի դրանց mod-ը միանգամից գտնելու համար։

Պատկերացրու՝ ուզում ենք հաշվել 2^90 mod 13-ը, բայց մեր հաշվիչը 2^50-ից մեծ թվեր չի կարողանում հաշվել։

Ահա հասարակ «Բաժանիր և տիրիր» մարտավարություն․

2^90 = 2^50 * 2^40

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

Ինչպե՞ս կարող ենք հաշվել 7^256 mod 13-ն այն հաշվիչով, որը 7^10-ից մեծ թվեր չի կարողանում հաշվել։

Կարող ենք 7^256-ը բաժանել 25 հատ 7^10-ի և 1 հատ 7^6-ի, բայց դա շատ արդյունավետ չի լինի։

Կա ավելի լավ եղանակ․․․