dixon/dixon.cc

   1 #include <myint.h>
   2
   3 myInt factor(myInt n) {
   4   myInt x, xx, d, root;
   5
   6   root = sqrt(n);
   7
   8   if (issquare(n))
   9     return root;
  10
  11   x = root;
  12
  13   for (;; x++) {
  14     d = gcd(x, n);
  15
  16     if (1 < d && d < n)
  17       return d;
  18
  19     xx = (x * x) % n;
  20
  21     if (issquare(xx)) {
  22       d = gcd((x - sqrt(xx)) % n, n);
  23
  24       if (1 < d && d < n)
  25         return d;
  26     }
  27   }
  28   cout << "couldn't find!" << endl;
  29
  30   return 0;
  31 };
  32
  33 int main(int argc, char *argv[]) {
  34   myInt n, f;
  35
  36   if (argc < 2) {
  37     cerr << "usage: " << argv[0] << " number_to_factorize" << endl;
  38     return 1;
  39   }
  40
  41   n = argv[1];
  42
  43   if (n == 1) {
  44     cout << n << ": is " << n << endl;
  45     return 0;
  46   }
  47
  48   cout << n << ": " << flush;
  49
  50   if (isprime(n)) {
  51     cout << "is prime" << endl;
  52     return 0;
  53   }
  54
  55   while (!isprime(n)) {
  56     f = factor(n);
  57     cout << f << " " << flush;
  58     n /= f;
  59   }
  60   cout << n << endl;
  61
  62   return 0;
  63 };