my_mpz_powm_ui.cc

Go to the documentation of this file.

void my_mpz_powm_ui(mpz_t a, unsigned int n, const mpz_t m)
{
  // berechnet a=a^n mod m, n>1, n (möglichst) prim,
  // dies ist eine alternative Vorgehensweise zur binären Version, die
  // für Primzahlen ein wenig schneller sein sollte...
  // Idee dahinter:
  // Wenn in n viele Bits gesetzt sind, müssen auch viele Zweierpotenzen
  // in der Exponentation kumuliert werden. Dann wird es in vielen
  // Fällen billiger sein, den Exponenten n anderweitig zusammenzusetzen.
  // Eine Möglichkeit besteht darin, n-1 in Faktoren zu zerlegen, die
  // ihrerseits wenig "Bitoverhead" haben.

  if (n<127) { mpz_powm_ui(a,a,n,m); return; } 

  register unsigned int h = n;
  register int b = 0;
  while (h) { b+=(h&1) ? 3 : -4; h>>=1; } // #gesetzte Bits bestimmen
  //cout << "b= " << b << endl;

  if (b<0)
   {
     //cout << "---> " << n << endl; 
     mpz_powm_ui(a,a,n,m);
     return;
   }

  //cout << "-> " << n << endl; 
  mpz_t r;
  mpz_init_set(r,a);
  n--;

  h=0; while ((n&1)==0) { n>>=1; h++; }
  if (h) mpz_powm_ui(r,r,1<<h,m);
  while (n%129==0) { n/=129; mpz_powm_ui(r,r,129,m); }
  while (n%65==0) { n/=65; mpz_powm_ui(r,r,65,m); }
  while (n%33==0) { n/=33; mpz_powm_ui(r,r,33,m); }
  while (n%17==0) { n/=17; mpz_powm_ui(r,r,17,m); }
  while (n%9==0) { n/=9; mpz_powm_ui(r,r,9,m); }
  while (n%5==0) { n/=5; mpz_powm_ui(r,r,5,m); }
  while (n%3==0) { n/=3; mpz_powm_ui(r,r,3,m); }
//  while (n%7==0) { n/=7; mpz_powm_ui(r,r,7,m); }
  while (n%11==0) { n/=11; mpz_powm_ui(r,r,11,m); }
  while (n%13==0) { n/=13; mpz_powm_ui(r,r,13,m); }
  while (n%19==0) { n/=19; mpz_powm_ui(r,r,19,m); }
  //while (n%23==0) { n/=19; mpz_powm_ui(r,r,23,m); }
  //while (n%29==0) { n/=29; mpz_powm_ui(r,r,29,m); }
  if (n>1) mpz_powm_ui(r,r,n,m);
  mpz_mul(a,a,r); mpz_mod(a,a,m);
  mpz_clear(r);
}

---