matematika

ucenicki forum


You are not connected. Please login or register

Faktorizacija

Vidi prethodnu temu Vidi sljedeću temu Go down  Poruka [Stranica 1/1]

1 Faktorizacija on Wed Mar 29, 2017 11:07 pm

xy^2

avatar
Admin
Pseudoprosti brojevi

Jedan način za provjeru da li je n prost jest da n dijelimo sa svim prostim brojevima ≤ √n. Ako n nije djeljiv s niti jednim od njih, onda je n sigurno prost. Ovo je vrlo neefikasan test. Budući da prostih brojeva manjih od √n ima O(√n / log n), a za svako dijeljenje trebamo O(log^2 n) operacija, to za ovaj test trebamo O(√n log n) operacija.

Efikasniji testovi se zasnivaju na nekim važnim osobinama prostih brojeva.
Mali Fermatov teorem:

Ako je n prost, onda za svaki cijeli broj b takav da je (b,n) = 1 vrijedi

b^(n -1)  = 1 (mod n).      (*)

Važno je uočiti da obrat ovog teorema ne vrijedi. Naime, n može biti složen, a da ipak za neki b vrijedi relacija (*).

Primjer1

Broj 91 je očito složen jer je 91 = 7 . 13. Međutim,

3^(90)  = 27^(30) = (-1)^(30) = 1 (mod 7)   i   3^(90)  = 27^(30 )= 1^(30 )= 1 (mod 13),

pa je 3^(90)  = 1 (mod 91). No, 2^(90)  = 64 (mod 91), pa i odavde možemo zaključiti da je 91 složen.

https://web.math.pmf.unizg.hr/~duje/kript/pseudoprosti.html

Vidi profil korisnika

Vidi prethodnu temu Vidi sljedeću temu Na vrh  Poruka [Stranica 1/1]

Permissions in this forum:
Ne možete odgovoriti na teme ili komentare u ovom forumu