Update from master sources.

1 files changed, 40 insertions, 46 deletions

diff --git a/demos/factorize.c b/demos/factorize.c
index 4a965d316..be50188bd 100644
--- a/demos/factorize.c
+++ b/demos/factorize.c
@@ -1,20 +1,20 @@
 /* Factoring with Pollard's rho method.
 
-   Copyright (C) 1995 Free Software Foundation, Inc.
+   Copyright (C) 1995, 1997 Free Software Foundation, Inc.
 
-This program is free software; you can redistribute it and/or modify it
-under the terms of the GNU General Public License as published by the
-Free Software Foundation; either version 2, or (at your option) any
-later version.
+   This program is free software; you can redistribute it and/or modify it
+   under the terms of the GNU General Public License as published by the
+   Free Software Foundation; either version 2, or (at your option) any
+   later version.
 
-This program is distributed in the hope that it will be useful, but
-WITHOUT ANY WARRANTY; without even the implied warranty of
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
-General Public License for more details.
+   This program is distributed in the hope that it will be useful, but
+   WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   General Public License for more details.
 
-You should have received a copy of the GNU General Public License along
-with this program; see the file COPYING.  If not, write to the Free Software
-Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
+   You should have received a copy of the GNU General Public License along
+   with this program; see the file COPYING.  If not, write to the Free
+   Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
 
 #include <stdio.h>
 #include "gmp.h"
@@ -23,6 +23,7 @@ int flag_mersenne = 0;
 
 static unsigned add[] = {4, 2, 4, 2, 4, 6, 2, 6};
 
+void
 factor_using_division (t, limit)
      mpz_t t;
      unsigned int limit;
@@ -35,55 +36,48 @@ factor_using_division (t, limit)
   mpz_init (q);
   mpz_init (r);
 
-  if (mpz_probab_prime_p (t, 50))
-    goto ready;
-
   for (;;)
     {
-      mpz_tdiv_qr_ui (q, r, t, 2);
-      if (mpz_cmp_ui (r, 0) != 0)
+      mpz_tdiv_qr_ui (q, r, t, 2L);
+      if (mpz_cmp_ui (r, 0L) != 0)
 	break;
       mpz_set (t, q);
       printf ("2 ");
       fflush (stdout);
-      if (mpz_probab_prime_p (t, 50))
-	goto ready;
     }
 
   for (;;)
     {
-      mpz_tdiv_qr_ui (q, r, t, 3);
-      if (mpz_cmp_ui (r, 0) != 0)
+      mpz_tdiv_qr_ui (q, r, t, 3L);
+      if (mpz_cmp_ui (r, 0L) != 0)
 	break;
       mpz_set (t, q);
       printf ("3 ");
       fflush (stdout);
-      if (mpz_probab_prime_p (t, 50))
-	goto ready;
     }
 
   for (;;)
     {
-      mpz_tdiv_qr_ui (q, r, t, 5);
-      if (mpz_cmp_ui (r, 0) != 0)
+      mpz_tdiv_qr_ui (q, r, t, 5L);
+      if (mpz_cmp_ui (r, 0L) != 0)
 	break;
       mpz_set (t, q);
       printf ("5 ");
       fflush (stdout);
-      if (mpz_probab_prime_p (t, 50))
-	goto ready;
     }
 
   f = 7;
   ai = 0;
-  for (;;)
+  while (mpz_cmp_ui (t, 1) != 0)
     {
       mpz_tdiv_qr_ui (q, r, t, f);
-      if (mpz_cmp_ui (r, 0) != 0)
+      if (mpz_cmp_ui (r, 0L) != 0)
 	{
 	  f += addv[ai];
 	  if (f > limit)
-	    goto ret;
+	    break;
+	  if (mpz_cmp_ui (q, f) < 0)
+	    break;
 	  ai = (ai + 1) & 7;
 	}
       else
@@ -91,17 +85,9 @@ factor_using_division (t, limit)
 	  mpz_set (t, q);
 	  printf ("%lu ", f);
 	  fflush (stdout);
-	  if (mpz_probab_prime_p (t, 50))
-	    goto ready;
 	}
     }
 
- ready:
-  mpz_out_str (stdout, 10, t);
-  fflush (stdout);
-  mpz_set_ui (t, 1);
-  fputc (' ', stdout);
- ret:
   mpz_clear (q);
   mpz_clear (r);
 }
@@ -124,14 +110,14 @@ factor_using_pollard_rho (m, a_int, x0, p)
   mpz_init_set (n, m);
 
   mpz_init (d);
-  mpz_init_set_ui (q, 1);
+  mpz_init_set_ui (q, 1L);
   mpz_init (tmp);
 
   mpz_init_set_si (a, a_int);
   mpz_init_set_si (x, x0);
   mpz_init_set_si (y, x0);
 
-  while (mpz_cmp_ui (n, 1) != 0)
+  while (mpz_cmp_ui (n, 1L) != 0)
     {
       if (flag_mersenne)
 	{
@@ -157,9 +143,9 @@ factor_using_pollard_rho (m, a_int, x0, p)
 	{
 	  j += 1;
 	  mpz_gcd (d, q, n);
-	  if (mpz_cmp_ui (d, 1) != 0)
+	  if (mpz_cmp_ui (d, 1L) != 0)
 	    {
-	      if (!mpz_probab_prime_p (d, 50))
+	      if (!mpz_probab_prime_p (d, 25))
 		factor_using_pollard_rho (d, (random () & 31) - 16,
 					  (random () & 31), p);
 	      else
@@ -169,7 +155,9 @@ factor_using_pollard_rho (m, a_int, x0, p)
 		  fputc (' ', stdout);
 		}
 	      mpz_div (n, n, d);
-	      if (mpz_probab_prime_p (n, 50))
+	      mpz_mod (x, x, n);
+	      mpz_mod (y, y, n);
+	      if (mpz_probab_prime_p (n, 25))
 		{
 		  mpz_out_str (stdout, 10, n);
 		  fflush (stdout);
@@ -196,7 +184,13 @@ factor (t, a, x0, p)
      unsigned long p;
 {
   factor_using_division (t, 1000000);
-  factor_using_pollard_rho (t, a, x0, p);
+  if (mpz_cmp_ui (t, 1) != 0)
+    {
+      if (mpz_probab_prime_p (t, 25))
+	mpz_out_str (stdout, 10, t);
+      else
+	factor_using_pollard_rho (t, a, x0, p);
+    }
 }
 
 main (argc, argv)
@@ -213,9 +207,9 @@ main (argc, argv)
       if (!strncmp (argv[i], "-Mp", 3))
 	{
 	  p = atoi (argv[i] + 3);
-	  mpz_init_set_ui (t, 1);
+	  mpz_init_set_ui (t, 1L);
 	  mpz_mul_2exp (t, t, p);
-	  mpz_sub_ui (t, t, 1);
+	  mpz_sub_ui (t, t, 1L);
 	  flag_mersenne = 1;
 	}
       else