solovay.c

应用密码学手册-英文版,学习密码学和网络安全的好资料。

/*
  Author:  Pate Williams (c) 1997

  4.18 Algorithm Solovay-Strassen probabilistic
  primality test. See "Handbook of Applied
  Cryptography" by Alfred J. Menezes et al
  page 138.
*/

#include <ctype.h>
#include <stdio.h>
#include "lip.h"

int Solovay_Strassen(long t, verylong zn)
{
  int flag = 1;
  long i;
  verylong za = 0, zn1 = 0, zn2 = 0, zr = 0;
  verylong zs = 0, zt = 0;

  if (zodd(zn)) {
    if (zscompare(zn, 3l) > 0) {
      zsadd(zn, - 1l, &zn1);
      zrshift(zn1, 1l, &zn2);
      for (i = 1; flag && i <= t; i++) {
        do zrandomb(zn1, &za); while (zscompare(za, 2l) < 0);
        zexpmod(za, zn2, zn, &zr);
        if (zscompare(zr, 1l) != 0 &&
            zcompare(zr, zn1) != 0) flag = 0;
        zintoz(zjacobi(za, zn), &zs);
        if (zscompare(zs, 0l) < 0) {
          zadd(zs, zn, &zt);
          zcopy(zt, &zs);
        }
        if (flag && zcompare(zr, zs) != 0)
          flag = 0;
      }
    }
  }
  else flag = zscompare(zn, 2l) == 0;
  zfree(&za);
  zfree(&zn1);
  zfree(&zn2);
  zfree(&zr);
  zfree(&zs);
  zfree(&zt);
  return flag;
}

int main(void)
{
  char answer[256];
  long t;
  verylong zn = 0;

  do {
    do {
      printf("enter the security parameter ( >= 1): ");
      scanf("%d", &t);
    } while (t < 1);
    printf("enter the number to be tested below:\n");
    zread(&zn);
    if (Solovay_Strassen(t, zn))
      printf("number is probably prime\n");
    else
      printf("number is composite\n");
    printf("another number (n or y)? ");
    scanf("%s", answer);
  } while (tolower(answer[0]) == 'y');
  zfree(&zn);
  return 0;
}