bignum-random-prime.c

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

/* nettle, low-level cryptographics library
 *
 * Copyright (C) 2010 Niels Mller
 *  
 * 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., 59 Temple Place - Suite 330, Boston,
 * MA 02111-1307, 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, multiplied to 32-bit or
   64-bit size. */

struct sieve_element {
  /* Product of some small primes. */
  unsigned long prod;
  /* Square of the smallest one. */
  unsigned long p2;
};

static const struct sieve_element
sieve_table[] = {
  {111546435, 9}, /* 3 -- 23 */
  {58642669, 841}, /* 29 -- 43 */
  {600662303, 2209}, /* 47 -- 67 */
  {33984931, 5041}, /* 71 -- 83 */
  {89809099, 7921}, /* 89 -- 103 */
  {167375713, 11449}, /* 107 -- 127 */
  {371700317, 17161}, /* 131 -- 149 */
  {645328247, 22801}, /* 151 -- 167 */
  {1070560157, 29929}, /* 173 -- 191 */
  {1596463769, 37249}, /* 193 -- 211 */
  {11592209, 49729}, /* 223 -- 229 */