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

Safe HaskellSafe
LanguageHaskell98

Bitcoin.Crypto.FiniteField.Naive.Fp

Contents

Description

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

Naive implementation.

Synopsis

Documentation

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

modp :: Integer -> Integer Source #

helper function: Modulo p

negFp :: Integer -> Integer Source #

Negation in Fp

mulFp :: Integer -> Integer -> Integer Source #

Multiplication in Fp

sqrFp :: Integer -> Integer Source #

Square in Fp

divFp :: Integer -> Integer -> Integer Source #

Division in Fp

invFp :: Integer -> Integer Source #

Multiplicative inverse in Fp

invFp_pow :: Integer -> Integer Source #

Inverse using the power function (slower)

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)

powFp :: Integer -> Integer -> Integer Source #

(Fast) exponentiation in Fp

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)

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

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.

newtype Fp Source #

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

Constructors

Fp 

Fields

Instances

Eq Fp Source # 

Methods

(==) :: Fp -> Fp -> Bool #

(/=) :: Fp -> Fp -> Bool #

Fractional Fp Source # 

Methods

(/) :: Fp -> Fp -> Fp #

recip :: Fp -> Fp #

fromRational :: Rational -> Fp #

Num Fp Source # 

Methods

(+) :: Fp -> Fp -> Fp #

(-) :: Fp -> Fp -> Fp #

(*) :: Fp -> Fp -> Fp #

negate :: Fp -> Fp #

abs :: Fp -> Fp #

signum :: Fp -> Fp #

fromInteger :: Integer -> Fp #

Show Fp Source # 

Methods

showsPrec :: Int -> Fp -> ShowS #

show :: Fp -> String #

showList :: [Fp] -> ShowS #

sqrt_p :: Fp -> Maybe Fp Source #

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