From 0be2be0a92f992bf8ee9eff701cb19658a1e7544 Mon Sep 17 00:00:00 2001
From: Andrew Guschin <guschin.drew@gmail.com>
Date: Thu, 29 Dec 2022 15:20:32 +0400
Subject: =?UTF-8?q?=D0=94=D0=BE=D0=B1=D0=B0=D0=B2=D0=BB=D0=B5=D0=BD=D1=8B?=
 =?UTF-8?q?=20=D0=BB=D0=B0=D0=B1=D1=8B=208-15?=
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 lab10/lab10.py | 96 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 96 insertions(+)
 create mode 100644 lab10/lab10.py

(limited to 'lab10/lab10.py')

diff --git a/lab10/lab10.py b/lab10/lab10.py
new file mode 100644
index 0000000..2e63379
--- /dev/null
+++ b/lab10/lab10.py
@@ -0,0 +1,96 @@
+import math
+import random
+
+
+def erathosphene(n):
+    is_prime = [True] * n
+    p = 2
+    while p * p < n:
+        cur = p * p;
+        while cur < n:
+            is_prime[cur] = False;
+            cur += p;
+        while not is_prime[p + 1]:
+            p += 1;
+        p += 1
+    primes = []
+    for i, p in enumerate(is_prime):
+        if p:
+            primes.append(i)
+    return primes[2:]
+
+
+def fast_power(base, power):
+    result = 1
+    while power > 0:
+        if power % 2 == 0:
+            power = power // 2
+            base *= base
+        else:
+            power -= 1
+            result = result * base
+            power = power // 2
+            base *= base
+    return result
+
+
+def get_only_prime_divisors(n):
+    factors = []
+    if (n % 2 == 0):
+        factors.append(2)
+
+    while (n % 2 == 0):
+        n = n // 2
+
+    for i in range(3, int(math.sqrt(n)) + 1, 2):
+        if (n % i == 0):
+            factors.append(i)
+
+        while (n % i == 0):
+            n = n // i
+
+    if (n > 2):
+        factors.append(n)
+
+    return factors
+
+
+def pocklington_criterion(n, borded_a):
+    prev_n = n - 1
+    prime_divisors = get_only_prime_divisors(prev_n)
+    prime_divisors = filter(lambda q: q > math.sqrt(n) - 1, prime_divisors)
+
+    for a in range(2, borded_a):
+        if pow(a, prev_n, n) != 1:
+            continue
+        for q in prime_divisors:
+            if math.gcd(n, fast_power(a, prev_n // q) - 1) == 1:
+                return True
+    return False
+
+
+def get_random_number(n):
+    while True:
+        number = random.randrange(2 ** (n-1) + 1, 2 ** n - 1)
+        for divisor in first_primes_list:
+            if number % divisor == 0 and divisor ** 2 <= number:
+                break
+        else:
+            return number
+
+
+def create_prime(n, a):
+    while True:
+        number = get_random_number(n)
+        if pocklington_criterion(number, a):
+            return number
+
+
+first_primes_list = erathosphene(500)
+if __name__ == "__main__":
+    print("Введите количество бит генерируемого простого числа:")
+    n = int(input())
+    print("Введите верхнюю границу числа 'a' в критерии Поклингтона (не меньше 3):")
+    a = int(input())
+    result = create_prime(n, a)
+    print(f"Сгенерированное простое число: {result}")
-- 
cgit v1.2.3