-
Notifications
You must be signed in to change notification settings - Fork 0
/
pseudocode.pc
34 lines (31 loc) · 756 Bytes
/
pseudocode.pc
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
const k, n, b, c; # they have to have values
const N = k * b ^ n - 1;
# find V1
# this uses Jacobi Symbols
while (v1 := 1) : () : (v1 += 1) {
if jacobi(v1 - 2, N) == 1 && jacobi(v1 + 2, N) == -1 {
break
}
}
# fastest method [ O(log(bitlen(k))) ] to find u0
# this calculates the value of the Lucas Sequence
x = v1
y = (v1 * v1) - 2
k_bitlen = bitlen(k)
while (i := k_bitlen - 2) : (i > 0) : (i -= 1) {
if k.bits[i] == 1 {
x = (x*y) - v1 mod N
y = (y*y) - 2 mod N
} else {
y = (x*y) - v1 mod N
x = (x*x) - 2 mod N
}
}
x = x * x
x = x - v1
u = u0 = x mod N
# Lucas-Lehmer-Riesel primality test starting from U0
while (i := 1) : (i < n - 1) : (i += 1) {
u = (u * u) - 2
}
'prime!' if u == 0