Մոդուլյար արտադրյալ

Արի ուսումնասիրենք մոդուլյար գործողությունների բազմապատկման հատկությունը․

(A * B) mod C = (A mod C * B mod C) mod C

Տրված է՝ A=4, B=7, C=6

Արի ստուգենք․ (A * B) mod C = (A mod C * B mod C) mod C

ՀՁԿ= Հավասարման ձախ կողմ

ՀԱԿ= Հավասարման աջ կողմ

ՀՁԿ = (A * B) mod C

ՀՁԿ = (4 * 7) mod 6

ՀՁԿ = 28 mod 6

ՀՁԿ = 4

ՀԱԿ = (A mod C * B mod C) mod C

ՀԱԿ = (4 mod 6 * 7 mod 6) mod 6

ՀԱԿ = (4 * 1) mod 6

ՀԱԿ = 4 mod 6

ՀԱԿ = 4

ՀՁԿ = ՀԱԿ = 4

Մենք կապացուցենք, որ (A * B) mod C = (A mod C * B mod C) mod C

Պետք է ցույց տանք, որ ՀՁԿ = ՀԱԿ

Մնացորդով բաժանման թեորեմից կարող ենք A-ն և B-ն գրել որպես․

A = C * Q1 + R1, որտեղ 0 ≤ R1 < C և Q1-ն ինչ-որ ամբողջ թիվ է։ A mod C = R1

B = C * Q2 + R2, որտեղ 0 ≤ R2 < C և Q2-ն ինչ-որ ամբողջ թիվ է։ B mod C = R2

ՀՁԿ = (A * B) mod C

ՀՁԿ = ((C * Q1 + R1 ) * (C * Q2 + R2) ) mod C

ՀՁԿ = (C * C * Q1 * Q2 + C * Q1 * R2 + C * Q2 * R1 + R1 * R 2 ) mod C

ՀՁԿ = (C * (C * Q1 * Q2 + Q1 * R2 + Q2 * R1) + R1 * R 2 ) mod C

Կարող ենք արտաքսել C-ի բազմապատիկները mod C գործողությունը կատարելիս

ՀՁԿ = (R1 * R2) mod C

Հետո արի անենք ՀԱԿ-ն

ՀԱԿ = (A mod C * B mod C) mod C

ՀԱԿ = (R1 * R2 ) mod C

Հետևաբար, ՀԱԿ = ՀՁԿ

ՀՁԿ = ՀԱԿ = (R1 * R2 ) mod C

Դասակարգել ըստ

Առայժմ հրապարակումներ չկան։