import random
def power(a, n, p):
res = 1
a = a % p
while n > 0:
if n & 1:
res = (res * a) % p
n = n >> 1
a = (a * a) % p
return res
def jacobi(a, n):
if n <= 0 or n % 2 == 0:
raise ValueError("n must be a positive odd integer.")
if a == 0:
return 0
if a == 1:
return 1
result = 1
while a != 0:
while a % 2 == 0:
a //= 2
if n % 8 == 3 or n % 8 == 5:
result =
-result
a, n = n, a
if a % 4 == 3 and n % 4 == 3:
result = -result
a %= n
if n == 1:
return result
return 0
def solovay_strassen_test(n, k):
if n <= 1:
return False
if n == 2 or n == 3:
return True
for _ in range(k):
a = random.randint(2, n - 2)
x = power(a, (n - 1) // 2, n)
if x != 1 and x != n - 1:
return False
jacobi_val = jacobi(a, n)
if x % n != jacobi_val % n:
return False
return True
number_str = "151617181920212223242526272829303132333435363738394041424
3444546474849505152535455565758596061 "
number = int(number_str)
iterations = 5
if solovay_strassen_test(number, iterations):
print("Berilgan son tub son hisoblanadi.")
else:
print("Berilgan son tub son emas.")
