diff options
| author | Andrew Guschin <guschin.drew@gmail.com> | 2022-12-29 15:20:32 +0400 |
|---|---|---|
| committer | Andrew Guschin <guschin.drew@gmail.com> | 2022-12-29 15:20:32 +0400 |
| commit | 0be2be0a92f992bf8ee9eff701cb19658a1e7544 (patch) | |
| tree | 5d855004fd8cc067a594475c0a666eb01f0ceefa /lab10 | |
| parent | 056f59346b727c9367998a423551eaba52854fce (diff) | |
Diffstat (limited to 'lab10')
| -rw-r--r-- | lab10/lab10.py | 96 |
1 files changed, 96 insertions, 0 deletions
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}")
|