Python/maths/solovay_strassen_primality_test.py at master · TheAlgorithms/Python · GitHub

Name: Python/maths/solovay_strassen_primality_test.py at master · TheAlgorithms/Python · GitHub
Rating: 4.8 (7164 reviews)
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
"""
This script implements the Solovay-Strassen Primality test.

This probabilistic primality test is based on Euler's criterion. It is similar
to the Fermat test but uses quadratic residues. It can quickly identify
composite numbers but may occasionally classify composite numbers as prime.

More details and concepts about this can be found on:
https://en.wikipedia.org/wiki/Solovay%E2%80%93Strassen_primality_test
"""

importrandom


defjacobi_symbol(random_a: int, number: int) ->int:
"""
 Calculate the Jacobi symbol. The Jacobi symbol is a generalization
 of the Legendre symbol, which can be used to simplify computations involving
 quadratic residues. The Jacobi symbol is used in primality tests, like the
 Solovay-Strassen test, because it helps determine if an integer is a
 quadratic residue modulo a given modulus, providing valuable information
 about the number's potential primality or compositeness.

 Parameters:
 random_a: A randomly chosen integer from 2 to n-2 (inclusive)
 number: The number that is tested for primality

 Returns:
 jacobi_symbol: The Jacobi symbol is a mathematical function
 used to determine whether an integer is a quadratic residue modulo
 another integer (usually prime) or not.

 >>> jacobi_symbol(2, 13)
 -1
 >>> jacobi_symbol(5, 19)
 1
 >>> jacobi_symbol(7, 14)
 0
 """

ifrandom_ain (0, 1):
returnrandom_a

random_a%=number
t=1

whilerandom_a!=0:
whilerandom_a%2==0:
random_a//=2
r=number%8
ifrin (3, 5):
t=-t

random_a, number=number, random_a

ifrandom_a%4==number%4==3:
t=-t

random_a%=number

returntifnumber==1else0


defsolovay_strassen(number: int, iterations: int) ->bool:
"""
 Check whether the input number is prime or not using
 the Solovay-Strassen Primality test

 Parameters:
 number: The number that is tested for primality
 iterations: The number of times that the test is run
 which effects the accuracy

 Returns:
 result: True if number is probably prime and false
 if not

 >>> random.seed(10)
 >>> solovay_strassen(13, 5)
 True
 >>> solovay_strassen(9, 10)
 False
 >>> solovay_strassen(17, 15)
 True
 """

ifnumber<=1:
returnFalse
ifnumber<=3:
returnTrue

for_inrange(iterations):
a=random.randint(2, number-2)
x=jacobi_symbol(a, number)
y=pow(a, (number-1) //2, number)

ifx==0ory!=x%number:
returnFalse

returnTrue


if__name__=="__main__":
importdoctest

doctest.testmod()