Line data Source code
1 : /* GMP-ECM -- Integer factorization with ECM, P-1 and P+1 methods.
2 :
3 : Copyright 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011,
4 : 2012, 2016 Jim Fougeron, Laurent Fousse, Alexander Kruppa, Paul Zimmermann,
5 : Cyril Bouvier, David Cleaver
6 :
7 : This program is free software; you can redistribute it and/or modify
8 : it under the terms of the GNU General Public License as published by
9 : the Free Software Foundation; either version 3 of the License, or (at your
10 : option) any later version.
11 :
12 : This program is distributed in the hope that it will be useful, but
13 : WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 : or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
15 : more details.
16 :
17 : You should have received a copy of the GNU General Public License
18 : along with this program; see the file COPYING. If not, see
19 : http://www.gnu.org/licenses/ or write to the Free Software Foundation, Inc.,
20 : 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA. */
21 :
22 : #include <stdio.h>
23 : #include <stdlib.h>
24 : #include <string.h>
25 : #include <time.h>
26 : #include <math.h>
27 : #ifdef _MSC_VER
28 : # include <winsock2.h>
29 : #endif
30 : #include "ecm-impl.h"
31 : #include "ecm-ecm.h"
32 :
33 : #include "config.h"
34 :
35 : #ifdef HAVE_UNISTD_H /* for access() */
36 : # include <unistd.h>
37 : #else
38 : # define F_OK 0
39 : # ifdef HAVE_IO_H
40 : # include <io.h>
41 : # endif
42 : #endif
43 :
44 : #ifdef HAVE_SIGNAL_H
45 : # include <signal.h>
46 : #endif
47 :
48 : #ifdef HAVE_GWNUM
49 : /* For GWNUM_VERSION */
50 : #include "gwnum.h"
51 : #endif
52 :
53 : /* Used in print_config() */
54 : #include "ecm-params.h"
55 :
56 : #ifdef HAVE_TORSION
57 : #include "torsions.h" /* to benefit from more torsion groups */
58 : #endif
59 :
60 :
61 : /* #define DEBUG */
62 :
63 : static int exit_asap_value = 0;
64 : static int exit_asap_signalnr = 0; /* Remembers which signal we received */
65 :
66 : void
67 0 : signal_handler (int sig)
68 : {
69 0 : if (sig == SIGINT || sig == SIGTERM)
70 : {
71 0 : exit_asap_value = 1;
72 0 : exit_asap_signalnr = sig;
73 : /* If one of these two signals arrives again, we'll let the default
74 : handler take over, which will usually terminate the process
75 : immediately. */
76 0 : signal (SIGINT, SIG_DFL);
77 0 : signal (SIGTERM, SIG_DFL);
78 : }
79 0 : }
80 :
81 : int
82 712213 : stop_asap_test ()
83 : {
84 712213 : return exit_asap_value;
85 : }
86 :
87 : static void
88 10 : usage (void)
89 : {
90 10 : printf ("Usage: ecm [options] B1 [[B2min-]B2] < file\n");
91 10 : printf ("\nParameters:\n");
92 10 : printf (" B1 stage 1 bound\n");
93 10 : printf (" B2 stage 2 bound (or interval B2min-B2max)\n");
94 10 : printf ("\nOptions:\n");
95 10 : printf (" -x0 x use x as initial point\n");
96 10 : printf (" -y0 y use y as initial point (Weierstrass form)\n");
97 10 : printf (" -param i which parametrization should be used [ecm]\n");
98 10 : printf (" -sigma s use s as parameter to compute curve's coefficients"
99 : "\n can use -sigma i:s to specify -param i at the same"
100 : " time [ecm]\n");
101 10 : printf (" -A A use A as a curve coefficient [ecm, see README]\n");
102 10 : printf (" -torsion T to generate a curve with torsion group T "
103 : "[ecm, see README]\n");
104 10 : printf (" -k n perform >= n steps in stage 2\n");
105 10 : printf (" -power n use x^n for Brent-Suyama's extension\n");
106 10 : printf (" -dickson n use n-th Dickson's polynomial for Brent-Suyama's extension\n");
107 10 : printf (" -c n perform n runs for each input\n");
108 10 : printf (" -pm1 perform P-1 instead of ECM\n");
109 10 : printf (" -pp1 perform P+1 instead of ECM\n");
110 10 : printf (" -q quiet mode\n");
111 10 : printf (" -v verbose mode\n");
112 10 : printf (" -timestamp print a time stamp with each number\n");
113 10 : printf (" -mpzmod use GMP's mpz_mod for modular reduction\n");
114 10 : printf (" -modmuln use Montgomery's MODMULN for modular reduction\n");
115 10 : printf (" -redc use Montgomery's REDC for modular reduction\n");
116 10 : printf (" -nobase2 disable special base-2 code\n");
117 10 : printf (" -nobase2s2 disable special base-2 code in ecm stage 2 only\n");
118 10 : printf (" -base2 n force base 2 mode with 2^n+1 (n>0) or 2^|n|-1 (n<0)\n");
119 10 : printf (" -ntt enable NTT convolution routines in stage 2\n");
120 10 : printf (" -no-ntt disable NTT convolution routines in stage 2\n");
121 10 : printf (" -save file save residues at end of stage 1 to file\n");
122 10 : printf (" -savea file like -save, appends to existing files\n");
123 10 : printf (" -resume file resume residues from file, reads from stdin if file is \"-\"\n");
124 10 : printf (" -chkpnt file save periodic checkpoints during stage 1 to file (for -param 0)\n");
125 10 : printf (" -primetest perform a primality test on input\n");
126 10 : printf (" -treefile f [ECM only] store stage 2 data in files f.0, ... \n");
127 10 : printf (" -maxmem n use at most n MB of memory in stage 2\n");
128 10 : printf (" -stage1time n add n seconds to ECM stage 1 time (for expected time est.)\n");
129 :
130 10 : printf (" -I f increment B1 by f*sqrt(B1) on each run\n");
131 10 : printf (" -inp file Use file as input (instead of redirecting stdin)\n");
132 10 : printf (" -one Stop processing a candidate if a factor is found (looping mode)\n");
133 10 : printf (" -go val Preload with group order val, which can be a simple expression,\n");
134 10 : printf (" or can use N as a placeholder for the number being factored.\n");
135 10 : printf (" -printconfig Print compile-time configuration and exit.\n");
136 :
137 10 : printf (" -bsaves file With -param 1-3, save stage 1 exponent in file.\n");
138 10 : printf (" -bloads file With -param 1-3, load stage 1 exponent from file.\n");
139 : #ifdef WITH_GPU
140 : printf (" -gpu Use GPU-ECM for stage 1.\n");
141 : #if HAVE_CGBN_H
142 : printf (" -cgbn Use CGBN for GPU-ECM stage 1 computation.\n");
143 : #endif /* HAVE_CGBN_H */
144 : printf (" -gpudevice n Use device n to execute GPU code (by default, "
145 : "CUDA chooses)\n");
146 : printf (" -gpucurves n Compute on n curves in parallel on the GPU (by "
147 : "default, CUDA chooses)\n");
148 : #endif /* WITH_GPU */
149 10 : printf (" -h, --help Prints this help and exit.\n");
150 10 : }
151 :
152 : /* Print parameters that were used to build GMP-ECM */
153 : static void
154 33 : print_config ()
155 : {
156 33 : printf ("Compilation options:\n");
157 : #ifdef __MPIR_VERSION
158 : printf ("Included MPIR header files version %d.%d.%d\n",
159 : __MPIR_VERSION, __MPIR_VERSION_MINOR, __MPIR_VERSION_PATCHLEVEL);
160 : #else /* __MPIR_VERSION */
161 : #ifdef __GNU_MP_VERSION_PATCHLEVEL
162 33 : printf ("Included GMP header files version %d.%d.%d\n",
163 : __GNU_MP_VERSION, __GNU_MP_VERSION_MINOR,
164 : __GNU_MP_VERSION_PATCHLEVEL);
165 : #else
166 : printf ("Included GMP header files version %d.%d\n",
167 : __GNU_MP_VERSION, __GNU_MP_VERSION_MINOR);
168 : #endif
169 : #endif /* __MPIR_VERSION */
170 33 : printf ("GMP_NUMB_BITS = %u\n", GMP_NUMB_BITS);
171 :
172 : #ifdef ECM_TUNE_CASE
173 33 : printf ("Tuning parameters from %s\n", ECM_TUNE_CASE);
174 : #else
175 : printf ("ECM_TUNE_CASE not defined.\n");
176 : #endif
177 :
178 : #ifdef GWNUM_VERSION
179 : printf ("Included GWNUM header files version %s\n", GWNUM_VERSION);
180 : #else
181 33 : printf ("GWNUM_VERSION undefined\n");
182 : #endif
183 :
184 : #ifdef HAVE_SSE2
185 : printf ("HAVE_SSE2 = %d\n", HAVE_SSE2);
186 : #else
187 33 : printf ("HAVE_SSE2 undefined\n");
188 : #endif
189 :
190 : #ifdef HAVE___GMPN_ADD_NC
191 33 : printf ("HAVE___GMPN_ADD_NC = %d\n", HAVE___GMPN_ADD_NC);
192 : #else
193 : printf ("HAVE___GMPN_ADD_NC undefined\n");
194 : #endif
195 :
196 : #ifdef HAVE___GMPN_MOD_34LSUB1
197 33 : printf ("HAVE___GMPN_MOD_34LSUB1 = %d\n", HAVE___GMPN_MOD_34LSUB1);
198 : #else
199 : printf ("HAVE___GMPN_MOD_34LSUB1 undefined\n");
200 : #endif
201 :
202 : #ifdef HAVE___GMPN_REDC_1
203 33 : printf ("HAVE___GMPN_REDC_1 = %d\n", HAVE___GMPN_REDC_1);
204 : #else
205 : printf ("HAVE___GMPN_REDC_1 undefined\n");
206 : #endif
207 :
208 : #ifdef USE_ASM_REDC
209 33 : printf ("USE_ASM_REDC = %d\n", USE_ASM_REDC);
210 : #ifdef WINDOWS64_ABI
211 : printf ("WINDOWS64_ABI = %d\n", WINDOWS64_ABI);
212 : #else
213 33 : printf ("WINDOWS64_ABI undefined\n");
214 : #endif
215 : #else
216 : printf ("USE_ASM_REDC undefined\n");
217 : #endif
218 :
219 : #ifdef WANT_ASSERT
220 : printf ("WANT_ASSERT = %d\n", WANT_ASSERT);
221 : #else
222 33 : printf ("WANT_ASSERT undefined\n");
223 : #endif
224 :
225 : #ifdef _OPENMP
226 : printf ("_OPENMP = %d\n", _OPENMP);
227 : #else
228 33 : printf ("_OPENMP undefined\n");
229 : #endif
230 :
231 : #ifdef MPZMOD_THRESHOLD
232 33 : printf ("MPZMOD_THRESHOLD = %d\n", MPZMOD_THRESHOLD);
233 : #else
234 : printf ("MPZMOD_THRESHOLD undefined\n");
235 : #endif
236 :
237 : #ifdef REDC_THRESHOLD
238 33 : printf ("REDC_THRESHOLD = %d\n", REDC_THRESHOLD);
239 : #else
240 : printf ("REDC_THRESHOLD undefined\n");
241 : #endif
242 :
243 : #ifdef MUL_NTT_THRESHOLD
244 33 : printf ("MUL_NTT_THRESHOLD = %d\n", MUL_NTT_THRESHOLD);
245 : #else
246 : printf ("MUL_NTT_THRESHOLD undefined\n");
247 : #endif
248 :
249 : #ifdef NTT_GFP_TWIDDLE_DIF_BREAKOVER
250 33 : printf ("NTT_GFP_TWIDDLE_DIF_BREAKOVER = %d\n",
251 : NTT_GFP_TWIDDLE_DIF_BREAKOVER);
252 : #else
253 : printf ("NTT_GFP_TWIDDLE_DIF_BREAKOVER undefined\n");
254 : #endif
255 :
256 : #ifdef NTT_GFP_TWIDDLE_DIT_BREAKOVER
257 33 : printf ("NTT_GFP_TWIDDLE_DIT_BREAKOVER = %d\n",
258 : NTT_GFP_TWIDDLE_DIT_BREAKOVER);
259 : #else
260 : printf ("NTT_GFP_TWIDDLE_DIT_BREAKOVER undefined\n");
261 : #endif
262 :
263 : #ifdef PREREVERTDIVISION_NTT_THRESHOLD
264 33 : printf ("PREREVERTDIVISION_NTT_THRESHOLD = %d\n",
265 : PREREVERTDIVISION_NTT_THRESHOLD);
266 : #else
267 : printf ("PREREVERTDIVISION_NTT_THRESHOLD undefined\n");
268 : #endif
269 :
270 : #ifdef POLYINVERT_NTT_THRESHOLD
271 33 : printf ("POLYINVERT_NTT_THRESHOLD = %d\n", POLYINVERT_NTT_THRESHOLD);
272 : #else
273 : printf ("POLYINVERT_NTT_THRESHOLD undefined\n");
274 : #endif
275 :
276 : #ifdef POLYEVALT_NTT_THRESHOLD
277 33 : printf ("POLYEVALT_NTT_THRESHOLD = %d\n", POLYEVALT_NTT_THRESHOLD);
278 : #else
279 : printf ("POLYEVALT_NTT_THRESHOLD undefined\n");
280 : #endif
281 :
282 : #ifdef MPZSPV_NORMALISE_STRIDE
283 33 : printf ("MPZSPV_NORMALISE_STRIDE = %d\n", MPZSPV_NORMALISE_STRIDE);
284 : #else
285 : printf ("MPZSPV_NORMALISE_STRIDE undefined\n");
286 : #endif
287 :
288 : #ifdef WITH_GPU
289 : printf ("WITH_GPU = %d\n", WITH_GPU);
290 : #else
291 33 : printf ("WITH_GPU undefined\n");
292 : #endif
293 :
294 33 : }
295 :
296 : /* r <- q mod N.
297 : Return value: 1 if den invertible, 0 if factor found; in this case
298 : gcd(den(q), N) is put in r.
299 : */
300 : static int
301 925 : mod_from_mpq (mpz_t r, mpq_t q, mpz_t N, int verbose)
302 : {
303 : mpz_t inv, C;
304 925 : int factor_is_prime, cofactor_is_prime, ret = ECM_NO_FACTOR_FOUND;
305 :
306 925 : mpz_init (inv);
307 925 : if (mpz_invert (inv, mpq_denref (q), N) == 0)
308 : {
309 60 : mpz_gcd (r, mpq_denref (q), N);
310 60 : if (verbose > 0)
311 : {
312 60 : if (verbose > 1)
313 10 : printf ("Warning: factor found during initialization\n");
314 60 : printf ("********** Factor found in step 1: ");
315 : }
316 60 : mpz_out_str (stdout, 10, r);
317 60 : if (verbose > 0)
318 60 : printf ("\n");
319 60 : if (mpz_cmp (r, N) == 0)
320 10 : ret = ECM_INPUT_NUMBER_FOUND;
321 : else
322 : {
323 50 : factor_is_prime = mpz_probab_prime_p (r, PROBAB_PRIME_TESTS);
324 50 : mpz_init (C);
325 50 : mpz_tdiv_q (C, N, r);
326 50 : cofactor_is_prime = mpz_probab_prime_p (C, PROBAB_PRIME_TESTS);
327 50 : mpz_clear (C);
328 50 : if (factor_is_prime)
329 40 : ret = cofactor_is_prime ? ECM_PRIME_FAC_PRIME_COFAC :
330 : ECM_PRIME_FAC_COMP_COFAC;
331 : else
332 10 : ret = cofactor_is_prime ? ECM_COMP_FAC_PRIME_COFAC :
333 : ECM_COMP_FAC_COMP_COFAC;
334 : }
335 : }
336 : else
337 : {
338 865 : mpz_mul (inv, mpq_numref (q), inv);
339 865 : mpz_mod (r, inv, N);
340 : }
341 925 : mpz_clear (inv);
342 925 : return ret;
343 : }
344 :
345 : /******************************************************************************
346 : * *
347 : * Main program *
348 : * *
349 : ******************************************************************************/
350 :
351 : int
352 3116 : main (int argc, char *argv[])
353 : {
354 3116 : char **argv0 = argv;
355 : mpz_t x, y, sigma, A, f, orig_x0, orig_y0, B2, B2min, startingB2min, tmp_n;
356 : mpcandi_t n;
357 : mpgocandi_t go;
358 : mpq_t rat_x0, rat_y0, rat_A;
359 : mpz_t numer_A, denom_A; /* used in Hessian stuff */
360 : double B1, B1done;
361 3116 : int result, returncode = 0;
362 3116 : int verbose = OUTPUT_NORMAL; /* verbose level */
363 3116 : int timestamp = 0;
364 3116 : int method = ECM_ECM;
365 3116 : int use_ntt = 1; /* Default, use NTT if input is small enough */
366 3116 : int specific_x0 = 0, /* 1=starting point supplied by user, 0=random or */
367 : /* compute from sigma */
368 3116 : specific_y0 = 0, /* was y0 given by the user? */
369 3116 : specific_A = 0, /* one may want its own A, including A=0 */
370 3116 : specific_sigma = 0; /* 0=make random */
371 : /* 1=sigma from command line */
372 3116 : int repr = ECM_MOD_DEFAULT; /* automatic choice */
373 3116 : int nobase2step2 = 0; /* flag to turn off base 2 arithmetic in ecm stage 2 */
374 3116 : unsigned long k = ECM_DEFAULT_K; /* default number of blocks in stage 2 */
375 3116 : int S = ECM_DEFAULT_S;
376 : /* Degree for Brent-Suyama extension requested by user.
377 : Positive value: use S-th power,
378 : negative: use degree |S| Dickson poly,
379 : default (0): automatic choice. */
380 3116 : char *savefilename = NULL, *resumefilename = NULL, *infilename = NULL;
381 3116 : char *TreeFilename = NULL, *chkfilename = NULL;
382 : #ifdef HAVE_TORSION
383 3116 : char *torsion = NULL;
384 : #endif
385 3116 : char rtime[256] = "", who[256] = "", comment[256] = "", program[256] = "";
386 3116 : FILE *resumefile = NULL, *infile = NULL;
387 : mpz_t resume_lastN, resume_lastfac; /* When resuming residues from a file,
388 : store the last number processed and the factors found for this it */
389 3116 : int resume_wasPrp = 0; /* 1 if resume_lastN/resume_lastfac is a PRP */
390 3116 : int primetest = 0, saveappend = 0;
391 3116 : double autoincrementB1 = 0.0, startingB1;
392 3116 : unsigned int count = 1; /* number of curves for each number */
393 3116 : unsigned int cnt = 0; /* number of remaining curves for current number */
394 3116 : int deep=1;
395 3116 : double maxmem = 0.;
396 3116 : double stage1time = 0.;
397 : ecm_params params;
398 3116 : int param = ECM_PARAM_DEFAULT; /* automatic choice */
399 3116 : char *savefile_s = NULL;
400 3116 : char *loadfile_s = NULL;
401 : #ifdef HAVE_GWNUM
402 : double gw_k = 0.0; /* set default values for gwnum poly k*b^n+c */
403 : unsigned long gw_b = 0; /* set default values for gwnum poly k*b^n+c */
404 : unsigned long gw_n = 0; /* set default values for gwnum poly k*b^n+c */
405 : signed long gw_c = 0; /* set default values for gwnum poly k*b^n+c */
406 : #endif
407 3116 : int use_gpu = 0; /* Do we use the GPU for stage 1 (by default no) */
408 3116 : int gpucgbn = 0; /* Do we use CGBN for stage 1 GPU computation (by default no) */
409 3116 : int gpudevice = -1; /* Which device do we use for GPU code (by default CUDA */
410 : /* chooses) */
411 3116 : unsigned int gpucurves = 0; /* How many curves do we want for GPU code */
412 : /* (by default CUDA chooses) */
413 :
414 : /* check ecm is linked with a compatible library */
415 3116 : if (mp_bits_per_limb != GMP_NUMB_BITS)
416 : {
417 0 : fprintf (stderr, "Error, mp_bits_per_limb and GMP_NUMB_BITS differ\n");
418 0 : fprintf (stderr, "Please check your LD_LIBRARY_PATH variable\n");
419 0 : exit (1);
420 : }
421 :
422 3116 : ecm_init (params);
423 :
424 : /* initialize the group order candidate */
425 3116 : mpgocandi_t_init (&go);
426 :
427 : /* Init variables we might need to store options */
428 3116 : mpz_init (sigma);
429 3116 : mpz_init (A);
430 3116 : mpz_init (B2);
431 3116 : mpz_init (B2min);
432 3116 : mpz_init (startingB2min);
433 3116 : mpq_init (rat_A);
434 3116 : mpq_init (rat_x0);
435 3116 : mpq_init (rat_y0);
436 :
437 : /* first look for options */
438 10722 : while ((argc > 1) && (argv[1][0] == '-'))
439 : {
440 7749 : if (strcmp (argv[1], "-pm1") == 0)
441 : {
442 277 : method = ECM_PM1;
443 277 : argv++;
444 277 : argc--;
445 : }
446 7472 : else if (strcmp (argv[1], "-pp1") == 0)
447 : {
448 284 : method = ECM_PP1;
449 284 : argv++;
450 284 : argc--;
451 : }
452 7188 : else if (strcmp (argv[1], "-q") == 0)
453 : {
454 20 : verbose = OUTPUT_ALWAYS;
455 20 : argv++;
456 20 : argc--;
457 : }
458 7168 : else if (strcmp (argv[1], "-v") == 0)
459 : {
460 312 : verbose ++;
461 312 : argv++;
462 312 : argc--;
463 : }
464 6856 : else if (strcmp (argv[1], "-timestamp") == 0)
465 : {
466 10 : timestamp = 1;
467 10 : argv++;
468 10 : argc--;
469 : }
470 6846 : else if (strcmp (argv[1], "-mpzmod") == 0)
471 : {
472 342 : repr = ECM_MOD_MPZ;
473 342 : argv++;
474 342 : argc--;
475 : }
476 6504 : else if (strcmp (argv[1], "-modmuln") == 0)
477 : {
478 373 : repr = ECM_MOD_MODMULN;
479 373 : argv++;
480 373 : argc--;
481 : }
482 6131 : else if (strcmp (argv[1], "-redc") == 0)
483 : {
484 347 : repr = ECM_MOD_REDC;
485 347 : argv++;
486 347 : argc--;
487 : }
488 5784 : else if (strcmp (argv[1], "-nobase2") == 0)
489 : {
490 20 : repr = ECM_MOD_NOBASE2;
491 20 : argv++;
492 20 : argc--;
493 : }
494 5764 : else if (strcmp (argv[1], "-nobase2s2") == 0)
495 : {
496 20 : nobase2step2 = 1;
497 20 : argv++;
498 20 : argc--;
499 : }
500 5744 : else if (strcmp (argv[1], "-ntt") == 0)
501 : {
502 35 : use_ntt = 2; /* Use NTT, even for large input numbers */
503 35 : argv++;
504 35 : argc--;
505 : }
506 5709 : else if (strcmp (argv[1], "-no-ntt") == 0)
507 : {
508 388 : use_ntt = 0; /* Never use NTT */
509 388 : argv++;
510 388 : argc--;
511 : }
512 5321 : else if (strcmp (argv[1], "-primetest") == 0)
513 : {
514 20 : primetest = 1;
515 20 : argv++;
516 20 : argc--;
517 : }
518 5301 : else if (strcmp (argv[1], "-one") == 0)
519 : {
520 10 : deep = 0;
521 10 : argv++;
522 10 : argc--;
523 : }
524 5291 : else if ((argc > 2) && (strcmp (argv[1], "-bsaves") == 0))
525 : {
526 38 : savefile_s = argv[2];
527 38 : argv += 2;
528 38 : argc -= 2;
529 : }
530 5253 : else if ((argc > 2) && (strcmp (argv[1], "-bloads") == 0))
531 : {
532 86 : loadfile_s = argv[2];
533 86 : argv += 2;
534 86 : argc -= 2;
535 : }
536 5167 : else if (strcmp (argv[1], "-h") == 0 || strcmp (argv[1], "--help") == 0)
537 : {
538 10 : usage ();
539 10 : goto free_all;
540 : }
541 5157 : else if (strcmp (argv[1], "-printconfig") == 0)
542 : {
543 33 : print_config ();
544 33 : goto free_all;
545 : }
546 5124 : else if ((argc > 2) && (strcmp (argv[1], "-x0")) == 0)
547 : {
548 519 : if (mpq_set_str (rat_x0, argv[2], 0))
549 : {
550 10 : fprintf (stderr, "Error, invalid starting point: %s\n", argv[2]);
551 10 : exit (EXIT_FAILURE);
552 : }
553 509 : specific_x0 = 1;
554 509 : argv += 2;
555 509 : argc -= 2;
556 : }
557 4605 : else if ((argc > 2) && (strcmp (argv[1], "-y0")) == 0)
558 : {
559 230 : if (mpq_set_str (rat_y0, argv[2], 0))
560 : {
561 10 : fprintf (stderr, "Error, invalid starting point: %s\n", argv[2]);
562 10 : exit (EXIT_FAILURE);
563 : }
564 220 : specific_y0 = 1;
565 220 : argv += 2;
566 220 : argc -= 2;
567 : }
568 4375 : else if ((argc > 2) && (strcmp (argv[1], "-param")) == 0)
569 : {
570 : /* atoi does not allow use to distinct from */
571 : /* '-param 0' and '-param -otherargs' as it will always return 0 */
572 1070 : if (argv[2][0] == '-')
573 : {
574 10 : fprintf (stderr, "Error, invalid -param value: %s\n", argv[2]);
575 10 : exit (EXIT_FAILURE);
576 : }
577 : /* If param was already set (by -sigma i:x), we should check that */
578 : /* the same value is passed with -param */
579 1060 : if (param != ECM_PARAM_DEFAULT)
580 : {
581 10 : if (param != atoi (argv[2]))
582 : {
583 10 : fprintf (stderr, "Error, conflict between -sigma and -param "
584 : "arguments\n");
585 10 : exit (EXIT_FAILURE);
586 : }
587 : }
588 : else
589 1050 : param = atoi (argv[2]);
590 1050 : argv += 2;
591 1050 : argc -= 2;
592 : }
593 3305 : else if ((argc > 2) && (strcmp (argv[1], "-sigma")) == 0)
594 : {
595 : /* Accept stuff like '-sigma i:s', this is equivalent to */
596 : /* '-param i -sigma s'. If we have only -sigma s and param is not */
597 : /* yet defined we assumed this is 0 (for compatibility reason) */
598 1473 : if (argv[2][1] == ':')
599 : {
600 457 : argv[2][1] = '\0';
601 : /* If param was already set (by -param i:x), we should check */
602 : /* that the same value is passed with -sigma */
603 457 : if (param != ECM_PARAM_DEFAULT)
604 : {
605 10 : if (param != atoi (argv[2]))
606 : {
607 10 : fprintf (stderr, "Error, conflict between -sigma and "
608 : "-param arguments\n");
609 10 : exit (EXIT_FAILURE);
610 : }
611 : }
612 : else
613 447 : param = atoi (argv[2]) ;
614 :
615 447 : if (mpz_set_str (sigma, argv[2]+2, 0) || mpz_sgn (sigma) == 0)
616 : {
617 0 : fprintf (stderr, "Error, invalid sigma value: %s\n",
618 0 : argv[2]+2);
619 0 : exit (EXIT_FAILURE);
620 : }
621 : }
622 : else
623 : {
624 1016 : if (param == ECM_PARAM_DEFAULT)
625 402 : param = ECM_PARAM_SUYAMA;
626 1016 : if (mpz_set_str (sigma, argv[2], 0))
627 : {
628 10 : fprintf (stderr, "Error, invalid sigma value: %s\n", argv[2]);
629 10 : exit (EXIT_FAILURE);
630 : }
631 : }
632 1453 : specific_sigma = 1;
633 1453 : argv += 2;
634 1453 : argc -= 2;
635 : }
636 1832 : else if ((argc > 2) && (strcmp (argv[1], "-A")) == 0)
637 : {
638 316 : if (mpq_set_str (rat_A, argv[2], 0))
639 : {
640 10 : fprintf (stderr, "Error, invalid A value: %s\n", argv[2]);
641 10 : exit (EXIT_FAILURE);
642 : }
643 306 : specific_A = 1;
644 306 : argv += 2;
645 306 : argc -= 2;
646 : }
647 : #ifdef HAVE_TORSION
648 1516 : else if ((argc > 2) && (strcmp (argv[1], "-torsion")) == 0)
649 : {
650 380 : torsion = argv[2];
651 380 : argv += 2;
652 380 : argc -= 2;
653 : }
654 : #endif
655 1136 : else if ((argc > 2) && (strcmp (argv[1], "-power")) == 0)
656 : {
657 10 : S = abs (atoi (argv[2]));
658 : /* should this be validated? and a error/abort issued if 0 ??? */
659 10 : argv += 2;
660 10 : argc -= 2;
661 : }
662 1126 : else if ((argc > 2) && (strcmp (argv[1], "-dickson") == 0))
663 : {
664 0 : S = - abs ( atoi (argv[2]));
665 : /* should this be validated? and a error/abort issued if 0 ??? */
666 0 : argv += 2;
667 0 : argc -= 2;
668 : }
669 1126 : else if ((argc > 2) && (strcmp (argv[1], "-k") == 0))
670 : {
671 151 : k = atol (argv[2]);
672 : /* should this be validated? and a error/abort issued if 0 ??? */
673 151 : argv += 2;
674 151 : argc -= 2;
675 : }
676 975 : else if ((argc > 2) && (strcmp (argv[1], "-c") == 0))
677 : {
678 70 : count = atoi (argv[2]);
679 : /* should this be validated? and a error/abort issued if 0 ??? */
680 70 : argv += 2;
681 70 : argc -= 2;
682 : }
683 905 : else if ((argc > 2) && (strcmp (argv[1], "-save") == 0))
684 : {
685 40 : savefilename = argv[2];
686 40 : saveappend = 0;
687 40 : argv += 2;
688 40 : argc -= 2;
689 : }
690 865 : else if ((argc > 2) && (strcmp (argv[1], "-savea") == 0))
691 : {
692 15 : savefilename = argv[2];
693 15 : saveappend = 1;
694 15 : argv += 2;
695 15 : argc -= 2;
696 : }
697 850 : else if ((argc > 2) && (strcmp (argv[1], "-resume") == 0))
698 : {
699 217 : resumefilename = argv[2];
700 217 : argv += 2;
701 217 : argc -= 2;
702 : }
703 633 : else if ((argc > 2) && (strcmp (argv[1], "-chkpnt") == 0))
704 : {
705 20 : chkfilename = argv[2];
706 20 : argv += 2;
707 20 : argc -= 2;
708 : }
709 613 : else if ((argc > 2) && (strcmp (argv[1], "-treefile") == 0))
710 : {
711 270 : TreeFilename = argv[2];
712 270 : argv += 2;
713 270 : argc -= 2;
714 : }
715 343 : else if ((argc > 2) && (strcmp (argv[1], "-base2") == 0))
716 20 : {
717 20 : int b = atoi (argv[2]);
718 20 : if (abs (b) >= 16) /* |Values| < 16 are reserved for other methods */
719 20 : repr = b; /* keep method unchanged in that case */
720 20 : argv += 2;
721 20 : argc -= 2;
722 : }
723 323 : else if ((argc > 2) && (strcmp (argv[1], "-I") == 0))
724 : {
725 40 : autoincrementB1 = strtod (argv[2], NULL);
726 40 : if (autoincrementB1 <= 0.0)
727 : {
728 10 : fprintf (stderr, "Error, the -I f option requires f > 0\n");
729 10 : exit (EXIT_FAILURE);
730 : }
731 30 : argv += 2;
732 30 : argc -= 2;
733 : }
734 283 : else if ((argc > 2) && (strcmp (argv[1], "-inp") == 0))
735 : {
736 30 : infilename = argv[2];
737 30 : infile = fopen (infilename, "r");
738 30 : if (!infile)
739 : {
740 10 : fprintf (stderr, "Can't find input file %s\n", infilename);
741 10 : exit (EXIT_FAILURE);
742 : }
743 20 : argv += 2;
744 20 : argc -= 2;
745 : }
746 253 : else if ((argc > 2) && (strcmp (argv[1], "-maxmem") == 0))
747 : {
748 52 : maxmem = atof (argv[2]) * 1048576.;
749 52 : ASSERT_ALWAYS (maxmem >= 0.0);
750 52 : argv += 2;
751 52 : argc -= 2;
752 : }
753 201 : else if ((argc > 2) && (strcmp (argv[1], "-stage1time") == 0))
754 : {
755 10 : stage1time = atof (argv[2]);
756 10 : argv += 2;
757 10 : argc -= 2;
758 : }
759 191 : else if ((argc > 2) && (strcmp (argv[1], "-go") == 0))
760 : {
761 181 : if (go.cpOrigExpr)
762 : {
763 10 : fprintf (stderr, "Warning, for multiple -go options, only the last one is taken into account.\n");
764 10 : free (go.cpOrigExpr);
765 : }
766 181 : go.cpOrigExpr = malloc (strlen (argv[2]) + 1);
767 181 : if (go.cpOrigExpr == NULL)
768 : {
769 0 : fprintf (stderr, "Cannot allocate memory in main\n");
770 0 : exit (1);
771 : }
772 181 : strcpy (go.cpOrigExpr, argv[2]);
773 181 : if (strchr (go.cpOrigExpr, 'N'))
774 : {
775 15 : go.containsN = 1;
776 15 : go.Valid = 1; /* we actually do not know if it is valid here,
777 : but we "assume" until the first time it gets
778 : run through */
779 : }
780 : else
781 : {
782 166 : go.containsN = 0; /* have "fully" parsed expr or number.
783 : Do not recompute for each N */
784 166 : if (eval_str (&(go.Candi), go.cpOrigExpr, 0, NULL))
785 166 : go.Valid = 1;
786 : }
787 181 : argv += 2;
788 181 : argc -= 2;
789 : }
790 : #ifdef WITH_GPU
791 : else if (strcmp (argv[1], "-gpu") == 0)
792 : {
793 : use_gpu = 1;
794 : argv++;
795 : argc--;
796 : }
797 : else if (strcmp (argv[1], "-cgbn") == 0)
798 : {
799 : use_gpu = 1;
800 : gpucgbn = 1;
801 : #ifndef HAVE_CGBN_H
802 : fprintf (stderr, "CGBN not present; configure with --with-cgbn-include\n");
803 : exit (EXIT_FAILURE);
804 : #endif /* !HAVE_CGBN_H */
805 : argv++;
806 : argc--;
807 : }
808 : else if ((argc > 2) && (strcmp (argv[1], "-gpudevice") == 0))
809 : {
810 : gpudevice = atoi (argv[2]);
811 : argv += 2;
812 : argc -= 2;
813 : }
814 : else if ((argc > 2) && (strcmp (argv[1], "-gpucurves") == 0))
815 : {
816 : gpucurves = atoi (argv[2]);
817 : argv += 2;
818 : argc -= 2;
819 : }
820 : #endif
821 : else
822 : {
823 10 : fprintf (stderr, "Unknown option: %s\n", argv[1]);
824 10 : exit (EXIT_FAILURE);
825 : }
826 : }
827 :
828 2973 : if ((method == ECM_PM1 || method == ECM_PP1) && (S != ECM_DEFAULT_S && S != 1))
829 : {
830 0 : fprintf (stderr, "Error, %s not supported for %s\n",
831 0 : S < 0 ? "-dickson" : "-power", method == ECM_PM1 ? "-pm1" : "-pp1" );
832 0 : exit (EXIT_FAILURE);
833 : }
834 :
835 2973 : if (argc < 2)
836 : {
837 10 : fprintf (stderr, "Invalid arguments. See %s --help.\n", argv0[0]);
838 10 : exit (EXIT_FAILURE);
839 : }
840 :
841 2963 : if (strcmp (ecm_version (), ECM_VERSION) != 0)
842 : {
843 0 : fprintf (stderr, "Error, library version %s differs from header "
844 : "version %s with which this file was compiled\n",
845 : ecm_version (), ECM_VERSION);
846 0 : exit (EXIT_FAILURE);
847 : }
848 :
849 : /* start of the program */
850 2963 : if (verbose >= 1)
851 : {
852 : char Gmp_version[64];
853 2943 : char out0[128], *out = out0;
854 :
855 : #ifdef __MPIR_VERSION
856 : sprintf (Gmp_version, "MPIR %d.%d.%d", __MPIR_VERSION,
857 : __MPIR_VERSION_MINOR, __MPIR_VERSION_PATCHLEVEL);
858 : #else /* original GMP */
859 2943 : sprintf (Gmp_version, "GMP %s", gmp_version);
860 : #endif /* __MPIR_VERSION */
861 :
862 2943 : out += sprintf (out, "GMP-ECM %s [configured with %s",
863 : ecm_version (), Gmp_version);
864 :
865 : #ifdef HAVE_GWNUM
866 : out += sprintf (out, ", GWNUM %s", GWNUM_VERSION);
867 : #endif
868 :
869 : #ifdef USE_ASM_REDC
870 2943 : out += sprintf (out, ", --enable-asm-redc");
871 : #endif
872 :
873 : #ifdef WITH_GPU
874 : out += sprintf (out, ", --enable-gpu");
875 : #endif
876 :
877 : #ifdef WANT_ASSERT
878 : out += sprintf (out, ", --enable-assert");
879 : #endif
880 :
881 : #ifdef _OPENMP
882 : out += sprintf (out, ", --enable-openmp");
883 : #endif
884 :
885 2943 : printf ("%s] [", out0);
886 2943 : switch (method)
887 : {
888 277 : case ECM_PM1:
889 277 : printf ("P-1");
890 277 : break;
891 274 : case ECM_PP1:
892 274 : printf ("P+1");
893 274 : break;
894 2392 : default:
895 2392 : printf ("ECM");
896 : }
897 2943 : printf ("]\n");
898 : #ifdef ECM_TUNE_CASE
899 2943 : if (verbose >= 2)
900 162 : printf ("Tuned for %s\n", ECM_TUNE_CASE);
901 : #endif
902 : #ifdef HAVE_GETHOSTNAME
903 2943 : if (verbose >= 2)
904 : {
905 : #define MNAMESIZE 64
906 : char mname[MNAMESIZE];
907 162 : if (gethostname (mname, MNAMESIZE) == 0)
908 : {
909 162 : mname[MNAMESIZE - 1] = 0; /* gethostname() may omit trailing 0 */
910 162 : printf ("Running on %s\n", mname);
911 : }
912 : }
913 : #endif
914 :
915 : #ifdef HAVE_GWNUM
916 : #ifdef gwnum_is_gpl
917 : if (! gwnum_is_gpl ())
918 : #endif
919 : printf ("Due to incompatible licenses, this binary file must not "
920 : "be distributed.\n");
921 : #endif
922 : }
923 :
924 : /* set first stage bound B1 */
925 2963 : B1 = strtod (argv[1], &argv[1]);
926 2963 : if (*argv[1] == '-')
927 : {
928 10 : B1done = B1;
929 10 : B1 = strtod (argv[1] + 1, NULL);
930 : }
931 : else
932 2953 : B1done = ECM_DEFAULT_B1_DONE;
933 2963 : mpz_set_si (B2min, -1); /* default, means that B2min will be set to B1 by
934 : ecm(), pm1() and pp1() */
935 :
936 2963 : if (B1 < 0.0 || B1done < 0.0)
937 : {
938 0 : fprintf (stderr, "Bound values must be positive\n");
939 0 : exit (EXIT_FAILURE);
940 : }
941 :
942 : /* check B1 is not too large */
943 2963 : if (B1 > MAX_B1)
944 : {
945 0 : fprintf (stderr, "Too large stage 1 bound, limit is %1.0f\n", MAX_B1);
946 0 : exit (EXIT_FAILURE);
947 : }
948 :
949 2963 : init_expr ();
950 :
951 2963 : mpz_set_si (B2, ECM_DEFAULT_B2); /* compute it automatically from B1 */
952 : /* parse B2 or B2min-B2max */
953 2963 : if (argc >= 3)
954 : {
955 : int c;
956 : double d;
957 : char *endptr;
958 :
959 : /* This is like strtok, but SunOS does not seem to have it declared in
960 : any header files, in spite of saying it does in the man pages... */
961 7006 : for (endptr = argv[2]; *endptr != '\0' && *endptr != '-'; endptr++);
962 1157 : if (*endptr == '-')
963 160 : *(endptr++) = '\0';
964 : else
965 997 : endptr = NULL;
966 :
967 1157 : c = -1;
968 : {
969 : int r;
970 :
971 1157 : r = gmp_sscanf (argv[2], "%Zd%n", B2, &c); /* Try parsing as integer */
972 1157 : if (r <= 0)
973 : {
974 : /* restore original value */
975 10 : if (endptr != NULL)
976 10 : *(--endptr) = '-';
977 10 : fprintf (stderr, "Invalid B2 value: %s\n", argv[2]);
978 10 : exit (EXIT_FAILURE);
979 : }
980 : }
981 : #ifdef __MINGW32__
982 : /* MinGW scanf() returns a value 1 too high for %n */
983 : /* Reported to MinGW as bug number 1163607 */
984 : if (c > 0 && argv[2][c - 1] == 0)
985 : c--;
986 : #endif
987 :
988 1147 : if (c < 0 || argv[2][c] != '\0')
989 : {
990 189 : c = -1;
991 189 : gmp_sscanf (argv[2], "%lf%n", &d, &c); /* Try parsing scientific */
992 : #ifdef __MINGW32__
993 : if (c > 0 && argv[2][c - 1] == 0)
994 : c--;
995 : #endif
996 189 : mpz_set_d (B2, d);
997 : }
998 1147 : if (c < 0 || argv[2][c] != '\0' || argv[2][0] == '\0')
999 : /* If not the whole token could be parsed either way, or if there was
1000 : no token to begin with (i.e string starting with '-') signal error */
1001 0 : c = -1;
1002 1147 : else if (endptr != NULL) /* Did we have a '-' in there? */
1003 : {
1004 150 : mpz_set (B2min, B2);
1005 : /* make sure B2min is not less than B1 */
1006 150 : if (mpz_cmp_d (B2min, B1) < 0)
1007 70 : mpz_set_d (B2min, B1);
1008 :
1009 150 : c = -1;
1010 150 : gmp_sscanf (endptr, "%Zd%n", B2, &c);
1011 : #ifdef __MINGW32__
1012 : if (c > 0 && endptr[c - 1] == 0)
1013 : c--;
1014 : #endif
1015 150 : if (c < 0 || endptr[c] != '\0')
1016 : {
1017 100 : gmp_sscanf (endptr, "%lf%n", &d, &c);
1018 : #ifdef __MINGW32__
1019 : if (c > 0 && endptr[c - 1] == 0)
1020 : c--;
1021 : #endif
1022 100 : mpz_set_d (B2, d);
1023 : }
1024 150 : if (c < 0 || endptr[c] != '\0')
1025 0 : c = -1;
1026 : }
1027 1147 : if (c == -1)
1028 : {
1029 0 : fprintf (stderr, "Error: expected positive integer(s) B2 or "
1030 : "B2min-B2\n");
1031 0 : exit (EXIT_FAILURE);
1032 : }
1033 : }
1034 :
1035 : /* set static parameters (i.e. those that don't change during the program) */
1036 2953 : params->verbose = verbose;
1037 2953 : params->method = method;
1038 2953 : mpz_set (params->B2min, B2min);
1039 2953 : mpz_set (params->B2, B2);
1040 2953 : params->k = k;
1041 2953 : params->S = S;
1042 2953 : params->repr = repr;
1043 2953 : params->nobase2step2 = nobase2step2;
1044 2953 : params->chkfilename = chkfilename;
1045 2953 : params->TreeFilename = TreeFilename;
1046 2953 : params->maxmem = maxmem;
1047 2953 : params->stage1time = stage1time;
1048 2953 : params->gpu = use_gpu; /* If WITH_GPU is not defined it will always be 0 */
1049 2953 : params->gpu_cgbn = gpucgbn; /* If !HAVE_CGBN_H will always be 0 */
1050 2953 : params->gpu_device = gpudevice; /* If WITH_GPU is not defined or */
1051 : /* use_gpu = 0, it has no meaning */
1052 2953 : params->gpu_number_of_curves = gpucurves; /* If WITH_GPU is not defined or */
1053 : /* use_gpu = 0, it has no meaning*/
1054 :
1055 : /* Open resume file for reading, if resuming is requested */
1056 2953 : if (resumefilename != NULL)
1057 : {
1058 : /* -resume should not be used with -gpu */
1059 217 : if (use_gpu)
1060 : {
1061 0 : fprintf (stderr, "Error, -resume not allowed with -gpu\n");
1062 0 : exit (EXIT_FAILURE);
1063 : }
1064 217 : if (strcmp (resumefilename, "-") == 0)
1065 0 : resumefile = stdin;
1066 : else
1067 217 : resumefile = fopen (resumefilename, "r");
1068 :
1069 217 : if (resumefile == NULL)
1070 : {
1071 0 : fprintf (stderr, "Could not open file %s for reading\n",
1072 : resumefilename);
1073 0 : exit (EXIT_FAILURE);
1074 : }
1075 217 : mpz_init (resume_lastN);
1076 217 : mpz_init (resume_lastfac);
1077 217 : mpz_set_ui (resume_lastfac, 1);
1078 : }
1079 :
1080 : /* Open save file for writing, if saving is requested */
1081 2953 : if (savefilename != NULL)
1082 : {
1083 : FILE *savefile;
1084 : /* Are we not appending and does this file already exist ? */
1085 55 : if (!saveappend && access (savefilename, F_OK) == 0)
1086 : {
1087 0 : printf ("Save file %s already exists, will not overwrite\n",
1088 : savefilename);
1089 0 : exit (EXIT_FAILURE);
1090 : }
1091 : /* Test if we can open the file for writing */
1092 55 : savefile = fopen (savefilename, "a");
1093 55 : if (savefile == NULL)
1094 : {
1095 0 : fprintf (stderr, "Could not open file %s for writing\n", savefilename);
1096 0 : exit (EXIT_FAILURE);
1097 : }
1098 55 : fclose (savefile);
1099 : }
1100 :
1101 2953 : if (specific_sigma && (specific_x0 || specific_A))
1102 : {
1103 10 : fprintf (stderr, "Error, -sigma parameter is incompatible with "
1104 : "-A and -x0 parameters.\n");
1105 10 : exit (EXIT_FAILURE);
1106 : }
1107 :
1108 2943 : if (specific_y0 && (!specific_x0 || !specific_A))
1109 : {
1110 10 : fprintf (stderr, "Error, -y0 must be used with -A and -x0 parameters.\n");
1111 10 : exit (EXIT_FAILURE);
1112 : }
1113 :
1114 2933 : if (resumefile && (specific_sigma || param != ECM_PARAM_DEFAULT ||
1115 217 : specific_A || specific_x0))
1116 : {
1117 10 : printf ("Warning: -sigma, -param, -A and -x0 parameters are\n"
1118 : "ignored when resuming from save files.\n");
1119 10 : mpz_set_ui (sigma, 0);
1120 10 : specific_sigma = 0;
1121 10 : param = ECM_PARAM_DEFAULT;
1122 10 : mpz_set_ui (A, 0);
1123 10 : specific_x0 = 0;
1124 : }
1125 :
1126 2933 : mpcandi_t_init (&n); /* number(s) to factor */
1127 2933 : mpz_init (f); /* factor found */
1128 2933 : mpz_init (x); /* stage 1 residue */
1129 2933 : mpz_init (y); /* stage 1 for ECM_W or ECM_H */
1130 2933 : mpz_init (orig_x0); /* starting point, for save file */
1131 2933 : mpz_init (orig_y0); /* starting point, for save file */
1132 :
1133 : /* Install signal handlers */
1134 : #ifdef HAVE_SIGNAL
1135 : /* We catch signals only if there is a savefile. Otherwise there's nothing
1136 : we could save by exiting cleanly, but the waiting for the code to check
1137 : for signals may delay program end unacceptably */
1138 :
1139 2933 : if (savefilename != NULL)
1140 : {
1141 55 : signal (SIGINT, &signal_handler);
1142 55 : signal (SIGTERM, &signal_handler);
1143 55 : params->stop_asap = &stop_asap_test;
1144 : }
1145 : #endif
1146 :
1147 : /* loop for number in standard input or file */
1148 :
1149 2933 : startingB1 = B1;
1150 2933 : mpz_set (startingB2min, B2min);
1151 :
1152 2933 : if (!infilename)
1153 2913 : infile = stdin;
1154 :
1155 : /* Main loop */
1156 5260 : while ((cnt > 0 || feof (infile) == 0) && !exit_asap_value)
1157 : {
1158 5250 : result = ECM_NO_FACTOR_FOUND;
1159 5250 : params->B1done = B1done; /* may change with resume */
1160 :
1161 5250 : if (resumefile != NULL) /* resume case */
1162 : {
1163 324 : if (count != 1)
1164 : {
1165 10 : fprintf (stderr,
1166 : "Error, option -c and -resume are incompatible\n");
1167 10 : exit (EXIT_FAILURE);
1168 : }
1169 314 : if (!read_resumefile_line (&method, x, y, &n, sigma, A,
1170 314 : orig_x0, orig_y0, &(params->E->type),
1171 : &(params->param), &(params->B1done),
1172 : program, who, rtime, comment, resumefile))
1173 207 : break;
1174 :
1175 107 : if (params->E->type == ECM_EC_TYPE_WEIERSTRASS
1176 97 : || params->E->type == ECM_EC_TYPE_HESSIAN
1177 97 : || params->E->type == ECM_EC_TYPE_TWISTED_HESSIAN)
1178 10 : params->sigma_is_A = -1;
1179 : else
1180 97 : params->sigma_is_A = mpz_sgn (sigma) == 0; /* sure? */
1181 :
1182 107 : if (mpz_cmp (n.n, resume_lastN) == 0)
1183 : {
1184 : /* Aha, we're trying the same number again. */
1185 : /* We skip this attempt if: 1. the remaining cofactor after
1186 : the last attempt was a probable prime, or 2. if a factor
1187 : was found and the user gave the -one option */
1188 0 : if (resume_wasPrp ||
1189 0 : (deep == 0 && mpz_cmp_ui (resume_lastfac, 1) != 0))
1190 0 : continue;
1191 :
1192 : /* If we found a factor in an earlier attempt, divide it out */
1193 0 : if (mpz_cmp_ui (resume_lastfac, 1) > 0)
1194 0 : mpcandi_t_addfoundfactor (&n, resume_lastfac, 1);
1195 : }
1196 : else
1197 : {
1198 : /* It's a different number. Set resume_lastN and
1199 : resume_lastfac */
1200 107 : mpz_set (resume_lastN, n.n);
1201 107 : mpz_set_ui (resume_lastfac, 1);
1202 107 : resume_wasPrp = n.isPrp;
1203 : }
1204 :
1205 107 : cnt = count; /* i.e. 1 */
1206 :
1207 107 : if (verbose >= OUTPUT_NORMAL)
1208 : {
1209 107 : printf ("Resuming ");
1210 107 : if (method == ECM_ECM)
1211 72 : printf ("ECM");
1212 35 : else if (method == ECM_PM1)
1213 25 : printf ("P-1");
1214 10 : else if (method == ECM_PP1)
1215 10 : printf ("P+1");
1216 107 : printf (" residue ");
1217 107 : if (program[0] || who[0] || rtime[0])
1218 77 : printf ("saved ");
1219 107 : if (who[0])
1220 55 : printf ("by %s ", who);
1221 107 : if (program[0])
1222 77 : printf ("with %s ", program);
1223 107 : if (rtime[0])
1224 55 : printf ("on %s ", rtime);
1225 107 : if (comment[0])
1226 10 : printf ("(%s)", comment);
1227 107 : printf ("\n");
1228 : }
1229 : }
1230 : else /* no-resume case */
1231 : {
1232 4926 : if (cnt) /* nothing to read: reuse old number */
1233 : {
1234 56 : if (verbose >= OUTPUT_NORMAL)
1235 56 : printf ("Run %u out of %u:\n", count - cnt + 1, count);
1236 : }
1237 : else /* new number */
1238 : {
1239 4870 : if (!read_number (&n, infile, primetest))
1240 2154 : break;
1241 :
1242 2446 : cnt = count;
1243 : /* reset B1 (and B2min) values, as they could have been advanced
1244 : on the prior candidate */
1245 2446 : B1 = startingB1;
1246 2446 : mpz_set (B2min, startingB2min);
1247 : }
1248 :
1249 : /* "blank" lines, or lines that could not be parsed correctly
1250 : will leave a 1 in this value */
1251 2502 : if (n.isPrp)
1252 : {
1253 : /* n is 0 or 1 (or -1 I guess) so do NOT proceed with it */
1254 10 : cnt = 0;
1255 10 : continue;
1256 : }
1257 :
1258 : /* Set effective seed for factoring attempt on this number */
1259 2492 : if (specific_A)
1260 : {
1261 306 : if (param != ECM_PARAM_TWISTED_HESSIAN)
1262 : {
1263 276 : returncode = mod_from_mpq (A, rat_A, n.n, verbose);
1264 : }
1265 : else
1266 : {
1267 30 : mpz_init(numer_A);
1268 30 : mpz_init(denom_A);
1269 30 : mpz_mod(numer_A, mpq_numref(rat_A), n.n);
1270 30 : mpz_mod(denom_A, mpq_denref(rat_A), n.n);
1271 30 : returncode = ECM_NO_FACTOR_FOUND;
1272 : }
1273 306 : if (returncode != ECM_NO_FACTOR_FOUND)
1274 40 : goto free_all1;
1275 : }
1276 :
1277 2452 : if (specific_x0) /* convert rational value to integer */
1278 : {
1279 469 : if (count != 1)
1280 : {
1281 10 : fprintf (stderr, "Error, option -c is incompatible with -x0\n");
1282 10 : exit (EXIT_FAILURE);
1283 : }
1284 :
1285 459 : returncode = mod_from_mpq (x, rat_x0, n.n, verbose);
1286 459 : if (returncode != ECM_NO_FACTOR_FOUND)
1287 10 : goto free_all1;
1288 :
1289 449 : if (specific_y0)
1290 : {
1291 190 : returncode = mod_from_mpq (y, rat_y0, n.n, verbose);
1292 190 : if (returncode != ECM_NO_FACTOR_FOUND)
1293 10 : goto free_all1;
1294 : }
1295 : }
1296 : else /* Set x to 0. This will tell the ecm library to choose a
1297 : random starting point for P-1 and P+1. ECM will
1298 : compute a suitable value from sigma or A if x is zero. */
1299 1983 : mpz_set_ui (x, 0);
1300 :
1301 2422 : if (ECM_IS_DEFAULT_B1_DONE (B1done)) /* first time */
1302 : {
1303 2412 : mpz_set (orig_x0, x);
1304 2412 : if (specific_y0)
1305 180 : mpz_set (orig_y0, y);
1306 : }
1307 : }
1308 2529 : if (verbose >= OUTPUT_NORMAL)
1309 : {
1310 2509 : if (cnt == count)
1311 : {
1312 : /* first time this candidate has been run
1313 : (if looping more than once) */
1314 2453 : if (n.cpExpr && n.nexprlen < MAX_NUMBER_PRINT_LEN)
1315 574 : printf ("Input number is %s (%u digits)\n", n.cpExpr,
1316 : n.ndigits);
1317 1879 : else if (n.ndigits < MAX_NUMBER_PRINT_LEN)
1318 1869 : gmp_printf ("Input number is %Zd (%u digits)\n",
1319 : n.n, n.ndigits);
1320 : else
1321 : {
1322 : /* Print only first and last ten digits of the number */
1323 : mpz_t t, u;
1324 10 : mpz_init (t);
1325 10 : mpz_init (u);
1326 10 : mpz_ui_pow_ui (u, 5, n.ndigits - 10);
1327 10 : mpz_tdiv_q_2exp (t, n.n, n.ndigits - 10);
1328 10 : mpz_tdiv_q (t, t, u);
1329 10 : gmp_printf ("Input number is %Zd...", t);
1330 10 : mpz_ui_pow_ui (u, 10, 10);
1331 10 : mpz_tdiv_r (t, n.n, u);
1332 10 : gmp_printf ("%Zd (%u digits)\n", t, n.ndigits);
1333 10 : mpz_clear (u);
1334 10 : mpz_clear (t);
1335 : }
1336 :
1337 2453 : if (n.isPrp)
1338 0 : printf ("****** Warning: input is probably prime ******\n");
1339 : }
1340 2509 : fflush (stdout);
1341 : }
1342 : /* Even in verbose=0 we should primality check if told to do so,
1343 : however, we will print to stderr to keep stdout "clean"
1344 : for verbose=0 like behavior */
1345 20 : else if (cnt == count && n.isPrp)
1346 0 : gmp_fprintf (stderr, "Input number is %Zd (%u digits)\n"
1347 : "****** Warning: input is probably prime ******\n",
1348 : n.n, n.ndigits);
1349 :
1350 2529 : mpgocandi_fixup_with_N (&go, &n);
1351 :
1352 2519 : if (param != ECM_PARAM_DEFAULT && method != ECM_ECM)
1353 : {
1354 10 : fprintf (stderr, "Error, the -param option is only valid for ECM\n");
1355 10 : exit (EXIT_FAILURE);
1356 : }
1357 2509 : else if (param != ECM_PARAM_DEFAULT && !IS_BATCH_MODE (param)
1358 1585 : && param != ECM_PARAM_SUYAMA && param != ECM_PARAM_WEIERSTRASS
1359 60 : && param != ECM_PARAM_HESSIAN
1360 30 : && param != ECM_PARAM_TWISTED_HESSIAN)
1361 : {
1362 0 : fprintf (stderr, "Error, invalid -param value: %d\n", param);
1363 0 : exit (EXIT_FAILURE);
1364 : }
1365 : /* params->param might be set if we resume from a file */
1366 2509 : if (params->param == ECM_PARAM_DEFAULT)
1367 2346 : params->param = param;
1368 :
1369 : /* this is a hack to produce an error in ecm() when -bsaves is used
1370 : but we are not in batch mode */
1371 2509 : if (savefile_s != NULL)
1372 : {
1373 38 : if (!IS_BATCH_MODE(param))
1374 : {
1375 20 : fprintf (stderr, "Error, -bsaves makes sense in batch mode only\n");
1376 20 : exit (EXIT_FAILURE);
1377 : }
1378 : /* if batch_s <> 1, it means it was already initialized,
1379 : thus don't discard it, for example with -c 2 */
1380 18 : if (mpz_cmp_ui (params->batch_s, 1) == 0) /* not initialized */
1381 18 : mpz_set_ui (params->batch_s, 2);
1382 : }
1383 :
1384 : /* load batch product s from a file */
1385 2489 : if (loadfile_s != NULL)
1386 : {
1387 86 : int st = cputime ();
1388 86 : if (!IS_BATCH_MODE(param))
1389 : {
1390 30 : fprintf (stderr, "Error, -bloads makes sense in batch mode only\n");
1391 30 : exit (EXIT_FAILURE);
1392 : }
1393 56 : params->batch_last_B1_used = B1;
1394 56 : if (read_s_from_file (params->batch_s, loadfile_s, B1))
1395 : {
1396 40 : fprintf (stderr, "Error while reading s from file\n");
1397 40 : exit (EXIT_FAILURE);
1398 : }
1399 16 : else if (verbose >= OUTPUT_VERBOSE)
1400 8 : fprintf (stdout, "Reading batch product (of %"PRIu64" bits) of "
1401 : "primes up to B1=%1.0f from %s took %ldms\n",
1402 8 : (uint64_t) mpz_sizeinbase (params->batch_s, 2), B1,
1403 8 : loadfile_s, cputime () - st);
1404 : }
1405 :
1406 : /* set parameters that may change from one curve to another */
1407 2419 : params->method = method; /* may change with resume */
1408 2419 : mpz_set (params->x, x); /* may change with resume */
1409 2419 : mpz_set (params->y, y); /* may change with resume */
1410 : /* already set when resumefile was read */
1411 2419 : if (resumefile == NULL)
1412 : {
1413 : /* if A is not zero, we use it */
1414 2312 : params->sigma_is_A = specific_A;
1415 2312 : if (specific_A)
1416 : {
1417 246 : if (params->param == ECM_PARAM_WEIERSTRASS)
1418 : {
1419 : /* compute B = y^2-x^3-A*x = y^2 - (x^2+A)*x */
1420 110 : mpz_mul (params->E->a6, y, y);
1421 110 : mpz_mul (params->E->a4, x, x);
1422 110 : mpz_add (params->E->a4, params->E->a4, A);
1423 110 : mpz_mul (params->E->a4, params->E->a4, x);
1424 110 : mpz_sub (params->E->a6, params->E->a6, params->E->a4);
1425 110 : mpz_mod (params->E->a6, params->E->a6, n.n);
1426 110 : mpz_set (params->E->a4, A);
1427 110 : params->sigma_is_A = -1;
1428 110 : params->E->type = ECM_EC_TYPE_WEIERSTRASS;
1429 110 : params->E->law = ECM_LAW_HOMOGENEOUS;
1430 : }
1431 136 : else if (params->param == ECM_PARAM_HESSIAN)
1432 : {
1433 : /* use x^3+y^3+1=3*A*x*y */
1434 30 : mpz_set (params->E->a4, A);
1435 30 : params->sigma_is_A = -1;
1436 30 : params->E->type = ECM_EC_TYPE_HESSIAN;
1437 30 : params->E->law = ECM_LAW_HOMOGENEOUS;
1438 : }
1439 106 : else if (params->param == ECM_PARAM_TWISTED_HESSIAN)
1440 : {
1441 : /* use a*x^3+y^3+1=d*x*y with A=a^3/d -- trick! */
1442 30 : mpz_set (params->E->a4, numer_A);
1443 30 : mpz_set (params->E->a6, denom_A);
1444 30 : mpz_clear(numer_A);
1445 30 : mpz_clear(denom_A);
1446 30 : params->sigma_is_A = -1;
1447 30 : params->E->type = ECM_EC_TYPE_TWISTED_HESSIAN;
1448 30 : params->E->law = ECM_LAW_HOMOGENEOUS;
1449 : }
1450 : }
1451 : #ifdef HAVE_TORSION
1452 2066 : else if (torsion != NULL)
1453 : {
1454 380 : params->param = ECM_PARAM_TORSION;
1455 380 : params->sigma_is_A = -1;
1456 380 : result = build_curves_with_torsion2 (f, n.n, params->E,
1457 : params->x, params->y,
1458 : torsion, sigma);
1459 : }
1460 : #endif
1461 : }
1462 2419 : mpz_set (params->sigma, (params->sigma_is_A) ? A : sigma);
1463 2419 : mpz_set (params->go, go.Candi.n); /* may change if contains N */
1464 2419 : mpz_set (params->B2min, B2min); /* may change with -c */
1465 : /* Default, for P-1/P+1 with old stage 2 and ECM, use NTT only
1466 : for small input */
1467 2419 : if (use_ntt == 1 && (method == ECM_ECM || S != ECM_DEFAULT_S))
1468 1673 : params->use_ntt = (mpz_size (n.n) <= NTT_SIZE_THRESHOLD);
1469 : else
1470 746 : params->use_ntt = use_ntt;
1471 :
1472 : #ifdef HAVE_GWNUM
1473 : /* check if the input number can be represented as k*b^n+c */
1474 : if (kbnc_z (&gw_k, &gw_b, &gw_n, &gw_c, n.n))
1475 : {
1476 : params->gw_k = gw_k;
1477 : params->gw_b = gw_b;
1478 : params->gw_n = gw_n;
1479 : params->gw_c = gw_c;
1480 : if (verbose > OUTPUT_NORMAL)
1481 : printf ("Found number: %.0f*%lu^%lu + %ld\n",
1482 : gw_k, gw_b, gw_n, gw_c);
1483 : }
1484 : else if (kbnc_str (&gw_k, &gw_b, &gw_n, &gw_c, n.cpExpr, n.n))
1485 : {
1486 : params->gw_k = gw_k;
1487 : params->gw_b = gw_b;
1488 : params->gw_n = gw_n;
1489 : params->gw_c = gw_c;
1490 : if (verbose > OUTPUT_NORMAL)
1491 : printf ("Found number: %.0f*%lu^%lu + %ld\n",
1492 : gw_k, gw_b, gw_n, gw_c);
1493 : }
1494 : else
1495 : {
1496 : if (verbose > OUTPUT_NORMAL)
1497 : printf ("Did not find a gwnum poly for the input number.\n");
1498 : }
1499 : #endif
1500 :
1501 2419 : if (timestamp)
1502 : {
1503 : time_t t;
1504 :
1505 10 : t = time (NULL);
1506 10 : printf ("[%.24s]\n", ctime (&t));
1507 : }
1508 :
1509 : #if 0
1510 : /* Test mpres_muldivbysomething_si() which is not called in normal
1511 : operation */
1512 : mpmod_selftest (n.n);
1513 : #endif
1514 :
1515 : /* now call the ecm library */
1516 2419 : if (result == ECM_NO_FACTOR_FOUND)
1517 : /* if torsion was used, some factor may have been found... */
1518 2169 : result = ecm_factor (f, n.n, B1, params);
1519 :
1520 2419 : if (result == ECM_ERROR)
1521 : {
1522 102 : fprintf (stderr, "Please report internal errors at <%s>.\n",
1523 : PACKAGE_BUGREPORT);
1524 102 : exit (EXIT_FAILURE);
1525 : }
1526 :
1527 2317 : if (!params->gpu)
1528 2317 : cnt --; /* one more curve performed */
1529 : else
1530 : {
1531 0 : if (cnt <= params->gpu_number_of_curves)
1532 0 : cnt = 0;
1533 : else
1534 0 : cnt -= params->gpu_number_of_curves;
1535 : }
1536 :
1537 : /* When GPU is used we need to have the value of N before it is
1538 : divided by potential factor in f */
1539 2317 : mpz_init_set (tmp_n, n.n);
1540 :
1541 2317 : if (result != ECM_NO_FACTOR_FOUND)
1542 : {
1543 : mpz_t tmp_factor;
1544 1929 : returncode = 0;
1545 1929 : mpz_init (tmp_factor);
1546 : do
1547 : {
1548 1929 : if (params->gpu)
1549 : /* gpu returns multiple factors as f = f0 + f1*n + ... + fk*n^k */
1550 0 : mpz_fdiv_qr (f, tmp_factor, f, tmp_n);
1551 : else
1552 1929 : mpz_set (tmp_factor, f);
1553 :
1554 1929 : returncode = process_newfactor (tmp_factor, result, &n, method,
1555 : returncode, params->gpu, &cnt, &resume_wasPrp,
1556 : resume_lastfac, resumefile, verbose, deep);
1557 0 : } while (params->gpu && mpz_cmp_ui (f, 0) != 0
1558 1929 : && returncode != ECM_INPUT_NUMBER_FOUND);
1559 1929 : mpz_clear (tmp_factor);
1560 : }
1561 :
1562 : /* if quiet mode, prints remaining cofactor after last curve */
1563 2317 : if ((cnt == 0) && (verbose == 0) && (mpz_cmp_ui (n.n, 1) > 0))
1564 : {
1565 20 : if (n.cpExpr)
1566 10 : printf ("%s", n.cpExpr);
1567 : else
1568 10 : mpz_out_str (stdout, 10, n.n);
1569 20 : putchar ('\n');
1570 20 : fflush (stdout);
1571 : }
1572 :
1573 : /* Write composite cofactors to savefile if requested */
1574 : /* If no factor was found, we consider cofactor composite and write it */
1575 2317 : if (savefilename != NULL && !n.isPrp)
1576 : {
1577 : /* TODO Deal with return code */
1578 55 : write_resumefile (savefilename, method, tmp_n, params, &n,
1579 : orig_x0, orig_y0, comment);
1580 : }
1581 :
1582 2317 : mpz_clear (tmp_n);
1583 :
1584 : /* Save the batch exponent s if requested */
1585 2317 : if (savefile_s != NULL)
1586 : {
1587 16 : int ret = write_s_in_file (savefile_s, params->batch_s);
1588 16 : if (verbose >= OUTPUT_VERBOSE && ret > 0)
1589 0 : printf ("Saved batch product (of %u bytes) in %s\n", ret,
1590 : savefile_s);
1591 : }
1592 :
1593 : /* advance B1, if autoincrement value had been set during command line
1594 : parsing */
1595 2317 : if (autoincrementB1 > 0.0)
1596 : {
1597 : double NewB1;
1598 76 : NewB1 = calc_B1_AutoIncrement (B1, autoincrementB1);
1599 76 : if (mpz_cmp_d (B2min, B1) <= 0) /* <= might be better than == */
1600 76 : mpz_set_d (B2min, NewB1);
1601 76 : B1 = NewB1;
1602 : }
1603 : } /* end of main loop */
1604 :
1605 10 : free_all1:
1606 2431 : if (infilename) /* infile might be stdin, don't fclose that! */
1607 20 : fclose (infile);
1608 :
1609 2431 : if (resumefile)
1610 : {
1611 207 : fclose (resumefile);
1612 207 : mpz_clear (resume_lastN);
1613 207 : mpz_clear (resume_lastfac);
1614 : }
1615 :
1616 2431 : mpz_clear (orig_y0);
1617 2431 : mpz_clear (orig_x0);
1618 2431 : mpz_clear (y);
1619 2431 : mpz_clear (x);
1620 2431 : mpz_clear (f);
1621 2431 : mpcandi_t_free (&n);
1622 :
1623 2474 : free_all:
1624 2474 : free_expr ();
1625 :
1626 2474 : mpq_clear (rat_y0);
1627 2474 : mpq_clear (rat_x0);
1628 2474 : mpq_clear (rat_A);
1629 2474 : mpz_clear (startingB2min);
1630 2474 : mpz_clear (B2min);
1631 2474 : mpz_clear (B2);
1632 2474 : mpz_clear (A);
1633 2474 : mpz_clear (sigma);
1634 :
1635 2474 : mpgocandi_t_free (&go);
1636 2474 : ecm_clear (params);
1637 :
1638 : /* exit 0 if a factor was found for the last input, except if we exit due
1639 : to a signal */
1640 : #ifdef HAVE_SIGNAL
1641 2474 : if (returncode == 0 && exit_asap_value != 0)
1642 0 : returncode = 143;
1643 : #endif
1644 :
1645 : /* print memory usage */
1646 2474 : if (verbose > 1)
1647 : {
1648 142 : long peak = PeakMemusage ();
1649 142 : if (peak != -1)
1650 142 : printf ("Peak memory usage: %ldMB\n", peak >> 10);
1651 : }
1652 :
1653 2474 : return returncode;
1654 : }
|