Հիմնական նյութ
Դասընթաց․ (Համակարգչային գիտություն) > Բաժին 2
Դաս 5: Մոդուլյար թվաբանություն- Ինչ է մոդուլյար թվաբանությունը
- Մոդուլյար անցում
- Մոդուլյար մարտահրավեր
- Մոդուլյար բաղդատում
- Բաղդատման հարաբերություն
- Համարժեքության հարաբերություն
- Մնացորդով բաժանման թեորեմ
- Մոդուլյար գումարում և հանում
- Մոդուլյար գումարում
- Մոդուլյար մարտահրավեր (գումարում և հանում)
- Մոդուլյար արտադրյալ
- Մոդուլյար արտադրյալ
- Մոդուլյար աստիճանացույց
- Արագ մոդուլյար աստիճանացույց
- Արագ մոդուլյար աստիճանացույց
- Մոդուլյար հակադարձներ
© 2024 Khan AcademyՕգտագործման պայմաններԳաղտնիության քաղաքականությունՔուքի (Cookie) ծանուցում
Արագ մոդուլյար աստիճանացույց
Ինչպես կարող ենք A^B mod C-ն արագ հաշվել, եթե B-ն 2-ի աստիճան է
Բազմապատկման կանոնն օգտագործելով,
Օրինակ՝ A^2 mod C = (A * A) mod C = ((A mod C) * (A mod C)) mod C
Այսպես կարող ենք արագ հաշվել 7^256 mod 13-ը.
7^1 mod 13 = 7
7^2 mod 13 = (7^1 *7^1) mod 13 = (7^1 mod 13 * 7^1 mod 13) mod 13
7^2 mod 13 = (7^1 *7^1) mod 13 = (7^1 mod 13 * 7^1 mod 13) mod 13
Նախորդ արդյունքը կարող ենք այս հավասարման մեջ փոխարինել 7^1 mod 13-ով։
7^2 mod 13 = (7 *7) mod 13 = 49 mod 13 = 10
7^2 mod 13 = 10
7^2 mod 13 = 10
7^4 mod 13 = (7^2 *7^2) mod 13 = (7^2 mod 13 * 7^2 mod 13) mod 13
Նախորդ արդյունքը կարող ենք այս հավասարման մեջ փոխարինել 7^2 mod 13-ով։
7^4 mod 13 = (10 * 10) mod 13 = 100 mod 13 = 9
7^4 mod 13 = 9
7^4 mod 13 = 9
7^8 mod 13 = (7^4 * 7^4) mod 13 = (7^4 mod 13 * 7^4 mod 13) mod 13
Նախորդ արդյունքը կարող ենք այս հավասարման մեջ փոխարինել 7^4 mod 13-ով։
7^8 mod 13 = (9 * 9) mod 13 = 81 mod 13 = 3
7^8 mod 13 = 3
7^8 mod 13 = 3
Այսպես կարող ենք շարունակենք՝ օգտագործելով նախորդ արժեքները մեր հավասարումների մեջ։
..,5 քայլ հետո կհասնենք՝
7^256 mod 13 = (7^128 * 7^128) mod 13 = (7^128 mod 13 * 7^128 mod 13) mod 13
7^256 mod 13 = (3 * 3) mod 13 = 9 mod 13 = 9
7^256 mod 13 = 9
7^256 mod 13 = (3 * 3) mod 13 = 9 mod 13 = 9
7^256 mod 13 = 9
Այսպես ունեցանք A^B mod C-ն արագ հաշվելու մեթոդ այն դեպքերի համար, երբ B-ն 2-ի աստիճան է։
Սակայն մեզ նաև պետք է մեթոդ այն բոլոր դեպքերի համար, երբ B-ն 2-ի աստիճան չէ։
Ինչպես կարող ենք A^B mod C-ն արագ հաշվել ցանկացած B-ի համար
Քայլ 1․ B-ն երկուականի վերածելով բաժանիր 2-ի աստիճանների
Սկսիր աջ կողմի թվանշանից․ վերցնենք k=0 և ամեն թվանշանի համար՝
- Եթե թվանշանը 1 է, այն դառնում է 2^k-ի մաս, այլապես՝ ոչ,
- k-ին գումարում ենք 1 և անցնում հաջորդ՝ ձախ կողմի թվանշանին:
Քայլ 2․ Հաշվիր երկուսի այն աստիճանների mod C-ն, որոնք ≤ B
5^1 mod 19 = 5
5^2 mod 19 = (5^1 * 5^1) mod 19 = (5^1 mod 19 * 5^1 mod 19) mod 19
5^2 mod 19 = (5 * 5) mod 19 = 25 mod 19
5^2 mod 19 = 6
5^2 mod 19 = (5 * 5) mod 19 = 25 mod 19
5^2 mod 19 = 6
5^4 mod 19 = (5^2 * 5^2) mod 19 = (5^2 mod 19 * 5^2 mod 19) mod 19
5^4 mod 19 = (6 * 6) mod 19 = 36 mod 19
5^4 mod 19 = 17
5^4 mod 19 = (6 * 6) mod 19 = 36 mod 19
5^4 mod 19 = 17
5^8 mod 19 = (5^4 * 5^4) mod 19 = (5^4 mod 19 * 5^4 mod 19) mod 19
5^8 mod 19 = (17 * 17) mod 19 = 289 mod 19
5^8 mod 19 = 4
5^8 mod 19 = (17 * 17) mod 19 = 289 mod 19
5^8 mod 19 = 4
5^16 mod 19 = (5^8 * 5^8) mod 19 = (5^8 mod 19 * 5^8 mod 19) mod 19
5^16 mod 19 = (4 * 4) mod 19 = 16 mod 19
5^16 mod 19 = 16
5^16 mod 19 = (4 * 4) mod 19 = 16 mod 19
5^16 mod 19 = 16
5^32 mod 19 = (5^16 * 5^16) mod 19 = (5^16 mod 19 * 5^16 mod 19) mod 19
5^32 mod 19 = (16 * 16) mod 19 = 256 mod 19
5^32 mod 19 = 9
5^32 mod 19 = (16 * 16) mod 19 = 256 mod 19
5^32 mod 19 = 9
5^64 mod 19 = (5^32 * 5^32) mod 19 = (5^32 mod 19 * 5^32 mod 19) mod 19
5^64 mod 19 = (9 * 9) mod 19 = 81 mod 19
5^64 mod 19 = 5
5^64 mod 19 = (9 * 9) mod 19 = 81 mod 19
5^64 mod 19 = 5
Քայլ 3․ Օգտագործիր մոդուլյար բազմապատկման հատկությունները, որ միացնես mod C-ի արժեքները
5^117 mod 19 = ( 5^1 * 5^4 * 5^16 * 5^32 * 5^64) mod 19
5^117 mod 19 = ( 5^1 mod 19 * 5^4 mod 19 * 5^16 mod 19 * 5^32 mod 19 * 5^64 mod 19) mod 19
5^117 mod 19 = ( 5 * 17 * 16 * 9 * 5 ) mod 19
5^117 mod 19 = 61200 mod 19 = 1
5^117 mod 19 = 1
5^117 mod 19 = ( 5^1 mod 19 * 5^4 mod 19 * 5^16 mod 19 * 5^32 mod 19 * 5^64 mod 19) mod 19
5^117 mod 19 = ( 5 * 17 * 16 * 9 * 5 ) mod 19
5^117 mod 19 = 61200 mod 19 = 1
5^117 mod 19 = 1
Նշումներ
Գոյություն ունեն ավելի շատ տեխնիկաներ, բայց դրանք չեն վերաբերվում կոնկրետ այս հոդվածին։ Նկատի պետք է ունենանք, որ մենք կատարում ենք մոդուլյար գործողություն ծածկագրման մեջ, և անսովոր կլինի օգտագործել B > 1000 ցուցիչներ։
Ուզո՞ւմ ես միանալ խոսակցությանը։
Առայժմ հրապարակումներ չկան։