1 /* Factoring with Pollard's rho method.
3 Copyright (C) 1995 Free Software Foundation, Inc.
5 This program is free software; you can redistribute it and/or modify it
6 under the terms of the GNU General Public License as published by the
7 Free Software Foundation; either version 2, or (at your option) any
10 This program is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 General Public License for more details.
15 You should have received a copy of the GNU General Public License along
16 with this program; see the file COPYING. If not, write to the Free Software
17 Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
22 int flag_mersenne = 0;
24 static unsigned add[] = {4, 2, 4, 2, 4, 6, 2, 6};
26 factor_using_division (t, limit)
38 if (mpz_probab_prime_p (t, 50))
43 mpz_tdiv_qr_ui (q, r, t, 2);
44 if (mpz_cmp_ui (r, 0) != 0)
49 if (mpz_probab_prime_p (t, 50))
55 mpz_tdiv_qr_ui (q, r, t, 3);
56 if (mpz_cmp_ui (r, 0) != 0)
61 if (mpz_probab_prime_p (t, 50))
67 mpz_tdiv_qr_ui (q, r, t, 5);
68 if (mpz_cmp_ui (r, 0) != 0)
73 if (mpz_probab_prime_p (t, 50))
81 mpz_tdiv_qr_ui (q, r, t, f);
82 if (mpz_cmp_ui (r, 0) != 0)
94 if (mpz_probab_prime_p (t, 50))
100 mpz_out_str (stdout, 10, t);
110 factor_using_pollard_rho (m, a_int, x0, p)
127 mpz_init_set_ui (q, 1);
130 mpz_init_set_si (a, a_int);
131 mpz_init_set_si (x, x0);
132 mpz_init_set_si (y, x0);
134 while (mpz_cmp_ui (n, 1) != 0)
138 mpz_powm_ui (x, x, p, n); mpz_add (x, x, a);
139 mpz_powm_ui (y, y, p, n); mpz_add (y, y, a);
140 mpz_powm_ui (y, y, p, n); mpz_add (y, y, a);
144 mpz_mul (x, x, x); mpz_add (x, x, a); mpz_mod (x, x, n);
145 mpz_mul (y, y, y); mpz_add (y, y, a); mpz_mod (y, y, n);
146 mpz_mul (y, y, y); mpz_add (y, y, a); mpz_mod (y, y, n);
149 if (mpz_cmp (x, y) > 0)
160 if (mpz_cmp_ui (d, 1) != 0)
162 if (!mpz_probab_prime_p (d, 50))
163 factor_using_pollard_rho (d, (random () & 31) - 16,
164 (random () & 31), p);
167 mpz_out_str (stdout, 10, d);
172 if (mpz_probab_prime_p (n, 50))
174 mpz_out_str (stdout, 10, n);
198 factor_using_division (t, 1000000);
199 factor_using_pollard_rho (t, a, x0, p);
211 for (i = 1; i < argc; i++)
213 if (!strncmp (argv[i], "-Mp", 3))
215 p = atoi (argv[i] + 3);
216 mpz_init_set_ui (t, 1);
217 mpz_mul_2exp (t, t, p);
218 mpz_sub_ui (t, t, 1);
224 mpz_init_set_str (t, argv[i], 0);
230 factor (t, a, x0, p);