跳转至

勒让德符号

 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
#determine if a is a prime number
def isPrime(a):
    return all(a % i for i in range(2, a))

#factorize n
def factorize(n):
    factors = []
    p = 2
    while True:
        while(n % p == 0 and n > 0): #while n can be divided by smaller number, do so
            factors.append(p)
            n = n // p
        p += 1  #p is not necessary prime, but n%p == 0 only for prime numbers
        if p > n // p:
            break
    if n > 1:
        factors.append(n)
    return factors

#calculate the Legendre symbol (a / p)
def calculateLegendre(a, p):
    if a >= p or a < 0:
        return calculateLegendre(a % p, p)
    elif a == 0 or a == 1:
        return a
    elif a == 2:
        if p%8 == 1 or p%8 == 7:
            return 1
        else:
            return -1
    elif a == p-1:
        if p%4 == 1:
            return 1
        else:
            return -1
    elif not isPrime(a):
        factors = factorize(a)
        product = 1
        for pi in factors:
            product *= calculateLegendre(pi, p)
        return product
    else:
        if ((p-1)/2)%2==0 or ((a-1)/2)%2==0:
            return calculateLegendre(p, a)
        else:
            return (-1)*calculateLegendre(p, a)

print("Calculate the legendre symbol (n / p) with p is prime.")
print("Please enter for n:")
n = eval(input())
print("Please enter for p:")
p = eval(input())
if not isPrime(p):
    print("The legendre symbol does not exist!")
else:
    result = calculateLegendre(n, p)
    print("The result of (%d / %d) is %d" %(n, p, result))

"""test examples:
   (3 / 29) = -1
   (111, 41) = -1
   (113, 41) = 1
   (2, 31) = 1
   (-5, 31) = -1
   (15, 3) = 0
   (12345, 331) = -1
"""