bignum-random-prime.c

/* bignum-random-prime.c
 *
 * Generation of random provable primes.
 */

/* nettle, low-level cryptographics library
 *
 * Copyright (C) 2010 Niels Möller
 *  
 * The nettle library is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation; either version 2.1 of the License, or (at your
 * option) any later version.
 * 
 * The nettle library is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
 * License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public License
 * along with the nettle library; see the file COPYING.LIB.  If not, write to
 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
 * MA 02111-1301, USA.
 */

#if HAVE_CONFIG_H
# include "config.h"
#endif

#ifndef RANDOM_PRIME_VERBOSE
#define RANDOM_PRIME_VERBOSE 0
#endif

#include <assert.h>
#include <stdlib.h>

#if RANDOM_PRIME_VERBOSE
#include <stdio.h>
#define VERBOSE(x) (fputs((x), stderr))
#else
#define VERBOSE(x)
#endif

#include "bignum.h"

#include "macros.h"

/* Use a table of p_2 = 3 to p_{172} = 1021, used for sieving numbers
   of up to 20 bits. */

#define NPRIMES 171
#define TRIAL_DIV_BITS 20
#define TRIAL_DIV_MASK ((1 << TRIAL_DIV_BITS) - 1)

/* A 20-bit number x is divisible by p iff

     ((x * inverse) & TRIAL_DIV_MASK) <= limit
*/
struct trial_div_info {
  uint32_t inverse; /* p^{-1} (mod 2^20) */
  uint32_t limit;   /* floor( (2^20 - 1) / p) */
};

static const uint16_t
primes[NPRIMES] = {
  3,5,7,11,13,17,19,23,
  29,31,37,41,43,47,53,59,
  61,67,71,73,79,83,89,97,
  101,103,107,109,113,127,131,137,
  139,149,151,157,163,167,173,179,