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

Bitcoin.Crypto.FiniteField.Fast.Fp

Contents

Description

Finite field of order p, where p is the prime parameter of the secp256k1 elliptic curve. Relatively fast arithmetic (written in C)

Should work on both little-endian and big-endian architectures, but only tested on little-endian.

Synopsis

Documentation

newtype Fp Source #

Constructors

 Fp FieldsunFp :: Word256

Instances

 Source # Methods 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 #

Converts to a little-endian bytestring

Converts to a big-endian bytestring

Converts to a little-endian sequence of bytes

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

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.