-
Notifications
You must be signed in to change notification settings - Fork 0
/
lucas.py
36 lines (22 loc) · 730 Bytes
/
lucas.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
from random import randint
from sympy.ntheory import factorint # sympy required "pip install sympy"
def is_probably_prime(n, k=1):
"""
Lucas primality test
:param n: Number to be tested
:param k: number of iterations, more iterations equals higher accuracy and time complexity
:return: True if number is probably prime, otherwise False
"""
if n < 3 or not n % 2:
return number == 2
for _ in range(k):
a = randint(2, n - 1)
if pow(a, n - 1, n) != 1:
return False
p_factors = factorint(n - 1)
for q in p_factors:
if pow(a, (n - 1)//q, n) == 1:
break
else:
return True
return False