From a36c74fd293f48ba68da96c84310d878a1d49e5a Mon Sep 17 00:00:00 2001 From: Torbjorn Granlund Date: Sun, 28 Jun 2009 21:17:42 +0200 Subject: (factor_using_pollard_rho): Rewrite. --- demos/factorize.c | 150 ++++++++++++++++++++++++++---------------------------- 1 file changed, 73 insertions(+), 77 deletions(-) (limited to 'demos') diff --git a/demos/factorize.c b/demos/factorize.c index 65d3aaa50..464a5fc59 100644 --- a/demos/factorize.c +++ b/demos/factorize.c @@ -98,8 +98,7 @@ factor_using_division (mpz_t t, unsigned int limit) } } - mpz_clear (q); - mpz_clear (r); + mpz_clears (q, r, NULL); } void @@ -132,129 +131,133 @@ factor_using_division_2kp (mpz_t t, unsigned int limit, unsigned long p) mpz_add_ui (f, f, 2 * p); } - mpz_clear (f); - mpz_clear (r); + mpz_clears (f, r, NULL); } void -factor_using_pollard_rho (mpz_t n, int a_int, unsigned long p) +factor_using_pollard_rho (mpz_t n, unsigned long a, unsigned long p) { mpz_t x, x1, y, P; - mpz_t a; - mpz_t g; mpz_t t1, t2; - int k, l, c, i; + unsigned long long k, l, i; if (flag_verbose > 0) { - printf ("[pollard-rho (%d)] ", a_int); + printf ("[pollard-rho (%lu)] ", a); fflush (stdout); } - mpz_init (g); - mpz_init (t1); - mpz_init (t2); - - mpz_init_set_si (a, a_int); + mpz_inits (t1, t2, NULL); mpz_init_set_si (y, 2); mpz_init_set_si (x, 2); mpz_init_set_si (x1, 2); + mpz_init_set_ui (P, 1); k = 1; l = 1; - mpz_init_set_ui (P, 1); - c = 0; while (mpz_cmp_ui (n, 1) != 0) { -S2: - if (p != 0) - { - mpz_powm_ui (x, x, p, n); mpz_add (x, x, a); - } - else - { - mpz_mul (x, x, x); mpz_add (x, x, a); mpz_mod (x, x, n); - } - mpz_sub (t1, x1, x); mpz_mul (t2, P, t1); mpz_mod (P, t2, n); - c++; - if (c == 20) - { - c = 0; - mpz_gcd (g, P, n); - if (mpz_cmp_ui (g, 1) != 0) - goto S4; - mpz_set (y, x); - } -S3: - k--; - if (k > 0) - goto S2; - - mpz_gcd (g, P, n); - if (mpz_cmp_ui (g, 1) != 0) - goto S4; - - mpz_set (x1, x); - k = l; - l = 2 * l; - for (i = 0; i < k; i++) + for (;;) { - if (p != 0) + do { - mpz_powm_ui (x, x, p, n); mpz_add (x, x, a); + if (p != 0) + { + mpz_powm_ui (x, x, p, n); + mpz_add_ui (x, x, a); + } + else + { + mpz_mul (t1, x, x); + mpz_mod (x, t1, n); + mpz_add_ui (x, x, a); + } + + mpz_sub (t1, x1, x); + mpz_mul (t2, P, t1); + mpz_mod (P, t2, n); + + if (k % 32 == 1) + { + mpz_gcd (t1, P, n); + if (mpz_cmp_ui (t1, 1) != 0) + goto factor_found; + mpz_set (y, x); + } } - else + while (--k != 0); + + mpz_gcd (t1, P, n); + if (mpz_cmp_ui (t1, 1) != 0) + goto factor_found; + + mpz_set (x1, x); + k = l; + l = 2 * l; + for (i = 0; i < k; i++) { - mpz_mul (x, x, x); mpz_add (x, x, a); mpz_mod (x, x, n); + if (p != 0) + { + mpz_powm_ui (x, x, p, n); + mpz_add_ui (x, x, a); + } + else + { + mpz_mul (t1, x, x); + mpz_mod (x, t1, n); + mpz_add_ui (x, x, a); + } } + mpz_set (y, x); } - mpz_set (y, x); - c = 0; - goto S2; -S4: + + factor_found: do { if (p != 0) { - mpz_powm_ui (y, y, p, n); mpz_add (y, y, a); + mpz_powm_ui (y, y, p, n); mpz_add_ui (y, y, a); } else { - mpz_mul (y, y, y); mpz_add (y, y, a); mpz_mod (y, y, n); + mpz_mul (t1, y, y); + mpz_mod (y, t1, n); + mpz_add_ui (y, y, a); } - mpz_sub (t1, x1, y); mpz_gcd (g, t1, n); + mpz_sub (t1, x1, y); + mpz_gcd (t1, t1, n); } - while (mpz_cmp_ui (g, 1) == 0); + while (mpz_cmp_ui (t1, 1) == 0); - mpz_div (n, n, g); /* divide by g, before g is overwritten */ + mpz_divexact (n, n, t1); /* divide by t1, before t1 is overwritten */ - if (!mpz_probab_prime_p (g, 3)) + if (!mpz_probab_prime_p (t1, 10)) { do { mp_limb_t a_limb; mpn_random (&a_limb, (mp_size_t) 1); - a_int = (int) a_limb; + a = a_limb; } - while (a_int == -2 || a_int == 0); + while (a == 0); if (flag_verbose > 0) { printf ("[composite factor--restarting pollard-rho] "); fflush (stdout); } - factor_using_pollard_rho (g, a_int, p); + factor_using_pollard_rho (t1, a, p); } else { - mpz_out_str (stdout, 10, g); + mpz_out_str (stdout, 10, t1); fflush (stdout); fputc (' ', stdout); } mpz_mod (x, x, n); mpz_mod (x1, x1, n); mpz_mod (y, y, n); - if (mpz_probab_prime_p (n, 3)) + if (mpz_probab_prime_p (n, 10)) { mpz_out_str (stdout, 10, n); fflush (stdout); @@ -263,14 +266,7 @@ S4: } } - mpz_clear (g); - mpz_clear (P); - mpz_clear (t2); - mpz_clear (t1); - mpz_clear (a); - mpz_clear (x1); - mpz_clear (x); - mpz_clear (y); + mpz_clears (P, t2, t1, x1, x, y, NULL); } void @@ -300,10 +296,10 @@ factor (mpz_t t, unsigned long p) printf ("[is number prime?] "); fflush (stdout); } - if (mpz_probab_prime_p (t, 3)) + if (mpz_probab_prime_p (t, 10)) mpz_out_str (stdout, 10, t); else - factor_using_pollard_rho (t, 1, p); + factor_using_pollard_rho (t, 1L, p); } } -- cgit v1.2.1