Եթե տեսնում ես այս հաղորդագրությունը, նշանակում է՝ մեզ չի հաջողվում կայքում արտաքին ռեսուրսներ բեռնել։

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Հիմնական նյութ

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

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

Օրինակ՝

2^90 = 1237940039290000000000000000
7^256 = 2213595400050000000000000000000000000000000000000000000000000000000000000000000000000000000 83794038078300000000000000000000000000000000000000000000000000000000000000000000000000000000000000 721264246243000000000000000
Այս ահռելի արժեքների պատճառով հաշվիչները կամ համակարգիչները կարող են հանգել գերլցման։
Նույնիսկ եթե չհանգեն, երկար ժամանակ կպահանջվի դրանց mod-ը միանգամից գտնելու համար։

Ինչպես կարող ենք անդամների չափերը փոքրացնել և ավելի արագ կատարել հաշվումները

Պատկերացրու՝ ուզում ենք հաշվել 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-ն արագ հաշվել, եթե B-ն 2-ի աստիճան է

Ինչպե՞ս կարող ենք հաշվել 7^256 mod 13-ն այն հաշվիչով, որը 7^10-ից մեծ թվեր չի կարողանում հաշվել։
Կարող ենք 7^256-ը բաժանել 25 հատ 7^10-ի և 1 հատ 7^6-ի, բայց դա շատ արդյունավետ չի լինի։
Կա ավելի լավ եղանակ․․․

Ուզո՞ւմ ես միանալ խոսակցությանը։

Առայժմ հրապարակումներ չկան։
Անգլերեն հասկանո՞ւմ ես: Սեղմիր այստեղ և ավելի շատ քննարկումներ կգտնես «Քան» ակադեմիայի անգլերեն կայքում: