[u/mdw/catacomb] / math / prim.c

/* -*-c-*-
 *
 * 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.
 */

/*----- 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_EQ(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_EQ(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 -------------------------------------------------*/
Commit	Line	Data
fcdaa180	1	/* --c--
fcdaa180	2	*
fcdaa180	3	* Finding primitive elements
	4	*
	5	* (c) 1999 Straylight/Edgeware
	6	*/
	7
45c0fd36	8	/----- Licensing notice --------------------------------------------------
fcdaa180	9	*
	10	* This file is part of Catacomb.
	11	*
	12	* Catacomb is free software; you can redistribute it and/or modify
	13	* it under the terms of the GNU Library General Public License as
	14	* published by the Free Software Foundation; either version 2 of the
	15	* License, or (at your option) any later version.
45c0fd36	16	*
fcdaa180	17	* Catacomb is distributed in the hope that it will be useful,
	18	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	19	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	20	* GNU Library General Public License for more details.
45c0fd36	21	*
fcdaa180	22	* You should have received a copy of the GNU Library General Public
	23	* License along with Catacomb; if not, write to the Free
	24	* Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
	25	* MA 02111-1307, USA.
	26	*/
	27
fcdaa180	28	/----- Header files ------------------------------------------------------/
	29
	30	#include "mp.h"
	31	#include "mpint.h"
	32	#include "mpmont.h"
	33	#include "mprand.h"
	34	#include "pgen.h"
	35	#include "prim.h"
	36
	37	/----- Main code ---------------------------------------------------------/
	38
	39	/* --- @prim_test@ --- */
	40
	41	int prim_test(int rq, pgen_event ev, void p)
	42	{
	43	prim_ctx *c = p;
	44	int rc = rq;
	45
	46	switch (rq) {
	47	case PGEN_BEGIN:
	48	return (PGEN_TRY);
	49	case PGEN_TRY: {
6f80d39f	50	mp *x;
fcdaa180	51	rc = PGEN_FAIL;
fcdaa180	52
6f80d39f	53	if (!c->exp)
45c0fd36	54	x = mp_copy(ev->m);
6f80d39f	55	else {
6f80d39f	56	x = mpmont_exp(&c->mm, MP_NEW, ev->m, c->exp);
22bab86c	57	if (MP_EQ(x, MP_ONE))
6f80d39f	58	goto done;
	59	}
	60	if (c->n == 0)
45c0fd36	61	goto ok;
6f80d39f	62	else {
	63	size_t n = c->n;
	64	mp **f = c->f;
	65	mp *y = MP_NEW;
fcdaa180	66	while (n) {
6f80d39f	67	y = mpmont_exp(&c->mm, y, x, *f);
22bab86c	68	if (MP_EQ(y, MP_ONE)) {
6f80d39f	69	mp_drop(y);
fcdaa180	70	goto done;
6f80d39f	71	}
fcdaa180	72	n--; f++;
fcdaa180	73	}
6f80d39f	74	mp_drop(y);
fcdaa180	75	}
6f80d39f	76	ok:
fcdaa180	77	rc = PGEN_DONE;
6f80d39f	78	mp_drop(ev->m);
	79	ev->m = x;
	80	break;
fcdaa180	81	done:
	82	mp_drop(x);
	83	} break;
	84	}
	85
	86	return (rc);
	87	}
	88
	89	/* --- Trivial stepping functions -----------------------------------------*/
	90
	91	/* --- @prim_step@ --- */
	92
	93	int prim_step(int rq, pgen_event ev, void p)
	94	{
	95	unsigned *i = p;
	96	switch (rq) {
	97	case PGEN_BEGIN:
	98	case PGEN_TRY:
	99	if (*i >= NPRIME)
	100	return PGEN_FAIL;
	101	ev->m = mp_fromint(ev->m, primetab[(*i)++]);
	102	return (PGEN_TRY);
	103	}
	104	return (0);
	105	}
	106
	107	/----- That's all, folks -------------------------------------------------/