Home
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
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