Expose two GMP primality operations
authorHerbert Valerio Riedel <hvr@gnu.org>
Mon, 28 Oct 2013 19:13:35 +0000 (20:13 +0100)
committerHerbert Valerio Riedel <hvr@gnu.org>
Mon, 28 Oct 2013 20:19:05 +0000 (21:19 +0100)
This exposes `mpz_probab_prime_p()` and `mpz_nextprime()` as
`testPrimeInteger` and `nextPrimeInteger` respectively and is especially
useful for cryptographic algorithms such as RSA.

Signed-off-by: Herbert Valerio Riedel <hvr@gnu.org>
GHC/Integer/GMP/Internals.hs
GHC/Integer/GMP/Prim.hs
GHC/Integer/Type.lhs
cbits/gmp-wrappers.cmm

index f1aec51..127122d 100644 (file)
@@ -1,6 +1,6 @@
 {-# LANGUAGE NoImplicitPrelude #-}
 
-module GHC.Integer.GMP.Internals (Integer(..), gcdInt, gcdInteger, gcdExtInteger, lcmInteger, powInteger, powModInteger, powModSecInteger, recipModInteger)
+module GHC.Integer.GMP.Internals (Integer(..), gcdInt, gcdInteger, gcdExtInteger, lcmInteger, powInteger, powModInteger, powModSecInteger, recipModInteger, nextPrimeInteger, testPrimeInteger)
     where
 
 import GHC.Integer.Type
index 0fd1b32..beb812c 100644 (file)
@@ -46,6 +46,9 @@ module GHC.Integer.GMP.Prim (
     powModSecInteger#,
     recipModInteger#,
 
+    nextPrimeInteger#,
+    testPrimeInteger#,
+
 #if WORD_SIZE_IN_BITS < 64
     int64ToInteger#,  integerToInt64#,
     word64ToInteger#, integerToWord64#,
@@ -209,6 +212,16 @@ foreign import prim "integer_cmm_recipModIntegerzh" recipModInteger#
 
 -- |
 --
+foreign import prim "integer_cmm_nextPrimeIntegerzh" nextPrimeInteger#
+  :: Int# -> ByteArray# -> (# Int#, ByteArray# #)
+
+-- |
+--
+foreign import prim "integer_cmm_testPrimeIntegerzh" testPrimeInteger#
+  :: Int# -> ByteArray# -> Int# -> Int#
+
+-- |
+--
 foreign import prim "integer_cmm_complementIntegerzh" complementInteger#
   :: Int# -> ByteArray# -> (# Int#, ByteArray# #)
 
index 5ff79ab..a44d299 100644 (file)
@@ -46,6 +46,7 @@ import GHC.Integer.GMP.Prim (
     andInteger#, orInteger#, xorInteger#, complementInteger#,
     testBitInteger#, mul2ExpInteger#, fdivQ2ExpInteger#,
     powInteger#, powModInteger#, powModSecInteger#, recipModInteger#,
+    nextPrimeInteger#, testPrimeInteger#,
 #if WORD_SIZE_IN_BITS < 64
     int64ToInteger#,  integerToInt64#,
     word64ToInteger#, integerToWord64#,
@@ -644,8 +645,38 @@ recipModInteger j@(S# _) m@(J# _ _) = recipModInteger (toBig j) m
 recipModInteger j@(J# _ _) m@(S# _) = recipModInteger j (toBig m)
 recipModInteger (J# s d) (J# ms md) = case recipModInteger# s d ms md of
                            (# s', d' #) -> J# s' d'
-\end{code}
 
+-- | Probalistic Miller-Rabin primality test.
+--
+-- @testPrimeInteger n k@ determines whether @n@ is prime and
+-- returns one of the following results:
+--
+-- * @2#@ is returned if @n@ is definitely prime,
+--
+-- * @1#@ if @n@ is a /probable prime/, or
+--
+-- * @0#@ if @n@ is definitely not a prime.
+--
+-- The @k@ argument controls how many test rounds are performed for
+-- determining a /probable prime/. For more details, see
+-- <http://gmplib.org/manual/Number-Theoretic-Functions.html#index-mpz_005fprobab_005fprime_005fp-360 GMP documentation for `mpz_probab_prime_p()`>.
+{-# NOINLINE testPrimeInteger #-}
+testPrimeInteger :: Integer -> Int# -> Int#
+testPrimeInteger j@(S# _) reps = testPrimeInteger (toBig j) reps
+testPrimeInteger (J# s d) reps = testPrimeInteger# s d reps
+
+-- | Compute next prime greater than @n@ probalistically.
+--
+-- According to the GMP documentation, the underlying function
+-- @mpz_nextprime()@ \"uses a probabilistic algorithm to identify
+-- primes. For practical purposes it's adequate, the chance of a
+-- composite passing will be extremely small.\"
+{-# NOINLINE nextPrimeInteger #-}
+nextPrimeInteger :: Integer -> Integer
+nextPrimeInteger j@(S# _) = nextPrimeInteger (toBig j)
+nextPrimeInteger (J# s d) = case nextPrimeInteger# s d of (# s', d' #) -> J# s' d'
+
+\end{code}
 
 %*********************************************************
 %*                                                      *
index aadd134..4db684d 100644 (file)
@@ -54,6 +54,8 @@ import "integer-gmp" __gmpz_pow_ui;
 import "integer-gmp" __gmpz_powm;
 import "integer-gmp" __gmpz_powm_sec;
 import "integer-gmp" __gmpz_invert;
+import "integer-gmp" __gmpz_nextprime;
+import "integer-gmp" __gmpz_probab_prime_p;
 
 import "integer-gmp" integer_cbits_decodeDouble;
 
@@ -323,8 +325,32 @@ again:                                                          \
          MP_INT__mp_d(mp_result) - SIZEOF_StgArrWords);         \
 }
 
+#define GMP_TAKE1_I1_RETI1(name,mp_fun)                         \
+name (W_ ws1, P_ d1, W_ wi)                                     \
+{                                                               \
+  CInt s1, res, i;                                              \
+  W_ mp_tmp;                                                    \
+                                                                \
+again:                                                          \
+  STK_CHK_GEN_N (SIZEOF_MP_INT);                                \
+  MAYBE_GC(again);                                              \
+                                                                \
+  s1 = W_TO_INT(ws1);                                           \
+  i  = W_TO_INT(wi);                                            \
+                                                                \
+  mp_tmp     = Sp - 1 * SIZEOF_MP_INT;                          \
+  MP_INT__mp_alloc(mp_tmp) = W_TO_INT(BYTE_ARR_WDS(d1));        \
+  MP_INT__mp_size(mp_tmp)  = (s1);                              \
+  MP_INT__mp_d(mp_tmp)     = BYTE_ARR_CTS(d1);                  \
+                                                                \
+  /* Perform the operation */                                   \
+  (res) = ccall mp_fun(mp_tmp "ptr", i);                        \
+                                                                \
+  return (TO_W_(res));                                          \
+}
+
 #define GMP_TAKE1_UL1_RETI1(name,mp_fun)                        \
-name (W_ ws1, P_ d1, W_ wul)                                     \
+name (W_ ws1, P_ d1, W_ wul)                                    \
 {                                                               \
   CInt s1, res;                                                 \
   CLong ul;                                                     \
@@ -442,6 +468,9 @@ GMP_TAKE3_RET1(integer_cmm_powModSecIntegerzh,      __gmpz_powm_sec)
 GMP_TAKE2_RET1(integer_cmm_recipModIntegerzh,       __gmpz_invert)
 GMP_TAKE1_UL1_RET1(integer_cmm_powIntegerzh,        __gmpz_pow_ui)
 
+GMP_TAKE1_RET1(integer_cmm_nextPrimeIntegerzh,      __gmpz_nextprime)
+GMP_TAKE1_I1_RETI1(integer_cmm_testPrimeIntegerzh,  __gmpz_probab_prime_p)
+
 integer_cmm_gcdIntzh (W_ int1, W_ int2)
 {
     W_ r;