Safe Haskell | Safe |
---|---|
Language | Haskell98 |
The finite field Fp of p elements, where p is the prime parameter of the elliptic curve secp256k1.
Naive implementation.
- secp256k1_p :: Integer
- modp :: Integer -> Integer
- addFp :: Integer -> Integer -> Integer
- subFp :: Integer -> Integer -> Integer
- negFp :: Integer -> Integer
- mulFp :: Integer -> Integer -> Integer
- sqrFp :: Integer -> Integer
- divFp :: Integer -> Integer -> Integer
- invFp :: Integer -> Integer
- invFp_pow :: Integer -> Integer
- invFp_pow_spec :: Fp -> Fp
- invFp_euclid :: Integer -> Integer
- powFp :: Integer -> Integer -> Integer
- secp256k1_ndiv4 :: Integer
- secp256k1_ndiv4p1 :: Integer
- unsafeSqrtFp :: Integer -> Integer
- sqrtFp :: Integer -> Maybe Integer
- newtype Fp = Fp {}
- toFp :: Integer -> Fp
- fromFp :: Fp -> Integer
- sqrt_p :: Fp -> Maybe Fp
- pow_p :: Fp -> Integer -> Fp
Documentation
Operations in the finite field Fp (p being the secp256k1 curve's p)
invFp_pow_spec :: Fp -> Fp Source #
Inverse using a specialized power function (should about 2x faster than invFp_pow
)
This uses the fact that
p-2 == 45 + 1024 * (1023 + 1024 * (1023 + 1024 * (1019 + 1024 * ( ... * 63 ) ) )
Since on the exponential level, both doubling and multiplying has the same cost,
additions and doubling in this type of representation of p-2
has the same cost.
And because in p-2
almost all bits are set, the standard binary power function
is very far from being optimal.
Total number of operations is
16 + (21+1+2+1)*(10+1) = 291
instead of almost 512
.
invFp_euclid :: Integer -> Integer Source #
Inverse using the binary Euclidean algorithm (faster)
square root in Fp
unsafeSqrtFp :: Integer -> Integer Source #
(One of the) square roots mod p (if any exists). Since p is a prime and p = 4k+3
,
we have a fortunately a very easy solution by some quadratic reciprocity stuff I don't
remember how exactly works
(but it's elementary number theory)
sqrtFp :: Integer -> Maybe Integer Source #
Note that square roots do not always exist in Fp: consider for example p=7, then 3, 5 and 6 do not have square roots, while the rest has two (except 0).
In general, if x is a square root then so is (p-x), since
(p-x)*(p-x) = p*p - p*(2*x) + x*x = x*x (mod p)
And that should be all solutions, since it's a quadratic equation.
For simpler (and safer) code, we introduce a newtype for elements of Fp