c_cpp/etc/calc/cal/pollard.cal

   1 /*
   2  * pollard - factor using Pollard's p-1 method
   3  *
   4  * Copyright (C) 1999  David I. Bell
   5  *
   6  * Calc is open software; you can redistribute it and/or modify it under
   7  * the terms of the version 2.1 of the GNU Lesser General Public License
   8  * as published by the Free Software Foundation.
   9  *
  10  * Calc is distributed in the hope that it will be useful, but WITHOUT
  11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  12  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General
  13  * Public License for more details.
  14  *
  15  * A copy of version 2.1 of the GNU Lesser General Public License is
  16  * distributed with calc under the filename COPYING-LGPL.  You should have
  17  * received a copy with calc; if not, write to Free Software Foundation, Inc.
  18  * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  19  *
  20  * @(#) $Revision: 30.1 $
  21  * @(#) $Id: pollard.cal,v 30.1 2007/03/16 11:09:54 chongo Exp $
  22  * @(#) $Source: /usr/local/src/bin/calc/cal/RCS/pollard.cal,v $
  23  *
  24  * Under source code control:   1991/05/22 21:56:37
  25  * File existed as early as:    1991
  26  *
  27  * Share and enjoy!  :-)        http://www.isthe.com/chongo/tech/comp/calc/
  28  */
  29
  30
  31 define pfactor(N, B, ai, af)
  32 {
  33         local   a, k, i, d;
  34
  35         if (isnull(B))
  36                 B = 1000;
  37         if (isnull(ai))
  38                 ai = 2;
  39         if (isnull(af))
  40                 af = ai + 20;
  41         k = lcmfact(B);
  42         d = lfactor(N, B);
  43         if (d > 1)
  44                 return d;
  45         for (a = ai; a <= af; a++) {
  46                 i = pmod(a, k, N);
  47                 d = gcd(i - 1, N);
  48                 if ((d > 1) && (d != N))
  49                         return d;
  50         }
  51         return 1;
  52 }