Method ModInv

IntMod.cpp:251–567

// ------------------------------------------------

void Int::ModInv() {

  // Compute modular inverse of this mop _P
  // 0 < this < P  , P must be odd
  // Return 0 if no inverse

  // 256bit
  //#define XCD 1               // ~80  kOps/s
  //#define MONTGOMERY 1        // ~246 kOps/s
  //#define PENK 1              // ~215 kOps/s
  #define DRS62 1               // ~640 kOps/s

  Int u(&_P);
  Int v(this);

#ifdef XCD

  Int r((int64_t)0);
  Int s((int64_t)1);
  Int q, t1, t2, w;

  // Classic XCD

  bool bIterations = true;  // Remember odd/even iterations
  while (!u.IsZero()) {
    // Step X3. Divide and "Subtract"
    q.Set(&v);
    q.Div(&u, &t2);   // q = u / v, t2 = u % v
    w.Mult(&q, &r);   // w = q * r
    t1.Add(&s, &w);   // t1 = s + w

                      // Swap u,v & r,s
    s.Set(&r);
    r.Set(&t1);
    v.Set(&u);
    u.Set(&t2);

    bIterations = !bIterations;
  }

  if (!v.IsOne()) {
    CLEAR();
    return;
  }

  if (!bIterations) {
    Set(&_P);
    Sub(&s);  /* inv = n - u1 */
  } else {
    Set(&s);  /* inv = u1     */
  }

#endif

#ifdef PENK

  Int r((int64_t)0);
  Int s((int64_t)1);