1/* crypto/bn/bn_prime.c */
2/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3 * All rights reserved.
4 *
5 * This package is an SSL implementation written
6 * by Eric Young (eay@cryptsoft.com).
7 * The implementation was written so as to conform with Netscapes SSL.
8 *

--- 364 unchanged lines hidden (view full) ---

373 bn_check_top(w);
374 return 1;
375 }
376
377static int probable_prime(BIGNUM *rnd, int bits)
378 {
379 int i;
380 BN_ULONG mods[NUMPRIMES];
381 BN_ULONG delta,maxdelta;
382
383again:
384 if (!BN_rand(rnd,bits,1,1)) return(0);
385 /* we now have a random number 'rand' to test. */
386 for (i=1; i<NUMPRIMES; i++)
387 mods[i]=BN_mod_word(rnd,(BN_ULONG)primes[i]);
388 maxdelta=BN_MASK2 - primes[NUMPRIMES-1];
389 delta=0;
390 loop: for (i=1; i<NUMPRIMES; i++)
391 {
392 /* check that rnd is not a prime and also
393 * that gcd(rnd-1,primes) == 1 (except for 2) */
394 if (((mods[i]+delta)%primes[i]) <= 1)
395 {
396 delta+=2;
397 if (delta > maxdelta) goto again;
398 goto loop;
399 }
400 }
401 if (!BN_add_word(rnd,delta)) return(0);
402 bn_check_top(rnd);
403 return(1);
404 }
405

--- 89 unchanged lines hidden ---