Conţinutul principal

Inverse modulare

Clasa Google

Ce este un invers?

Un număr înmulțit cu inversul său este egal cu 1. Din aritmetica elementară știm că:

Inversul unui număr A este 1/A deoarece A * 1/A = 1 (de exemplu, inversul lui 5 este 1/5)
Toate numerele reale diferite de 0 au un invers
Înmulțirea unui număr cu inversul lui A este echivalentă cu împărțirea la A (de exemplu, 10/5 este egal cu 10* 1/5)

Ce este un invers modular?

În aritmetica modulară nu avem operația de împărțire. Totuși, avem conceptul de invers modular.

Inversul modular al lui A (mod C) este A^-1
(A * A^-1) ≡ 1 (mod C) sau (A * A^-1) mod C = 1
Doar numerele prime cu C (numere care nu au factori primi comuni cu C) au un invers modular (mod C)

Aflarea inversului modular

O metodă naivă de a găsi un invers modular pentru A (mod C) are următorii pași:

Pasul 1. Calculăm A * B mod C pentru B de la 0 la C-1

Pasul 2. Inversul modular al lui A mod C este valoarea B pentru care A * B mod C = 1

Observă că B mod C poate avea doar o valoare întreagă în intervalul de la 0 la C-1, astfel că testarea de valori mai mari pentru B este redundantă (este inutilă).

Exemplu: A=3 și C=7

Pasul 1. Calculăm A * B mod C pentru B în intervalul de la 0 la C-1

3 * 0 ≡ 0 (mod 7)

3 * 1 ≡ 3 (mod 7)

3 * 2 ≡ 6 (mod 7)

3 * 3 ≡ 9 ≡ 2 (mod 7)

3 * 4 ≡ 12 ≡ 5 (mod 7)

3 * 5 ≡ 15 (mod 7) ≡ 1 (mod 7) <------ AM GĂSIT INVERSUL!

3 * 6 ≡ 18 (mod 7) ≡ 4 (mod 7)

**Pasul 2. Inversul modular al lui A mod C este valoarea B astfel încât A * B mod C = 1**

5 este inversul modular al lui 3 mod 7 deoarece 5*3 mod 7 = 1

Simplu!

Hai să mai vedem un exemplu pentru care nu vom găsi niciun invers.

Exemplu: A=2 și C=6

**Pasul 1. Calculăm A * B mod C pentru B cu valori în intervalul de la 0 la C-1**

2 * 0 ≡ 0 (mod 6)

2 * 1 ≡ 2 (mod 6)

2 * 2 ≡ 4 (mod 6)

2 * 3 ≡ 6 ≡ 0 (mod 6)

2 * 4 ≡ 8 ≡ 2 (mod 6)

2 * 5 ≡ 10 ≡ 4 (mod 6)

**Pasul 2. Inversul modular al lui A mod C este valoarea B pentru care A * B mod C = 1**

Nu există o valoare a lui B pentru care A * B mod C = 1. De aceea, A nu are invers modular (mod 6), deoarece 2 nu este prim cu 6 (aceste numere au în comun factorul prim 2).

Această metodă pare înceată...

Există o metodă mult mai rapidă pentru identificarea inversului lui A (mod C), pe care o vom discuta în următoarele articole despre algoritmul lui Euclid extins.

Vrei să te alături conversației?

Conectare

Ordonare după:

Nici o postare încă.

Înțelegi engleza? Dă clic aici pentru a vedea mai multe discuții care au loc pe site-ul în limba engleză al Khan Academy.

Teoria informației și criptografie

Curs: Teoria informației și criptografie > Unitatea 2