rndsort{Miller, Rabin} primality test.

[openssl.git] / crypto / bn / bn.h

diff --git a/crypto/bn/bn.h b/crypto/bn/bn.h
index 9c92d76b4121c97ce7576818df045f19a9a9fc64..299873819347713e401e1c50aa1f95e7a60c777e 100644 (file)
--- a/crypto/bn/bn.h
+++ b/crypto/bn/bn.h
@@ -286,6 +286,25 @@ typedef struct bn_recp_ctx_st
 #define BN_prime_checks 0 /* default: select number of iterations
                             based on the size of the number */
 
+
+/* number of Miller-Rabin iterations for an error rate  of less than 2^-80
+ * for random 'b'-bit input, b >= 100 (taken from table 4.4 in the Handbook
+ * of Applied Cryptography [Menezes, van Oorschot, Vanstone; CRC Press 1996];
+ * original paper: Damgaard, Landrock, Pomerance: Average case error estimates
+ * for the strong probable prime test. -- Math. Comp. 61 (1993) 177-194) */
+#define BN_prime_checks_for_size(b) ((b) >= 1300 ?  2 : \
+                                (b) >=  850 ?  3 : \
+                                (b) >=  650 ?  4 : \
+                                (b) >=  550 ?  5 : \
+                                (b) >=  450 ?  6 : \
+                                (b) >=  400 ?  7 : \
+                                (b) >=  350 ?  8 : \
+                                (b) >=  300 ?  9 : \
+                                (b) >=  250 ? 12 : \
+                                (b) >=  200 ? 15 : \
+                                (b) >=  150 ? 18 : \
+                                /* b >= 100 */ 27)
+
 #define BN_num_bytes(a)        ((BN_num_bits(a)+7)/8)
 #define BN_is_word(a,w)        (((a)->top == 1) && ((a)->d[0] == (BN_ULONG)(w)))
 #define BN_is_zero(a)  (((a)->top == 0) || BN_is_word(a,0))
@@ -317,6 +336,7 @@ BN_CTX *BN_CTX_new(void);
 void   BN_CTX_init(BN_CTX *c);
 void   BN_CTX_free(BN_CTX *c);
 int     BN_rand(BIGNUM *rnd, int bits, int top,int bottom);
+int     BN_pseudo_rand(BIGNUM *rnd, int bits, int top,int bottom);
 int    BN_num_bits(const BIGNUM *a);
 int    BN_num_bits_word(BN_ULONG);
 BIGNUM *BN_new(void);
@@ -386,6 +406,9 @@ BIGNUM *BN_generate_prime(BIGNUM *ret,int bits,int safe,BIGNUM *add,
                BIGNUM *rem,void (*callback)(int,int,void *),void *cb_arg);
 int    BN_is_prime(BIGNUM *p,int nchecks,void (*callback)(int,int,void *),
                BN_CTX *ctx,void *cb_arg);
+int    BN_is_prime_fasttest(BIGNUM *p,int nchecks,
+               void (*callback)(int,int,void *),BN_CTX *ctx,void *cb_arg,
+               int do_trial_division);
 void   ERR_load_BN_strings(void );
 
 BN_ULONG bn_mul_add_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w);