Remove vestiges of @primorial@.

[u/mdw/catacomb] / prim.c

/* -*-c-*-
 *
 * $Id: prim.c,v 1.2 2000/07/29 09:57:42 mdw Exp $
 *
 * Finding primitive elements
 *
 * (c) 1999 Straylight/Edgeware
 */

/*----- Licensing notice --------------------------------------------------* 
 *
 * This file is part of Catacomb.
 *
 * Catacomb is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Library General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 * 
 * Catacomb 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 Library General Public License for more details.
 * 
 * You should have received a copy of the GNU Library General Public
 * License along with Catacomb; if not, write to the Free
 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
 * MA 02111-1307, USA.
 */

/*----- Revision history --------------------------------------------------* 
 *
 * $Log: prim.c,v $
 * Revision 1.2  2000/07/29 09:57:42  mdw
 * Improve primitive-element testing a lot.  Now much more sensible and
 * orthogonal: you can find a generator for any given subgroup order by
 * putting in the appropriate parameters.
 *
 * Revision 1.1  1999/12/22 15:58:59  mdw
 * Search for primitive elements using prime-search equipment.
 *
 */

/*----- Header files ------------------------------------------------------*/

#include "mp.h"
#include "mpint.h"
#include "mpmont.h"
#include "mprand.h"
#include "pgen.h"
#include "prim.h"

/*----- Main code ---------------------------------------------------------*/

/* --- @prim_test@ --- */

int prim_test(int rq, pgen_event *ev, void *p)
{
  prim_ctx *c = p;
  int rc = rq;

  switch (rq) {
    case PGEN_BEGIN:
      return (PGEN_TRY);
    case PGEN_TRY: {
      mp *x;
      rc = PGEN_FAIL;

      if (!c->exp)
        x = mp_copy(ev->m);
      else {
	x = mpmont_exp(&c->mm, MP_NEW, ev->m, c->exp);
	if (MP_CMP(x, ==, MP_ONE))
	  goto done;
      }
      if (c->n == 0)
        goto ok;
      else {
	size_t n = c->n;
	mp **f = c->f;
	mp *y = MP_NEW;
	while (n) {
	  y = mpmont_exp(&c->mm, y, x, *f);
	  if (MP_CMP(y, ==, MP_ONE)) {
	    mp_drop(y);
	    goto done;
	  }
	  n--; f++;
	}
	mp_drop(y);
      }
    ok:
      rc = PGEN_DONE;
      mp_drop(ev->m);
      ev->m = x;
      break;
    done:
      mp_drop(x);
    } break;
  }

  return (rc);
}

/* --- Trivial stepping functions -----------------------------------------*/

/* --- @prim_step@ --- */

int prim_step(int rq, pgen_event *ev, void *p)
{
  unsigned *i = p;
  switch (rq) {
    case PGEN_BEGIN:
    case PGEN_TRY:
      if (*i >= NPRIME)
	return PGEN_FAIL;
      ev->m = mp_fromint(ev->m, primetab[(*i)++]);
      return (PGEN_TRY);
  }
  return (0);
}

/*----- That's all, folks -------------------------------------------------*/