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

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

(limited to 'lab9/lab9.py')

diff --git a/lab9/lab9.py b/lab9/lab9.py
new file mode 100644
index 0000000..5024088
--- /dev/null
+++ b/lab9/lab9.py
@@ -0,0 +1,84 @@
+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 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 lucas_test(n):
+    prev_n = n - 1
+    prime_divisors = get_only_prime_divisors(prev_n)
+    for a in range(2, n):
+        is_prime = True
+        if pow(a, prev_n, n) != 1:
+            continue
+        for q in prime_divisors:
+            if pow(a, prev_n // q, n) == 1:
+                is_prime = False
+                break
+        if is_prime:
+            return True
+    return False
+
+
+def get_random_number(n):
+    while True:
+        number = random.randrange(2 ** (n - 1) + 1, 2 ** n - 1)
+        if number % 2 == 0:
+            continue
+        for divisor in first_primes_list:
+            if number % divisor == 0 and divisor ** 2 <= number:
+                break
+        else:
+            return number
+
+
+def create_prime(n):
+    while True:
+        number = get_random_number(n)
+        if lucas_test(number):
+            return number
+
+
+first_primes_list = erathosphene(500)
+if __name__ == "__main__":
+    print("Введите количество бит генерируемого простого числа:")
+    n = int(input())
+    result = create_prime(n)
+    print(f"Сгенерированное простое число: {result}")
-- 
cgit v1.2.3