-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Integer library based on GMP
--   
--   This package contains an Integer library based on GMP.
@package integer-gmp


-- | This modules provides access to the <a>Integer</a> constructors and
--   exposes some highly optimized GMP-operations.
module GHC.Integer.GMP.Internals

-- | Arbitrary-precision integers.
data Integer
S# :: Int# -> Integer
J# :: Int# -> ByteArray# -> Integer

-- | Compute greatest common divisor.
gcdInt :: Int# -> Int# -> Int#

-- | Compute greatest common divisor.
gcdInteger :: Integer -> Integer -> Integer

-- | Extended euclidean algorithm.
--   
--   For <tt><i>a</i></tt> and <tt><i>b</i></tt>, compute their greatest
--   common divisor <tt><i>g</i></tt> and the coefficient <tt><i>s</i></tt>
--   satisfying <tt><i>a</i><i>s</i> + <i>b</i><i>t</i> = <i>g</i></tt>.
gcdExtInteger :: Integer -> Integer -> (# Integer, Integer #)

-- | Compute least common multiple.
lcmInteger :: Integer -> Integer -> Integer

-- | Compute next prime greater than <tt><i>n</i></tt> probalistically.
--   
--   According to the GMP documentation, the underlying function
--   <tt>mpz_nextprime()</tt> "uses a probabilistic algorithm to identify
--   primes. For practical purposes it's adequate, the chance of a
--   composite passing will be extremely small."
nextPrimeInteger :: Integer -> Integer

-- | Probalistic Miller-Rabin primality test.
--   
--   "<tt><a>testPrimeInteger</a> <i>n</i> <i>k</i></tt>" determines
--   whether <tt><i>n</i></tt> is prime and returns one of the following
--   results:
--   
--   <ul>
--   <li><tt>2#</tt> is returned if <tt><i>n</i></tt> is definitely
--   prime,</li>
--   <li><tt>1#</tt> if <tt><i>n</i></tt> is a <i>probable prime</i>,
--   or</li>
--   <li><tt>0#</tt> if <tt><i>n</i></tt> is definitely not a prime.</li>
--   </ul>
--   
--   The <tt><i>k</i></tt> argument controls how many test rounds are
--   performed for determining a <i>probable prime</i>. For more details,
--   see <a>GMP documentation for `mpz_probab_prime_p()`</a>.
testPrimeInteger :: Integer -> Int# -> Int#

-- | "<tt><a>powInteger</a> <i>b</i> <i>e</i></tt>" computes base
--   <tt><i>b</i></tt> raised to exponent <tt><i>e</i></tt>.
powInteger :: Integer -> Word# -> Integer

-- | "<tt><a>powModInteger</a> <i>b</i> <i>e</i> <i>m</i></tt>" computes
--   base <tt><i>b</i></tt> raised to exponent <tt><i>e</i></tt> modulo
--   <tt><i>m</i></tt>.
--   
--   Negative exponents are supported if an inverse modulo
--   <tt><i>m</i></tt> exists. It's advised to avoid calling this primitive
--   with negative exponents unless it is guaranteed the inverse exists, as
--   failure to do so will likely cause program abortion due to a
--   divide-by-zero fault. See also <a>recipModInteger</a>.
powModInteger :: Integer -> Integer -> Integer -> Integer

-- | "<tt><a>powModSecInteger</a> <i>b</i> <i>e</i> <i>m</i></tt>" computes
--   base <tt><i>b</i></tt> raised to exponent <tt><i>e</i></tt> modulo
--   <tt><i>m</i></tt>. It is required that <tt><i>e</i> &gt; 0</tt> and
--   <tt><i>m</i></tt> is odd.
--   
--   This is a "secure" variant of <a>powModInteger</a> using the
--   <tt>mpz_powm_sec()</tt> function which is designed to be resilient to
--   side channel attacks and is therefore intended for cryptographic
--   applications.
powModSecInteger :: Integer -> Integer -> Integer -> Integer

-- | "<tt><a>recipModInteger</a> <i>x</i> <i>m</i></tt>" computes the
--   inverse of <tt><i>x</i></tt> modulo <tt><i>m</i></tt>. If the inverse
--   exists, the return value <tt><i>y</i></tt> will satisfy <tt>0 &lt;
--   <i>y</i> &lt; abs(<i>m</i>)</tt>, otherwise the result is <tt>0</tt>.
--   
--   Note: The implementation exploits the undocumented property of
--   <tt>mpz_invert()</tt> to not mangle the result operand (which is
--   initialized to 0) in case of non-existence of the inverse.
recipModInteger :: Integer -> Integer -> Integer

-- | Compute number of digits (without sign) in given <tt><i>base</i></tt>.
--   
--   It's recommended to avoid calling <a>sizeInBaseInteger</a> for small
--   integers as this function would currently convert those to big
--   integers in order to call <tt>mpz_sizeinbase()</tt>.
--   
--   This function wraps <tt>mpz_sizeinbase()</tt> which has some
--   implementation pecularities to take into account:
--   
--   <ul>
--   <li>"<tt><a>sizeInBaseInteger</a> 0 <i>base</i> = 1</tt>" (see also
--   comment in <a>exportIntegerToMutableByteArray</a>).</li>
--   <li>This function is only defined if <tt><i>base</i> &gt;= 2#</tt> and
--   <tt><i>base</i> &lt;= 256#</tt> (Note: the documentation claims that
--   only <tt><i>base</i> &lt;= 62#</tt> is supported, however the actual
--   implementation supports up to base 256).</li>
--   <li>If <tt><i>base</i></tt> is a power of 2, the result will be exact.
--   In other cases (e.g. for <tt><i>base</i> = 10#</tt>), the result
--   <i>may</i> be 1 digit too large sometimes.</li>
--   <li>"<tt><a>sizeInBaseInteger</a> <i>i</i> 2#</tt>" can be used to
--   determine the most significant bit of <tt><i>i</i></tt>.</li>
--   </ul>
sizeInBaseInteger :: Integer -> Int# -> Word#

-- | Read <a>Integer</a> (without sign) from byte-array in base-256
--   representation.
--   
--   The call
--   
--   <pre>
--   <a>importIntegerFromByteArray</a> <i>ba</i> <i>offset</i> <i>size</i> <i>order</i>
--   
--   </pre>
--   
--   reads
--   
--   <ul>
--   <li><tt><i>size</i></tt> bytes from the <a>ByteArray#</a>
--   <tt><i>ba</i></tt> starting at <tt><i>offset</i></tt></li>
--   <li>with most significant byte first if <tt><i>order</i></tt> is
--   <tt>1#</tt> or least significant byte first if <tt><i>order</i></tt>
--   is <tt>-1#</tt>, and</li>
--   <li>returns a new <a>Integer</a></li>
--   </ul>
importIntegerFromByteArray :: ByteArray# -> Word# -> Word# -> Int# -> Integer

-- | Read <a>Integer</a> (without sign) from memory location at
--   <tt><i>addr</i></tt> in base-256 representation.
--   
--   <pre>
--   <a>importIntegerFromAddr</a> <i>addr</i> <i>size</i> <i>order</i>
--   
--   </pre>
--   
--   See description of <a>importIntegerFromByteArray</a> for more details.
importIntegerFromAddr :: Addr# -> Word# -> Int# -> State# s -> (# State# s, Integer #)

-- | Dump <a>Integer</a> (without sign) to mutable byte-array in base-256
--   representation.
--   
--   The call
--   
--   <pre>
--   <a>exportIntegerToMutableByteArray</a> <i>i</i> <i>mba</i> <i>offset</i> <i>order</i>
--   
--   </pre>
--   
--   writes
--   
--   <ul>
--   <li>the <a>Integer</a> <tt><i>i</i></tt></li>
--   <li>into the <a>MutableByteArray#</a> <tt><i>mba</i></tt> starting at
--   <tt><i>offset</i></tt></li>
--   <li>with most significant byte first if <tt>order</tt> is <tt>1#</tt>
--   or least significant byte first if <tt>order</tt> is <tt>-1#</tt>,
--   and</li>
--   <li>returns number of bytes written.</li>
--   </ul>
--   
--   Use "<tt><a>sizeInBaseInteger</a> <i>i</i> 256#</tt>" to compute the
--   exact number of bytes written in advance for <tt><i>i</i> /= 0</tt>.
--   In case of <tt><i>i</i> == 0</tt>,
--   <a>exportIntegerToMutableByteArray</a> will write and report zero
--   bytes written, whereas <a>sizeInBaseInteger</a> report one byte.
--   
--   It's recommended to avoid calling
--   <a>exportIntegerToMutableByteArray</a> for small integers as this
--   function would currently convert those to big integers in order to
--   call <tt>mpz_export()</tt>.
exportIntegerToMutableByteArray :: Integer -> MutableByteArray# s -> Word# -> Int# -> State# s -> (# State# s, Word# #)

-- | Dump <a>Integer</a> (without sign) to <tt><i>addr</i></tt> in base-256
--   representation.
--   
--   <pre>
--   <a>exportIntegerToAddr</a> <i>addr</i> <i>o</i> <i>e</i>
--   
--   </pre>
--   
--   See description of <a>exportIntegerToMutableByteArray</a> for more
--   details.
exportIntegerToAddr :: Integer -> Addr# -> Int# -> State# s -> (# State# s, Word# #)

module GHC.Integer.Logarithms

-- | Calculate the integer logarithm for an arbitrary base. The base must
--   be greater than 1, the second argument, the number whose logarithm is
--   sought, should be positive, otherwise the result is meaningless.
--   
--   <pre>
--   base ^ integerLogBase# base m &lt;= m &lt; base ^ (integerLogBase# base m + 1)
--   </pre>
--   
--   for <tt>base &gt; 1</tt> and <tt>m &gt; 0</tt>.
integerLogBase# :: Integer -> Integer -> Int#

-- | Calculate the integer base 2 logarithm of an <a>Integer</a>. The
--   calculation is more efficient than for the general case, on platforms
--   with 32- or 64-bit words much more efficient.
--   
--   The argument must be strictly positive, that condition is <i>not</i>
--   checked.
integerLog2# :: Integer -> Int#

-- | This function calculates the integer base 2 logarithm of a
--   <a>Word#</a>.
wordLog2# :: Word# -> Int#
