[BACK]Return to factorize.c CVS log [TXT][DIR] Up to [local] / OpenXM / src / kan96xx / gmp-2.0.2-ssh-2 / demos

Annotation of OpenXM/src/kan96xx/gmp-2.0.2-ssh-2/demos/factorize.c, Revision 1.1.1.1

1.1       takayama    1: /* Factoring with Pollard's rho method.
                      2:
                      3:    Copyright (C) 1995 Free Software Foundation, Inc.
                      4:
                      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
                      8: later version.
                      9:
                     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.
                     14:
                     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. */
                     18:
                     19: #include <stdio.h>
                     20: #include "gmp.h"
                     21:
                     22: int flag_mersenne = 0;
                     23:
                     24: static unsigned add[] = {4, 2, 4, 2, 4, 6, 2, 6};
                     25:
                     26: factor_using_division (t, limit)
                     27:      mpz_t t;
                     28:      unsigned int limit;
                     29: {
                     30:   mpz_t q, r;
                     31:   unsigned long int f;
                     32:   int i, ai;
                     33:   unsigned *addv = add;
                     34:
                     35:   mpz_init (q);
                     36:   mpz_init (r);
                     37:
                     38:   if (mpz_probab_prime_p (t, 50))
                     39:     goto ready;
                     40:
                     41:   for (;;)
                     42:     {
                     43:       mpz_tdiv_qr_ui (q, r, t, 2);
                     44:       if (mpz_cmp_ui (r, 0) != 0)
                     45:        break;
                     46:       mpz_set (t, q);
                     47:       printf ("2 ");
                     48:       fflush (stdout);
                     49:       if (mpz_probab_prime_p (t, 50))
                     50:        goto ready;
                     51:     }
                     52:
                     53:   for (;;)
                     54:     {
                     55:       mpz_tdiv_qr_ui (q, r, t, 3);
                     56:       if (mpz_cmp_ui (r, 0) != 0)
                     57:        break;
                     58:       mpz_set (t, q);
                     59:       printf ("3 ");
                     60:       fflush (stdout);
                     61:       if (mpz_probab_prime_p (t, 50))
                     62:        goto ready;
                     63:     }
                     64:
                     65:   for (;;)
                     66:     {
                     67:       mpz_tdiv_qr_ui (q, r, t, 5);
                     68:       if (mpz_cmp_ui (r, 0) != 0)
                     69:        break;
                     70:       mpz_set (t, q);
                     71:       printf ("5 ");
                     72:       fflush (stdout);
                     73:       if (mpz_probab_prime_p (t, 50))
                     74:        goto ready;
                     75:     }
                     76:
                     77:   f = 7;
                     78:   ai = 0;
                     79:   for (;;)
                     80:     {
                     81:       mpz_tdiv_qr_ui (q, r, t, f);
                     82:       if (mpz_cmp_ui (r, 0) != 0)
                     83:        {
                     84:          f += addv[ai];
                     85:          if (f > limit)
                     86:            goto ret;
                     87:          ai = (ai + 1) & 7;
                     88:        }
                     89:       else
                     90:        {
                     91:          mpz_set (t, q);
                     92:          printf ("%lu ", f);
                     93:          fflush (stdout);
                     94:          if (mpz_probab_prime_p (t, 50))
                     95:            goto ready;
                     96:        }
                     97:     }
                     98:
                     99:  ready:
                    100:   mpz_out_str (stdout, 10, t);
                    101:   fflush (stdout);
                    102:   mpz_set_ui (t, 1);
                    103:   fputc (' ', stdout);
                    104:  ret:
                    105:   mpz_clear (q);
                    106:   mpz_clear (r);
                    107: }
                    108:
                    109: void
                    110: factor_using_pollard_rho (m, a_int, x0, p)
                    111:      mpz_t m;
                    112:      long a_int;
                    113:      long x0;
                    114:      unsigned long p;
                    115: {
                    116:   mpz_t x, y, q;
                    117:   mpz_t a;
                    118:   mpz_t d;
                    119:   mpz_t tmp;
                    120:   mpz_t n;
                    121:   int i = 1;
                    122:   int j = 1;
                    123:
                    124:   mpz_init_set (n, m);
                    125:
                    126:   mpz_init (d);
                    127:   mpz_init_set_ui (q, 1);
                    128:   mpz_init (tmp);
                    129:
                    130:   mpz_init_set_si (a, a_int);
                    131:   mpz_init_set_si (x, x0);
                    132:   mpz_init_set_si (y, x0);
                    133:
                    134:   while (mpz_cmp_ui (n, 1) != 0)
                    135:     {
                    136:       if (flag_mersenne)
                    137:        {
                    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);
                    141:        }
                    142:       else
                    143:        {
                    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);
                    147:        }
                    148:
                    149:       if (mpz_cmp (x, y) > 0)
                    150:        mpz_sub (tmp, x, y);
                    151:       else
                    152:        mpz_sub (tmp, y, x);
                    153:       mpz_mul (q, q, tmp);
                    154:       mpz_mod (q, q, n);
                    155:
                    156:       if (++i % j == 0)
                    157:        {
                    158:          j += 1;
                    159:          mpz_gcd (d, q, n);
                    160:          if (mpz_cmp_ui (d, 1) != 0)
                    161:            {
                    162:              if (!mpz_probab_prime_p (d, 50))
                    163:                factor_using_pollard_rho (d, (random () & 31) - 16,
                    164:                                          (random () & 31), p);
                    165:              else
                    166:                {
                    167:                  mpz_out_str (stdout, 10, d);
                    168:                  fflush (stdout);
                    169:                  fputc (' ', stdout);
                    170:                }
                    171:              mpz_div (n, n, d);
                    172:              if (mpz_probab_prime_p (n, 50))
                    173:                {
                    174:                  mpz_out_str (stdout, 10, n);
                    175:                  fflush (stdout);
                    176:                  fputc (' ', stdout);
                    177:                  break;
                    178:                }
                    179:            }
                    180:        }
                    181:     }
                    182:
                    183:   mpz_clear (n);
                    184:   mpz_clear (d);
                    185:   mpz_clear (q);
                    186:   mpz_clear (tmp);
                    187:   mpz_clear (a);
                    188:   mpz_clear (x);
                    189:   mpz_clear (y);
                    190: }
                    191:
                    192: factor (t, a, x0, p)
                    193:      mpz_t t;
                    194:      long a;
                    195:      long x0;
                    196:      unsigned long p;
                    197: {
                    198:   factor_using_division (t, 1000000);
                    199:   factor_using_pollard_rho (t, a, x0, p);
                    200: }
                    201:
                    202: main (argc, argv)
                    203:      int argc;
                    204:      char *argv[];
                    205: {
                    206:   mpz_t t;
                    207:   long x0, a;
                    208:   unsigned long p;
                    209:   int i;
                    210:
                    211:   for (i = 1; i < argc; i++)
                    212:     {
                    213:       if (!strncmp (argv[i], "-Mp", 3))
                    214:        {
                    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);
                    219:          flag_mersenne = 1;
                    220:        }
                    221:       else
                    222:        {
                    223:          p = 0;
                    224:          mpz_init_set_str (t, argv[i], 0);
                    225:        }
                    226:
                    227:       a = -1;
                    228:       x0 = 3;
                    229:
                    230:       factor (t, a, x0, p);
                    231:       puts ("");
                    232:     }
                    233: }

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>