Subversion Repositories openrisc

unsigned long

gcd_ll (unsigned long long x, unsigned long long y)

{

  for (;;)

    {

      if (y == 0)

        return (unsigned long) x;

      x = x % y;

      if (x == 0)

        return (unsigned long) y;

      y = y % x;

    }

}

unsigned long long

powmod_ll (unsigned long long b, unsigned e, unsigned long long m)

{

  unsigned t;

  unsigned long long pow;

  int i;

  if (e == 0)

    return 1;

  /* Find the most significant bit in E.  */

  t = e;

  for (i = 0; t != 0; i++)

    t >>= 1;

  /* The most sign bit in E is handled outside of the loop, by beginning

     with B in POW, and decrementing I.  */

  pow = b;

  i -= 2;

  for (; i >= 0; i--)

    {

      pow = pow * pow % m;

      if ((1 << i) & e)

        pow = pow * b % m;

    }

  return pow;

}

unsigned long factab[10];

void

facts (t, a_int, x0, p)

     unsigned long long t;

     int a_int;

     int x0;

     unsigned p;

{

  unsigned long *xp = factab;

  unsigned long long x, y;

  unsigned long q = 1;

  unsigned long long a = a_int;

  int i;

  unsigned long d;

  int j = 1;

  unsigned long tmp;

  int jj = 0;

  x = x0;

  y = x0;

  for (i = 1; i < 10000; i++)

    {

      x = powmod_ll (x, p, t) + a;

      y = powmod_ll (y, p, t) + a;

      y = powmod_ll (y, p, t) + a;

      if (x > y)

        tmp = x - y;

      else

        tmp = y - x;

      q = (unsigned long long) q * tmp % t;

      if (i == j)

        {

          jj += 1;

          j += jj;

          d = gcd_ll (q, t);

          if (d != 1)

            {

              *xp++ = d;

              t /= d;

              if (t == 1)

                {

                  return;

                  *xp = 0;

                }

            }

        }

    }

}

main ()

{

  unsigned long long t;

  unsigned x0, a;

  unsigned p;

  p = 27;

  t = (1ULL << p) - 1;

  a = -1;

  x0 = 3;

  facts (t, a, x0, p);

  if (factab[0] != 7 || factab[1] != 73 || factab[2] != 262657)

    abort();

  exit (0);

}