mirror of
https://github.com/TheAlgorithms/Python.git
synced 2024-10-05 21:29:29 +00:00
4d0c830d2c
* ci(pre-commit): Add ``flake8-builtins`` additional dependency to ``pre-commit`` (#7104) * refactor: Fix ``flake8-builtins`` (#7104) * fix(lru_cache): Fix naming conventions in docstrings (#7104) * ci(pre-commit): Order additional dependencies alphabetically (#7104) * fix(lfu_cache): Correct function name in docstring (#7104) * Update strings/snake_case_to_camel_pascal_case.py Co-authored-by: Christian Clauss <cclauss@me.com> * Update data_structures/stacks/next_greater_element.py Co-authored-by: Christian Clauss <cclauss@me.com> * Update digital_image_processing/index_calculation.py Co-authored-by: Christian Clauss <cclauss@me.com> * Update graphs/prim.py Co-authored-by: Christian Clauss <cclauss@me.com> * Update hashes/djb2.py Co-authored-by: Christian Clauss <cclauss@me.com> * refactor: Rename `_builtin` to `builtin_` ( #7104) * fix: Rename all instances (#7104) * refactor: Update variable names (#7104) * [pre-commit.ci] auto fixes from pre-commit.com hooks for more information, see https://pre-commit.ci * ci: Create ``tox.ini`` and ignore ``A003`` (#7123) * revert: Remove function name changes (#7104) * [pre-commit.ci] auto fixes from pre-commit.com hooks for more information, see https://pre-commit.ci * Rename tox.ini to .flake8 * Update data_structures/heap/heap.py Co-authored-by: Dhruv Manilawala <dhruvmanila@gmail.com> * refactor: Rename `next_` to `next_item` (#7104) * ci(pre-commit): Add `flake8` plugin `flake8-bugbear` (#7127) * refactor: Follow `flake8-bugbear` plugin (#7127) * fix: Correct `knapsack` code (#7127) * [pre-commit.ci] auto fixes from pre-commit.com hooks for more information, see https://pre-commit.ci Co-authored-by: Christian Clauss <cclauss@me.com> Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com> Co-authored-by: Dhruv Manilawala <dhruvmanila@gmail.com>
224 lines
3.2 KiB
Python
224 lines
3.2 KiB
Python
# Primality Testing with the Rabin-Miller Algorithm
|
|
|
|
import random
|
|
|
|
|
|
def rabin_miller(num: int) -> bool:
|
|
s = num - 1
|
|
t = 0
|
|
|
|
while s % 2 == 0:
|
|
s = s // 2
|
|
t += 1
|
|
|
|
for _ in range(5):
|
|
a = random.randrange(2, num - 1)
|
|
v = pow(a, s, num)
|
|
if v != 1:
|
|
i = 0
|
|
while v != (num - 1):
|
|
if i == t - 1:
|
|
return False
|
|
else:
|
|
i = i + 1
|
|
v = (v**2) % num
|
|
return True
|
|
|
|
|
|
def is_prime_low_num(num: int) -> bool:
|
|
if num < 2:
|
|
return False
|
|
|
|
low_primes = [
|
|
2,
|
|
3,
|
|
5,
|
|
7,
|
|
11,
|
|
13,
|
|
17,
|
|
19,
|
|
23,
|
|
29,
|
|
31,
|
|
37,
|
|
41,
|
|
43,
|
|
47,
|
|
53,
|
|
59,
|
|
61,
|
|
67,
|
|
71,
|
|
73,
|
|
79,
|
|
83,
|
|
89,
|
|
97,
|
|
101,
|
|
103,
|
|
107,
|
|
109,
|
|
113,
|
|
127,
|
|
131,
|
|
137,
|
|
139,
|
|
149,
|
|
151,
|
|
157,
|
|
163,
|
|
167,
|
|
173,
|
|
179,
|
|
181,
|
|
191,
|
|
193,
|
|
197,
|
|
199,
|
|
211,
|
|
223,
|
|
227,
|
|
229,
|
|
233,
|
|
239,
|
|
241,
|
|
251,
|
|
257,
|
|
263,
|
|
269,
|
|
271,
|
|
277,
|
|
281,
|
|
283,
|
|
293,
|
|
307,
|
|
311,
|
|
313,
|
|
317,
|
|
331,
|
|
337,
|
|
347,
|
|
349,
|
|
353,
|
|
359,
|
|
367,
|
|
373,
|
|
379,
|
|
383,
|
|
389,
|
|
397,
|
|
401,
|
|
409,
|
|
419,
|
|
421,
|
|
431,
|
|
433,
|
|
439,
|
|
443,
|
|
449,
|
|
457,
|
|
461,
|
|
463,
|
|
467,
|
|
479,
|
|
487,
|
|
491,
|
|
499,
|
|
503,
|
|
509,
|
|
521,
|
|
523,
|
|
541,
|
|
547,
|
|
557,
|
|
563,
|
|
569,
|
|
571,
|
|
577,
|
|
587,
|
|
593,
|
|
599,
|
|
601,
|
|
607,
|
|
613,
|
|
617,
|
|
619,
|
|
631,
|
|
641,
|
|
643,
|
|
647,
|
|
653,
|
|
659,
|
|
661,
|
|
673,
|
|
677,
|
|
683,
|
|
691,
|
|
701,
|
|
709,
|
|
719,
|
|
727,
|
|
733,
|
|
739,
|
|
743,
|
|
751,
|
|
757,
|
|
761,
|
|
769,
|
|
773,
|
|
787,
|
|
797,
|
|
809,
|
|
811,
|
|
821,
|
|
823,
|
|
827,
|
|
829,
|
|
839,
|
|
853,
|
|
857,
|
|
859,
|
|
863,
|
|
877,
|
|
881,
|
|
883,
|
|
887,
|
|
907,
|
|
911,
|
|
919,
|
|
929,
|
|
937,
|
|
941,
|
|
947,
|
|
953,
|
|
967,
|
|
971,
|
|
977,
|
|
983,
|
|
991,
|
|
997,
|
|
]
|
|
|
|
if num in low_primes:
|
|
return True
|
|
|
|
for prime in low_primes:
|
|
if (num % prime) == 0:
|
|
return False
|
|
|
|
return rabin_miller(num)
|
|
|
|
|
|
def generate_large_prime(keysize: int = 1024) -> int:
|
|
while True:
|
|
num = random.randrange(2 ** (keysize - 1), 2 ** (keysize))
|
|
if is_prime_low_num(num):
|
|
return num
|
|
|
|
|
|
if __name__ == "__main__":
|
|
num = generate_large_prime()
|
|
print(("Prime number:", num))
|
|
print(("is_prime_low_num:", is_prime_low_num(num)))
|