Line data Source code
1 : /* Encapsulated candidate. This candidate should have been a C++ class, but
2 : since we are using straight C for this project, I guess I can deal with it.
3 :
4 : Copyright 2003, 2004, 2005, 2006 Jim Fougeron, Paul Zimmermann.
5 :
6 : This program is free software; you can redistribute it and/or modify
7 : it under the terms of the GNU General Public License as published by
8 : the Free Software Foundation; either version 3 of the License, or (at your
9 : option) any later version.
10 :
11 : This program is distributed in the hope that it will be useful, but
12 : WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 : or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
14 : more details.
15 :
16 : You should have received a copy of the GNU General Public License
17 : along with this program; see the file COPYING. If not, see
18 : http://www.gnu.org/licenses/ or write to the Free Software Foundation, Inc.,
19 : 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA. */
20 :
21 : #include <stdio.h>
22 : #include <stdlib.h>
23 : #include <string.h>
24 : #include "ecm-ecm.h"
25 :
26 : #define VALID_MAGIC 0x24837BF5
27 : #define DEAD_MAGIC 0xDEADBEEF
28 :
29 : #if defined (CANDI_DEBUG)
30 : static void
31 : Candi_Validate (const char *FunctionStr, const mpcandi_t *n)
32 : {
33 : int abrt = 0;
34 : if (!FunctionStr)
35 : {
36 : fprintf (stderr, "ERROR, UNKNOWN FUNCTION, can NOT continue checks!\n");
37 : exit(-1);
38 : }
39 : if (!n)
40 : {
41 : abrt = fprintf (stderr, "ERROR, %s() *n was NULL, can NOT continue checks!\n", FunctionStr);
42 : exit(-1);
43 : }
44 : if (n->magic != VALID_MAGIC)
45 : abrt = fprintf (stderr, "ERROR, %s() VALID_MAGIC not valid\n", FunctionStr);
46 : if (n->cpExpr && n->nexprlen != strlen(n->cpExpr))
47 : abrt = fprintf (stderr, "ERROR, %s() Invalid cpExpr length\n", FunctionStr);
48 : if (n->ndigits != nb_digits(n->n))
49 : abrt = fprintf (stderr, "ERROR, %s() Invalid n->ndigits length\n", FunctionStr);
50 : if (abrt)
51 : exit(-1);
52 : }
53 : #endif
54 :
55 : void
56 6049 : mpcandi_t_init (mpcandi_t *n)
57 : {
58 6049 : n->cpExpr = NULL;
59 6049 : n->nexprlen = 0;
60 6049 : n->ndigits = 1;
61 6049 : mpz_init_set_ui (n->n, 1);
62 6049 : n->isPrp = 0;
63 : #if defined (CANDI_DEBUG)
64 : n->magic = VALID_MAGIC;
65 : Candi_Validate ("mpcandi_t_init", n);
66 : #endif
67 6049 : }
68 :
69 : void
70 4905 : mpcandi_t_free (mpcandi_t *n)
71 : {
72 : #if defined (CANDI_DEBUG)
73 : Candi_Validate("mpcandi_t_free", n);
74 : #endif
75 4905 : if (n->cpExpr)
76 553 : free (n->cpExpr);
77 4905 : n->cpExpr = NULL;
78 4905 : n->nexprlen = 0;
79 4905 : n->ndigits = 0;
80 4905 : mpz_clear (n->n);
81 4905 : n->isPrp = 1; /* "default" to prp, so that if the candidate does not get
82 : filled in, it will not be tested */
83 : #if defined (CANDI_DEBUG)
84 : n->magic = DEAD_MAGIC;
85 : #endif
86 4905 : }
87 :
88 : int
89 2774 : mpcandi_t_add_candidate (mpcandi_t *n, mpz_t c, const char *cpExpr,
90 : int primetest)
91 : {
92 : #if defined (CANDI_DEBUG)
93 : Candi_Validate("Pre mpcandi_t_add_candidate", n);
94 : #endif
95 :
96 2774 : if (n->cpExpr)
97 0 : free (n->cpExpr);
98 2774 : n->cpExpr = NULL;
99 2774 : if (cpExpr)
100 : {
101 613 : n->nexprlen = strlen (cpExpr);
102 613 : n->cpExpr = (char *) malloc (n->nexprlen + 1);
103 613 : ASSERT_ALWAYS (n->cpExpr != NULL);
104 613 : strcpy (n->cpExpr, cpExpr);
105 : }
106 2774 : mpz_set (n->n, c);
107 2774 : n->ndigits = nb_digits (c);
108 2774 : if (primetest)
109 : {
110 20 : if (n->ndigits < APRCL_CUTOFF)
111 20 : n->isPrp = mpz_aprtcle (c, 0);
112 0 : else if (n->ndigits < APRCL_CUTOFF2)
113 0 : n->isPrp = mpz_aprtcle (c, 1);
114 : else
115 0 : n->isPrp = mpz_probab_prime_p (c, PROBAB_PRIME_TESTS);
116 : }
117 : else
118 2754 : n->isPrp = 0; /* there is a candidate there now, and the user did not
119 : tell us to prp it, so assume it is composite */
120 :
121 : #if defined (CANDI_DEBUG)
122 : Candi_Validate("Post mpcandi_t_add_candidate", n);
123 : #endif
124 :
125 2774 : return 1;
126 : }
127 :
128 : int
129 1929 : mpcandi_t_addfoundfactor (mpcandi_t *n, mpz_t f, int displaywarning)
130 : {
131 : #if defined (CANDI_DEBUG)
132 : Candi_Validate("Pre mpcandi_t_addfoundfactor", n);
133 : #endif
134 : char *cp, *cp1;
135 :
136 1929 : if (!mpz_divisible_p (n->n, f))
137 : {
138 : /* ERROR was not a factor NOTE however, that this is "valid" for the
139 : ui() function to call. When trial dividing, it is VERY frequent to
140 : be divisible by 2^3, and we try to remove factors UNTIL */
141 0 : if (displaywarning)
142 0 : gmp_fprintf (stderr, "ECM logic ERROR. Trying to remove a "
143 : "non-factor %Zd\n", f);
144 : #if defined (CANDI_DEBUG)
145 : Candi_Validate("Post (no factor removed) mpcandi_t_addfoundfactor", n);
146 : #endif
147 0 : return 0;
148 : }
149 :
150 : /* remove f from n->n */
151 1929 : mpz_divexact (n->n, n->n, f);
152 1929 : n->ndigits = nb_digits (n->n);
153 1929 : if (n->ndigits < APRCL_CUTOFF)
154 1874 : n->isPrp = mpz_aprtcle (n->n, 0);
155 55 : else if (n->ndigits < APRCL_CUTOFF2)
156 20 : n->isPrp = mpz_aprtcle (n->n, 1);
157 : else
158 35 : n->isPrp = mpz_probab_prime_p (n->n, PROBAB_PRIME_TESTS);
159 1929 : if (n->cpExpr != NULL)
160 : {
161 : /* If there is an expression, then lets preserve it */
162 509 : cp1 = mpz_get_str (NULL, 10, f);
163 509 : cp = (char *) malloc(n->nexprlen+1 + 3 + strlen(cp1)); /* +1 for null, +3 for ()/ */
164 509 : ASSERT_ALWAYS (cp != NULL);
165 509 : sprintf (cp, "(%s)/%s", n->cpExpr, cp1);
166 509 : free(n->cpExpr);
167 509 : n->cpExpr = cp;
168 509 : n->nexprlen += (3+strlen(cp1));
169 509 : free (cp1); /* size strlen (cp1) + 1 */
170 : }
171 : #if defined (CANDI_DEBUG)
172 : Candi_Validate("Post (removed factor) mpcandi_t_addfoundfactor", n);
173 : #endif
174 1929 : return 1;
175 : }
176 :
177 : /**********************************************************************
178 : Group order candidate functions. These wrap the logic for the -go
179 : command line switch which allows the user to "insert" the proper
180 : group order.
181 : **********************************************************************/
182 : void
183 3116 : mpgocandi_t_init (mpgocandi_t *go)
184 : {
185 3116 : go->cpOrigExpr = NULL;
186 3116 : mpcandi_t_init (&(go->Candi));
187 3116 : go->containsN = 0;
188 3116 : go->Valid = 0;
189 3116 : }
190 :
191 : void
192 2474 : mpgocandi_t_free (mpgocandi_t *go)
193 : {
194 2474 : if (go->cpOrigExpr)
195 161 : free (go->cpOrigExpr);
196 2474 : mpcandi_t_free (&(go->Candi));
197 2474 : go->Valid = 0;
198 2474 : }
199 :
200 : int
201 2529 : mpgocandi_fixup_with_N (mpgocandi_t *go, mpcandi_t *n)
202 : {
203 : int NumNs, len;
204 : char *cp, *cpo, *numbuf;
205 :
206 2529 : if (go->Valid == 0)
207 2358 : return 0;
208 171 : if (go->containsN == 0)
209 156 : return 1; /* a valid "normal" expression does not need updating */
210 :
211 15 : cp = strchr (go->cpOrigExpr, 'N');
212 15 : NumNs = 0;
213 30 : while (cp)
214 : {
215 15 : ++NumNs;
216 15 : cp = strchr (&cp[1], 'N');
217 : }
218 : /* compute size of string needed, and add some safety buffer to it */
219 15 : cp = go->cpOrigExpr;
220 15 : len = NumNs * mpz_sizeinbase (n->n, 10) + strlen (cp) + 100;
221 15 : numbuf = (char *) malloc(len);
222 15 : ASSERT_ALWAYS (numbuf != NULL);
223 15 : cpo = numbuf;
224 50 : while (*cp)
225 : {
226 35 : if (*cp == 'N')
227 15 : cpo += gmp_sprintf (cpo, "%Zi", n->n);
228 : else
229 20 : *cpo++ = *cp;
230 35 : ++cp;
231 : }
232 :
233 15 : *cpo = 0; /* Null terminate the string correctly. */
234 :
235 15 : go->Valid = eval_str (&(go->Candi), numbuf, 0, NULL);
236 : /* for invalid inputs, eval_str() directly exit(1) */
237 :
238 5 : free (numbuf);
239 5 : return go->Valid;
240 : }
|