Line data Source code
1 : /* Auxiliary functions for GMP-ECM.
2 :
3 : Copyright 2002, 2003, 2004, 2005, 2006, 2007, 2011, 2012 Paul Zimmermann,
4 : Alexander Kruppa, Laurent Fousse, Jim Fougeron, Cyril Bouvier.
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 :
22 : #include <stdio.h>
23 : #include <stdlib.h>
24 : #include "ecm-impl.h"
25 : #include "ecm-ecm.h"
26 :
27 : #ifdef HAVE_GWNUM
28 : /* For GWNUM_VERSION */
29 : #include "gwnum.h"
30 : #endif
31 :
32 : #include "champions.h"
33 :
34 : /******************************************************************************
35 : * *
36 : * Auxiliary functions *
37 : * *
38 : ******************************************************************************/
39 :
40 : /* returns the number of decimal digits of n */
41 : unsigned int
42 7259 : nb_digits (const mpz_t n)
43 : {
44 : mpz_t x;
45 : unsigned int size;
46 :
47 7259 : size = mpz_sizeinbase (n, 10);
48 :
49 : /* the GMP documentation says mpz_sizeinbase returns the exact value,
50 : or one too big, thus:
51 : (a) either n < 10^(size-1), and n has size-1 digits
52 : (b) or n >= size-1, and n has size digits
53 : Note: mpz_sizeinbase returns 1 for n=0, thus we always have size >= 1.
54 : */
55 :
56 7259 : mpz_init (x);
57 7259 : mpz_ui_pow_ui (x, 10, size - 1);
58 7259 : if (mpz_cmpabs (n, x) < 0)
59 787 : size --;
60 7259 : mpz_clear (x);
61 :
62 7259 : return size;
63 : }
64 :
65 : /* Tries to read a number from a line from fd and stores it in r.
66 : Keeps reading lines until a number is found. Lines beginning with "#"
67 : are skipped.
68 : Returns 1 if a number was successfully read, 0 if no number can be read
69 : (i.e. at EOF)
70 : Function is now simpler. Much of the logic (other than skipping # lines
71 : is now contained within eval() function.
72 : */
73 :
74 : int
75 5037 : read_number (mpcandi_t *n, FILE *fd, int primetest)
76 : {
77 : int c;
78 :
79 5037 : new_line:
80 5037 : c = fgetc (fd);
81 :
82 : /* Skip comment lines beginning with '#' */
83 5037 : if (c == '#')
84 : {
85 : do
86 1100 : c = fgetc (fd);
87 1100 : while (c != EOF && !IS_NEWLINE(c));
88 10 : if (IS_NEWLINE(c))
89 10 : goto new_line;
90 : }
91 :
92 5027 : if (c == EOF)
93 2154 : return 0;
94 :
95 2873 : ungetc (c, fd);
96 2873 : if (!eval (n, fd, primetest))
97 0 : goto new_line;
98 :
99 : #if 0
100 : /* Code to test out eval_str function, which "appears" to work correctly. */
101 : {
102 : /* warning!! Line is pretty small, but since this is just testing code, we
103 : can easily control the input for this test. This code should NEVER be
104 : compiled into released build, its only for testing of eval_str() */
105 : char Line[500], *cp;
106 : fgets (Line, sizeof(Line), fd);
107 :
108 : if (!eval_str (n, Line, primetest, &cp))
109 : goto new_line;
110 : fprintf (stderr, "\nLine is at %X cp is at %X\n", Line, cp);
111 : }
112 : #endif
113 :
114 : #if defined (DEBUG_EVALUATOR)
115 : if (n->cpExpr)
116 : fprintf (stderr, "%s\n", n->cpExpr);
117 : mpz_out_str (stderr, 10, n->n);
118 : fprintf (stderr, "\n");
119 : #endif
120 :
121 2603 : return 1;
122 : }
123 :
124 : int
125 1929 : process_newfactor (mpz_t g, int result, mpcandi_t *n, int method,
126 : int returncode, int gpu, unsigned int *cnt,
127 : int *resume_wasPrp, mpz_t resume_lastfac,
128 : FILE *resumefile, int verbose, int deep)
129 : {
130 1929 : int factor_is_prime = 0;
131 : /* If a factor was found, indicate whether factor, cofactor are */
132 : /* prime. If no factor was found, both are zero. */
133 1929 : int cofactor_is_prime = 0;
134 : int method1;
135 : int found_n;
136 : mpz_t f;
137 :
138 1929 : mpz_init (f);
139 :
140 1929 : mpz_gcd (f, g, n->n);
141 :
142 : /* When GPU is not used, the factor should divide n->n */
143 1929 : if (gpu == 0)
144 1929 : ASSERT_ALWAYS(mpz_cmp (g, f) == 0);
145 0 : else if (mpz_cmp (g, f) != 0 && mpz_cmp_ui (f, 1) == 0)
146 : /* GPU case: all factors of g were already found */
147 : {
148 : /* FIXME Maybe print something in very verbose mode */
149 0 : mpz_clear (f);
150 0 : return returncode;
151 : }
152 :
153 : /* Restoring print statement that was disabled from previous code clean-up efforts */
154 : /* This print statement is important to the function of external factoring programs */
155 : /* that rely on the following information being printed out */
156 : /* g = f (gpu or not gpu) or g != 1 with gpu */
157 1929 : if (mpz_cmp (g, f) == 0 || (gpu != 0 && mpz_cmp_ui (g, 1) != 0))
158 : {
159 1929 : if (verbose > 0)
160 1909 : printf ("********** Factor found in step %u: ", ABS (result));
161 :
162 1929 : mpz_out_str (stdout, 10, f);
163 :
164 1929 : if (verbose > 0)
165 1909 : printf ("\n");
166 : }
167 :
168 : /* Complain about non-proper factors (0, negative) */
169 1929 : ASSERT_ALWAYS(mpz_cmp_ui (f, 1) >= 1);
170 :
171 1929 : found_n = mpz_cmp (f, n->n) == 0;
172 :
173 : /* 1 for display warning if factor does not divide the current
174 : candidate */
175 1929 : mpcandi_t_addfoundfactor (n, f, gpu == 0);
176 :
177 1929 : if (found_n == 0)
178 : {
179 : /* prints factor found and cofactor on standard output. */
180 : /* the second argument here tells aprtcle to not print primality proving progress info */
181 1316 : factor_is_prime = mpz_aprtcle (f, 0);
182 :
183 1316 : if (verbose >= 1)
184 : {
185 1296 : if (factor_is_prime == ECM_FAC_PRIME)
186 1260 : printf ("Found prime factor of %u digits: ", nb_digits (f));
187 36 : else if (factor_is_prime == ECM_FAC_PRP)
188 0 : printf ("Found probable prime factor of %u digits: ", nb_digits (f));
189 : else
190 36 : printf ("Found composite factor of %u digits: ", nb_digits (f));
191 1296 : mpz_out_str (stdout, 10, f);
192 1296 : printf ("\n");
193 : }
194 :
195 1316 : if (resumefile != NULL)
196 : {
197 : /* If we are resuming from a save file, add factor to the
198 : discovered factors for the current number */
199 62 : mpz_mul (resume_lastfac, resume_lastfac, f);
200 62 : *resume_wasPrp = n->isPrp;
201 : }
202 :
203 1316 : if (factor_is_prime && returncode == 0)
204 1280 : returncode = (n->isPrp) ? ECM_PRIME_FAC_PRIME_COFAC :
205 : ECM_PRIME_FAC_COMP_COFAC;
206 : else
207 36 : returncode = (n->isPrp) ? ECM_COMP_FAC_PRIME_COFAC :
208 : ECM_COMP_FAC_COMP_COFAC;
209 :
210 1316 : if (verbose >= 1)
211 : {
212 1296 : cofactor_is_prime = n->isPrp; /* from mpcandi_t_addfoundfactor */
213 :
214 1296 : if (cofactor_is_prime == ECM_FAC_PRIME)
215 879 : printf ("Prime cofactor ");
216 417 : else if (cofactor_is_prime == ECM_FAC_PRP)
217 0 : printf ("Probable prime cofactor ");
218 : else
219 417 : printf ("Composite cofactor ");
220 :
221 1296 : if (n->cpExpr)
222 464 : printf ("%s", n->cpExpr);
223 : else
224 832 : mpz_out_str (stdout, 10, n->n);
225 1296 : printf (" has %u digits\n", n->ndigits);
226 : }
227 : else /* quiet mode: just print a space here, remaining cofactor
228 : will be printed after last curve */
229 20 : printf (" ");
230 :
231 : /* check for champions (top ten for each method) */
232 31 : method1 = ((method == ECM_PP1) && (result < 0)) ?
233 1347 : ECM_PM1 : method;
234 1316 : if ((verbose > 0) && factor_is_prime &&
235 1260 : nb_digits (f) >= champion_digits[method1])
236 : {
237 1 : printf ("Report your potential champion to %s\n",
238 : champion_keeper[method1]);
239 1 : printf ("(see %s)\n", champion_url[method1]);
240 : }
241 :
242 : /* Take care of fully factoring this number,
243 : in case we are in deep mode */
244 1316 : if (n->isPrp)
245 889 : *cnt = 0; /* no more curve to perform */
246 :
247 1316 : if (!deep)
248 10 : *cnt = 0;
249 : }
250 : else
251 : {
252 613 : *cnt = 0; /* no more curve to perform */
253 613 : if (verbose > 0)
254 613 : printf ("Found input number N");
255 613 : printf ("\n");
256 613 : returncode = ECM_INPUT_NUMBER_FOUND;
257 : }
258 1929 : fflush (stdout);
259 :
260 1929 : mpz_clear (f);
261 1929 : return returncode;
262 : }
|
