[u/mdw/catacomb] / pgen-gcd.c

/* -*-c-*-
 *
 * $Id: pgen-gcd.c,v 1.1 2000/06/17 11:51:53 mdw Exp $
 *
 * Prime search stepper ensuring a low GCD for %$(p - 1)/2$%
 *
 * (c) 2000 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: pgen-gcd.c,v $
 * Revision 1.1  2000/06/17 11:51:53  mdw
 * Filter which imposes additional restrictions on GCD of %$(p - 1)/2$%
 * with a given integer.
 *
 */

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

#include "mp.h"
#include "pgen.h"

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

int pgen_gcdstep(int rq, pgen_event *ev, void *p)
{
  pgen_gcdstepctx *g = p;
  int rc = PGEN_ABORT;

  switch (rq) {

    /* --- Set everything up --- *
     *
     * Call things off if @q@ and @jq@ have common factors.
     */

    case PGEN_BEGIN: {
      mp *p = ev->m;
      g->q = mp_lsr(MP_NEW, p, 1);
      g->jq = mp_lsr(MP_NEW, g->jp.m, 1);
      mp_gcd(&g->g, 0, 0, g->q, g->jq);
      if (MP_CMP(g->g, >, MP_ONE))
	return (PGEN_ABORT);
      rc = pfilt_create(&g->p, p);
      mp_drop(p);
    } break;

    /* --- Grind through another iteration --- */

    case PGEN_TRY:
      mp_drop(ev->m);
      rc = pfilt_jump(&g->p, &g->jp);
      g->q = mp_add(g->q, g->q, g->jq);
      break;

    /* --- Finished --- */

    case PGEN_DONE:
      pfilt_destroy(&g->p);
      mp_drop(g->q);
      mp_drop(g->jq);
      return (PGEN_DONE);
  }

  /* --- Step on until everything is OK --- */

  for (;;) {
    if (rc != PGEN_FAIL) {
      mp_gcd(&g->g, 0, 0, g->r, g->q);
      if (MP_CMP(g->g, >, g->max))
	rc = PGEN_FAIL;
    }
    if (rc != PGEN_FAIL)
      break;
    rc = pfilt_jump(&g->p, &g->jp);
    g->q = mp_add(g->q, g->q, g->jq);
  }

  ev->m = MP_COPY(g->p.m);
  return (rc);
}

/*----- That's all, folks -------------------------------------------------*/
Commit	Line	Data
423c89a3	1	/* --c--
	2	*
	3	* $Id: pgen-gcd.c,v 1.1 2000/06/17 11:51:53 mdw Exp $
	4	*
	5	* Prime search stepper ensuring a low GCD for %$(p - 1)/2$%
	6	*
	7	* (c) 2000 Straylight/Edgeware
	8	*/
	9
	10	/----- Licensing notice --------------------------------------------------
	11	*
	12	* This file is part of Catacomb.
	13	*
	14	* Catacomb is free software; you can redistribute it and/or modify
	15	* it under the terms of the GNU Library General Public License as
	16	* published by the Free Software Foundation; either version 2 of the
	17	* License, or (at your option) any later version.
	18	*
	19	* Catacomb is distributed in the hope that it will be useful,
	20	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	21	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	22	* GNU Library General Public License for more details.
	23	*
	24	* You should have received a copy of the GNU Library General Public
	25	* License along with Catacomb; if not, write to the Free
	26	* Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
	27	* MA 02111-1307, USA.
	28	*/
	29
	30	/----- Revision history --------------------------------------------------
	31	*
	32	* $Log: pgen-gcd.c,v $
	33	* Revision 1.1 2000/06/17 11:51:53 mdw
	34	* Filter which imposes additional restrictions on GCD of %$(p - 1)/2$%
	35	* with a given integer.
	36	*
	37	*/
	38
	39	/----- Header files ------------------------------------------------------/
	40
	41	#include "mp.h"
	42	#include "pgen.h"
	43
	44	/----- Main code ---------------------------------------------------------/
	45
	46	int pgen_gcdstep(int rq, pgen_event ev, void p)
	47	{
	48	pgen_gcdstepctx *g = p;
	49	int rc = PGEN_ABORT;
	50
	51	switch (rq) {
	52
	53	/* --- Set everything up --- *
	54	*
	55	* Call things off if @q@ and @jq@ have common factors.
	56	*/
	57
	58	case PGEN_BEGIN: {
	59	mp *p = ev->m;
	60	g->q = mp_lsr(MP_NEW, p, 1);
	61	g->jq = mp_lsr(MP_NEW, g->jp.m, 1);
	62	mp_gcd(&g->g, 0, 0, g->q, g->jq);
	63	if (MP_CMP(g->g, >, MP_ONE))
	64	return (PGEN_ABORT);
65	rc = pfilt_create(&g->p, p);
66	mp_drop(p);
67	} break;
68
69	/* --- Grind through another iteration --- */
70
71	case PGEN_TRY:
72	mp_drop(ev->m);
73	rc = pfilt_jump(&g->p, &g->jp);
74	g->q = mp_add(g->q, g->q, g->jq);
75	break;
76
77	/* --- Finished --- */
78
79	case PGEN_DONE:
80	pfilt_destroy(&g->p);
81	mp_drop(g->q);
82	mp_drop(g->jq);
83	return (PGEN_DONE);
84	}
85
86	/* --- Step on until everything is OK --- */
87
88	for (;;) {
89	if (rc != PGEN_FAIL) {
90	mp_gcd(&g->g, 0, 0, g->r, g->q);
91	if (MP_CMP(g->g, >, g->max))
92	rc = PGEN_FAIL;
93	}
94	if (rc != PGEN_FAIL)
95	break;
96	rc = pfilt_jump(&g->p, &g->jp);
97	g->q = mp_add(g->q, g->q, g->jq);
98	}
99
100	ev->m = MP_COPY(g->p.m);
101	return (rc);
102	}
103
104	/----- That's all, folks -------------------------------------------------/