rndsort{Miller, Rabin} primality test.

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

diff --git a/crypto/bn/bn.h b/crypto/bn/bn.h
index 80421a24ccda37cf5db8210611ad6d35119ddca0..299873819347713e401e1c50aa1f95e7a60c777e 100644 (file)
--- a/crypto/bn/bn.h
+++ b/crypto/bn/bn.h
@@ -142,7 +142,7 @@ extern "C" {
 #endif
 
 #ifdef THIRTY_TWO_BIT
-#ifdef WIN32
+#if defined(WIN32) && !defined(__GNUC__)
 #define BN_ULLONG      unsigned _int64
 #else
 #define BN_ULLONG      unsigned long long
@@ -257,16 +257,16 @@ typedef struct bn_blinding_st
 
 /* Used for montgomery multiplication */
 typedef struct bn_mont_ctx_st
-        {
-       int use_word;   /* 0 for word form, 1 for long form */
-        int ri;         /* number of bits in R */
-        BIGNUM RR;     /* used to convert to montgomery form */
-        BIGNUM N;      /* The modulus */
-        BIGNUM Ni;     /* The inverse of N */
-       BN_ULONG n0;    /* word form of inverse, normally only one of
-                        * Ni or n0 is defined */
+       {
+       int use_word;  /* 0 for word form, 1 for bignum form */
+       int ri;        /* number of bits in R */
+       BIGNUM RR;     /* used to convert to montgomery form */
+       BIGNUM N;      /* The modulus */
+       BIGNUM Ni;     /* R*(1/R mod N) - N*Ni = 1
+                       * (Ni is only stored for bignum algorithm) */
+       BN_ULONG n0;   /* least significant word of Ni */
        int flags;
-        } BN_MONT_CTX;
+       } BN_MONT_CTX;
 
 /* Used for reciprocal division/mod functions
  * It cannot be shared between threads
@@ -283,7 +283,27 @@ typedef struct bn_recp_ctx_st
 #define BN_to_montgomery(r,a,mont,ctx) BN_mod_mul_montgomery(\
        r,a,&((mont)->RR),(mont),ctx)
 
-#define BN_prime_checks                (5)
+#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)))
@@ -316,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);
@@ -329,11 +350,11 @@ int       BN_bn2mpi(const BIGNUM *a, unsigned char *to);
 int    BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b);
 int    BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b);
 int    BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b);
-int    BN_add(BIGNUM *r, BIGNUM *a, BIGNUM *b);
+int    BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b);
 int    BN_mod(BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx);
 int    BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d,
               BN_CTX *ctx);
-int    BN_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b,BN_CTX *ctx);
+int    BN_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_CTX *ctx);
 int    BN_sqr(BIGNUM *r, BIGNUM *a,BN_CTX *ctx);
 BN_ULONG BN_mod_word(BIGNUM *a, BN_ULONG w);
 BN_ULONG BN_div_word(BIGNUM *a, BN_ULONG w);
@@ -359,7 +380,7 @@ int BN_mod_exp_simple(BIGNUM *r, BIGNUM *a, BIGNUM *p,
 int    BN_mask_bits(BIGNUM *a,int n);
 int    BN_mod_mul(BIGNUM *ret, BIGNUM *a, BIGNUM *b, const BIGNUM *m, BN_CTX *ctx);
 #ifndef WIN16
-int    BN_print_fp(FILE *fp, BIGNUM *a);
+int    BN_print_fp(FILE *fp, const BIGNUM *a);
 #endif
 #ifdef HEADER_BIO_H
 int    BN_print(BIO *fp, const BIGNUM *a);
@@ -381,10 +402,13 @@ int       BN_hex2bn(BIGNUM **a, const char *str);
 int    BN_dec2bn(BIGNUM **a, const char *str);
 int    BN_gcd(BIGNUM *r,BIGNUM *in_a,BIGNUM *in_b,BN_CTX *ctx);
 BIGNUM *BN_mod_inverse(BIGNUM *ret,BIGNUM *a, const BIGNUM *n,BN_CTX *ctx);
-BIGNUM *BN_generate_prime(BIGNUM *ret,int bits,int strong,BIGNUM *add,
+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);