bitcoin-hs-0.0.1: Partial implementation of the Bitcoin protocol (as of 2013)

Bitcoin.Crypto.FiniteField.Naive.Fp

Description

The finite field Fp of p elements, where p is the prime parameter of the elliptic curve secp256k1.

Naive implementation.

Synopsis

Operations in the finite field Fp (p being the secp256k1 curve's p)

helper function: Modulo p

Negation in Fp

Multiplication in Fp

Square in Fp

Division in Fp

Multiplicative inverse in Fp

Inverse using the power function (slower)

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.

Inverse using the binary Euclidean algorithm (faster)

(Fast) exponentiation in Fp

square root in Fp

(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)

http://course1.winona.edu/eerrthum/13Spring/SquareRoots.pdf

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.

newtype Fp Source #

For simpler (and safer) code, we introduce a newtype for elements of Fp

Constructors

 Fp FieldsunFp :: Integer

Instances

 Source # Methods(==) :: Fp -> Fp -> Bool #(/=) :: Fp -> Fp -> Bool # Source # Methods(/) :: Fp -> Fp -> Fp #recip :: Fp -> Fp # Source # Methods(+) :: Fp -> Fp -> Fp #(-) :: Fp -> Fp -> Fp #(*) :: Fp -> Fp -> Fp #negate :: Fp -> Fp #abs :: Fp -> Fp #signum :: Fp -> Fp # Source # MethodsshowsPrec :: Int -> Fp -> ShowS #show :: Fp -> String #showList :: [Fp] -> ShowS #

Note that this gives only one of the possibly two square roots