gordon.c

Handbook of Applied Cryptography (Algorithms, Mathematics, Science, Source Code)

/*
  Author:  Pate Williams (c) 1997

  Gordon's algorithm for generating strong primes.
  See "Handbook of Applied Cryptography" by Alfred
  J. Menezes et al 4.53 Algorithm page 150.
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "lip.h"

long Gordon(long bit_length, verylong *zp)
{
  long i, i0, j, k, j0, s_size = bit_length / 2;
  verylong za = 0, zb = 0, zc = 0, zr = 0;
  verylong zs = 0, zt = 0, zp0 = 0;

  zrstarts(time(NULL));
  zrandomprime(s_size, 5l, &zs, zrandomb);
  zrandomprime(s_size, 5l, &zt, zrandomb);
  zlshift(zt, 1l, &za);
  do i0 = rand(); while (i0 == 0);
  i = i0;
  do {
    /* compute r = 2 * i * t + 1 */
    zsmul(za, i, &zb);
    zsadd(zb, 1l, &zr);
    i++;
  } while (!zprobprime(zr, 5l));
  /* compute p0 = ((2 * s) ^ (r - 2) mod r) * s - 1 */
  zlshift(zs, 2l, &za);
  zsadd(zr, - 2l, &zb);
  zexpmod(za, zb, zr, &zc);
  zmul(zc, zs, &za);
  zsadd(za, - 1l, &zp0);
  zlshift(zr, 1l, &zb);
  zmul(zb, zs, &za);
  do j0 = rand(); while (j0 == 0);
  j = j0;
  k = 0;
  do {
    /* compute p = p0 + 2 * j * r * s */
    zsmul(za, j, &zb);
    zadd(zb, zp0, zp);
    j++, k++;
    printf("\b\b\b\b\b%4ld", k);
  } while (k < 1000 && !zprobprime(*zp, 5l));
  zfree(&za);
  zfree(&zb);
  zfree(&zc);
  zfree(&zr);
  zfree(&zs);
  zfree(&zt);
  zfree(&zp0);
  if (k == 1000) return Gordon(bit_length, zp);
  return z2log(*zp);
}

int main(void)
{
  long bit_length, i;
  verylong zp = 0;

  for (i = 100; i <= 180; i += 20) {
    bit_length = Gordon(i, &zp);
    printf(" %3ld %3ld ", i, bit_length);
    zwriteln(zp);
  }
  zfree(&zp);
  return 0;
}