Compute the Jacobi symbol of n modulo k See https://en.wikipedia.org/wiki/Jacobi_symbol For our application k is always prime, so this is the same as the Legendre symbol.
(n, k)
| 22 | return hashlib.sha256(ss).digest() |
| 23 | |
| 24 | def jacobi_symbol(n, k): |
| 25 | """Compute the Jacobi symbol of n modulo k |
| 26 | |
| 27 | See https://en.wikipedia.org/wiki/Jacobi_symbol |
| 28 | |
| 29 | For our application k is always prime, so this is the same as the Legendre symbol.""" |
| 30 | assert k > 0 and k & 1, "jacobi symbol is only defined for positive odd k" |
| 31 | n %= k |
| 32 | t = 0 |
| 33 | while n != 0: |
| 34 | while n & 1 == 0: |
| 35 | n >>= 1 |
| 36 | r = k & 7 |
| 37 | t ^= (r == 3 or r == 5) |
| 38 | n, k = k, n |
| 39 | t ^= (n & k & 3 == 3) |
| 40 | n = n % k |
| 41 | if k == 1: |
| 42 | return -1 if t else 1 |
| 43 | return 0 |
| 44 | |
| 45 | def modsqrt(a, p): |
| 46 | """Compute the square root of a modulo p when p % 4 = 3. |