[Prethodno poglavlje]   [Sljedeće poglavlje]   [Sadržaj]

4.2. Solovay-Strassenov test

Neka je p neparan prost broj. Za broj b, koji je relativno prost s p, kažemo da je kvadratni ostatak modulo p ako kongruencija x2 ≡ b (mod p) ima rješenja. U protivnom, kažemo da je b kvadratni neostatak. Legendreov simbol (b/p) se definira ovako: (b/p) = 1 ako je b kvadratni ostatak modulo p; (b/p) = -1 ako je b kvadratni neostatak modulo p; (b/p) = 0 ako p dijeli b.

Neka je n neparan broj i n = p1 · · · pk njegov rastav na (ne nužno različite) proste faktore. Tada se Jacobijev simbol (b/n) definira sa (b/n) = (b/p_1)...(b/p_k) Ako je n prost, onda se Jacobijev i Legendreov simbol podudaraju. Važno svojstvo Legendreovog simbola je Eulerov kriterij:

(b/p)=b^((p-1)/2) (mod p)

Definicija: Ako je n neparan složen broj, te b cijeli broj takav da je (b,n) = 1 i vrijedi

(b/n)=b^((n-1)/2)

gdje je (b/n) Jacobijev simbol, onda n zovemo Eulerov pseudoprosti broj u bazi b (ili epsp(b)).

Kvadriranjem relacije (**) dobivamo bn -1 ≡ 1 (mod n), tj. relaciju (*). To znači da je svaki epsp(b) ujedno i psp(b). Međutim , obrat ove tvrdnje ne vrijedi.

Primjer 4.2: Vidjeli smo u Primjeru 4.1 da je 91 pseudoprost u bazi 3. Međutim,

345 ≡ 7297 . 27 ≡ 27 (mod 91),

pa 91 nije Eulerov pseudoprost broj u bazi 3. Ipak, 91 jest Eulerov pseudoprost u bazi 10 jer je

1045 ≡ 100015 ≡ (-1)15 ≡ -1 (mod 91)     i     (10 / 91) = -1.


Neka je Zn* = { b ∈ Zn : (b,n) = 1}. Tada je |Zn*| = φ(n). Neka je nadalje

Pn = { b ∈ Zn* : (b/n) ≡ b(n -1)/2 (mod n) }.

Sljedeći teorem predstavlja osnovu za Solovay-Strassenov test prostosti.

Teorem 4.2: Za sve neparne složene brojeve n vrijedi |Pn| ≤ φ(n)/2.

Uočimo važnu razliku između Teorema 4.1.3) i 4.2. Naime, kod Eulerovih pseudoprostih brojeva nema analogona Carmichaelovih brojeva, već za svaki složen broj n, relacija (**) nije zadovoljena za barem pola mogućih baza.

Prije dokaza Teorema 4.2, dokažimo dvije leme. Koristit ćemo oznaku: νm(t) = najveći cijeli broj k takav da mk dijeli t.

Lema 4.1: Neka je n = p1alpha1 . . . pralphar neparan broj, te neka je ν = min { ν2 (pi-1) : i = 1, ... , r }, s = ∏i (m, φ(pialphai). Tada vrijedi:

(1)   Kongruencija xm ≡ 1 (mod n) ima točno s rješenja.

(2)   Kongruencija xm ≡ -1 (mod n) ima rješenja ako i samo ako je ν2(m) < ν.

(3)   Ako kongruencija xm ≡ -1 (mod n) ima rješenja, onda ih ima točno s.

Dokaz: Neka je gi primitivni korijen modulo pialphai, tj. gia ≢ 1 (mod pialphai) za a < φ(pialphai) = pialphai (1 - 1/pi ). To znači da za svaki x ∈ { 1, ... , pialphai - 1 } postoji j takav da je gij ≡ x (mod pialphai). Označimo taj j s indi x. Sada je kongruencija xm ≡ c (mod n) ekvivalentna sustavu kongruencija

m · indi x ≡ indi c (mod φ(pialphai)),   za i = 1, ... , r.         (4.1)

Za c = 1 je indi 1 = 0, pa sustav (4.1) postaje

m · indi x ≡ 0 (mod φ(pialphai)),   za i = 1, ... , r.

Ovo su linearne kongruencije i i-ta ima (m, φ(pialphai)) rješenja. Stoga je ukupan broj rješenja sustava jednak s.

Za c = -1 je indi (-1) = φ(pialphai)/2, pa sustav (4.1) postaje

m . indi x ≡ φ(pialphai)/2 (mod φ(pialphai)),   za i = 1, ... , r.

Sada iz svojstava linearnih kongruencija zaključujemo da ako ovaj sustav ima rješenja, onda ih ima s, a nužan i dovoljan uvjet za postojanje rješenja je da (m,φ(pialphai)) dijeli φ(pialphai)/2. Odavde imamo da (2nu2(m) m1, pialphai -1 . 2nu2(pi -1) q1) dijeli pialphai -1 . 2nu2(pi -1)-1 q1, gdje su m1 i q1 neparni brojevi. No, ovo je očito ekvivalentno s ν2(m) < ν2(pi-1) za i = 1, ... , r, tj. s ν2(m) < ν.

■


Lema 4.2: Neka je n neparan broj, te p1, ..., pr svi različiti prosti faktori od n. Tada je

|P_n|=delta_n*((n-1)/2,p_i-1)

gdje je δn ∈ {1/2, 1, 2}.

Dokaz: Neka je

K_n+-, L_n+-, M_n+-

Tada je Pn = Mn+. Iz Leme 4.1 imamo: |Kn+| = ∏i ((n-1)/2, pi -1). S druge strane, Mn+ = (Kn+ ∩ Ln+) ∪ (Kn- ∩ Ln-). Ako je Kn- ∩ Ln- = ∅, onda je |Mn+| = |Kn+ ∩ Ln+|. Ako je Kn- ∩ Ln- ≠ ∅ i b0 ∈ Kn- ∩ Ln-, onda je preslikavanje f : Kn+ ∩ Ln+ → Kn- ∩ Ln- definirano s f(b) = bb0 bijekcija, pa je |Mn+| = 2|Kn+ ∩ Ln+|. Na isti način, iz relacije Kn+ = (Kn+ ∩ Ln+) ∪ (Kn+ ∩ Ln-) slijedi |Kn+ ∩ Ln+| = |Kn+| ako je Kn+ ∩ Ln- = ∅, te |Kn+ ∩ Ln+| = 1/2 |Kn+| ako je Kn+ ∩ Ln- ≠ ∅.
Stoga je zaista |Pn|= |Mn+|= δn |Kn+|, gdje je δn ∈ {1/2, 1, 2}.

■


Dokaz Teorema 4.1: Neka je n = p_1^a_1...p_r^a_r. Iz Leme 4.2 slijedi

|P_n|/phi(n)= (4.2)

Ako je αi ≥ 2 za neki i, onda je desna strana od (4.2)   ≤ δn/3 ≤ 2/3. Skup Pn je jezgra homomorfizma hn : Zn* → Zn* definiranog s hn(a) = (a/n) a(n-1)/2 mod n, pa je Pn podgrupa od Zn*, a zbog |Pn| < φ(n) je prava podgrupa od Zn*. Stoga je |Pn| ≤ φ(n)/2.

Sada možemo pretpostaviti da je αi = 1, tj. n = p1 · · · pr, r ≥ 2. Pretpostavimo da tvrdnja teorema ne vrijedi. Tada bi bilo Pn = Zn*. Neka je g primitivni korijen modulo p1 (ili bilo koji kvadratni neostatak modulo p1). Po Kineskom teoremu o ostatcima, možemo naći a ∈ Zn* takav da je a ≡ g (mod p1) i a ≡ 1 (mod n/p1). Budući da je Zn* = Pn, to je a(n-1)/2 ≡ (a/n) (mod n). Međutim, (a/n) = (a/p1) (a/(n/p1)) = (g/p1) = -1. Zato je a(n-1)/2 ≡ -1 (mod n/p1), što je u suprotnosti s a ≡ 1 (mod n/p1).

■


Korolar 4.1: Neka je n ≡ 3 (mod 4) složen broj s r različitih prostih faktora. Tada je

|Pn| ≤ φ(n)/2r -1.

Dokaz: Iz relacije (4.2) imamo:

|P_n|/phi(n) <= 1/2^(r-1)

■



Solovay-Strassenov test prostosti:

Neka je n neparan broj za kojeg želimo ustanoviti da li je prost ili složen. Odaberimo na slučajan način k brojeva b takvih da je 0 < b < n. Za svaki od tih b-ova izračunamo obje strane od (**). Za računanje   b(n-1)/2 mod n   treba O(log3 n) operacija metodom kvadriraj i množi. Za računanje Jacobijevog simbola (b/n), koristeći kvadratni zakon reciprociteta, treba O(log2 n) operacija. Ako ova dva broja nisu kongruentna modulo n, onda znamo da je n složen i test staje. Inače uzmemo idući b. Ako n prođe test (**) za k različitih b-ova, onda je vjerojatnost da je n složen ≤ 1/2k. Stoga, ako je k dovoljno velik, n proglašavamo "vjerojatno prostim". U praksi se uzima k = 50 ili k = 100 (2-50 ≈ 10-15, 2-100 ≈ 10-30).

Solovay-Strassenov test je primjer tzv. Monte Carlo algoritma koji uvijek daje odgovor, ali on može biti netočan. Drugi tip vjerojatnosnog algoritma je Las Vegas algoritam koji ne daje uvijek odgovor, ali kada ga da, onda je odgovor sigurno točan. Primjer takvog algoritma smo vidjeli kod faktorizacije RSA modula n ako je poznat tajni eksponent d.


Napomena: Navest ćemo svojstva Jacobijevog simbola koja se koriste u njegovom računanju:

    (1)   a ≡ b (mod n)   ⇒   (a/n) = (b/n)

    (2)   (-1/n) = (-1)(n -1)/2,   (2/n) = (-1)(n2 -1)/8

    (3)   (ab/n) = (a/n) (b/n)

    (4)   (m/n) = - (n/m) ako je m ≡ n ≡ 3 (mod 4), a (m/n) = (n/m) inače.

[Prethodno poglavlje]   [Sljedeće poglavlje]   [Sadržaj]
Web stranica kolegija Kriptografija Andrej Dujella - osobna stranica