Kryptografia/miniprojekt1/zad3.py

26 lines
537 B
Python

import random
# Test fermata - snrawdzanie czy liczba jest nierwsza
def potegowanieimod(b, k, n):
y = 1
while k > 0:
if k & 1:
y = y*b % n
b = b**2 % n
k = k >> 1
return y
def fermat(k, n):
i = 0
while i < k:
a = random.randint(1, n - 1)
if potegowanieimod(a, (n - 1), n) == 1:
i = i + 1
else:
return False
return True
n = int(input("Podaj liczbę do sprawdzenia: "))
print("Liczba jest pierwsza: {}".format(fermat(100, n)))