Jaccobi.py

from toolkit import *
import random

nlst = [17 * 19, 23 * 47]
for n in nlst:
    for b in range(n):
        left = pow(b, (n - 1) // 2, n)
        # print(left)
        if abs(left) != 1 and abs(left) != n - 1:
            continue
        right = Jacobi(b, n)
        # print('left =', left, 'right =', right)
        if (left - right) % n == 0:
            # pass
            print(n, 'is a Euler pseudoprime based on', b)

t = 30
found = False
while not found:
    n = randint(4)
    while len(str(n)) < 10:
        n = randint(4)
    for i in range(t):
        b = 2
        while gcd(b, n) != 1:
            b = randint(1)
        # generates b that (b, n) = 1

        left = pow(b, (n - 1) // 2, n)
        if abs(left) != 1 and abs(left) != n - 1:
            # then n cannot be prime
            break
        right = Jacobi(b, n)
        if (left - right) % n != 0:
            break
        if i == t - 1:
            found = True
            print('Prime number generated by Solovay-Stassen test is', n)