Compute the square root of a modulo p when p % 4 = 3. The Tonelli-Shanks algorithm can be used. See https://en.wikipedia.org/wiki/Tonelli-Shanks_algorithm Limiting this function to only work for p % 4 = 3 means we don't need to iterate through the loop. The highest n such that p - 1 =
(a, p)
| 43 | return 0 |
| 44 | |
| 45 | def modsqrt(a, p): |
| 46 | """Compute the square root of a modulo p when p % 4 = 3. |
| 47 | |
| 48 | The Tonelli-Shanks algorithm can be used. See https://en.wikipedia.org/wiki/Tonelli-Shanks_algorithm |
| 49 | |
| 50 | Limiting this function to only work for p % 4 = 3 means we don't need to |
| 51 | iterate through the loop. The highest n such that p - 1 = 2^n Q with Q odd |
| 52 | is n = 1. Therefore Q = (p-1)/2 and sqrt = a^((Q+1)/2) = a^((p+1)/4) |
| 53 | |
| 54 | secp256k1's is defined over field of size 2**256 - 2**32 - 977, which is 3 mod 4. |
| 55 | """ |
| 56 | if p % 4 != 3: |
| 57 | raise NotImplementedError("modsqrt only implemented for p % 4 = 3") |
| 58 | sqrt = pow(a, (p + 1)//4, p) |
| 59 | if pow(sqrt, 2, p) == a % p: |
| 60 | return sqrt |
| 61 | return None |
| 62 | |
| 63 | class EllipticCurve: |
| 64 | def __init__(self, p, a, b): |