static TBigInteger modInverseMontgomery(TBigInteger a,TBigInteger p){
  if (a.sign == 0) {
    throw new ArithmeticException("BigInteger not invertible");
  }
  if (!p.testBit(0)) {
    return modInverseHars(a,p);
  }
  int m=p.numberLength * 32;
  TBigInteger u, v, r, s;
  u=p.copy();
  v=a.copy();
  int max=Math.max(v.numberLength,u.numberLength);
  r=new TBigInteger(1,1,new int[max + 1]);
  s=new TBigInteger(1,1,new int[max + 1]);
  s.digits[0]=1;
  int k=0;
  int lsbu=u.getLowestSetBit();
  int lsbv=v.getLowestSetBit();
  int toShift;
  if (lsbu > lsbv) {
    TBitLevel.inplaceShiftRight(u,lsbu);
    TBitLevel.inplaceShiftRight(v,lsbv);
    TBitLevel.inplaceShiftLeft(r,lsbv);
    k+=lsbu - lsbv;
  }
 else {
    TBitLevel.inplaceShiftRight(u,lsbu);
    TBitLevel.inplaceShiftRight(v,lsbv);
    TBitLevel.inplaceShiftLeft(s,lsbu);
    k+=lsbv - lsbu;
  }
  r.sign=1;
  while (v.signum() > 0) {
    while (u.compareTo(v) > TBigInteger.EQUALS) {
      TElementary.inplaceSubtract(u,v);
      toShift=u.getLowestSetBit();
      TBitLevel.inplaceShiftRight(u,toShift);
      TElementary.inplaceAdd(r,s);
      TBitLevel.inplaceShiftLeft(s,toShift);
      k+=toShift;
    }
    while (u.compareTo(v) <= TBigInteger.EQUALS) {
      TElementary.inplaceSubtract(v,u);
      if (v.signum() == 0)       break;
      toShift=v.getLowestSetBit();
      TBitLevel.inplaceShiftRight(v,toShift);
      TElementary.inplaceAdd(s,r);
      TBitLevel.inplaceShiftLeft(r,toShift);
      k+=toShift;
    }
  }
  if (!u.isOne()) {
    throw new ArithmeticException("BigInteger not invertible.");
  }
  if (r.compareTo(p) >= TBigInteger.EQUALS) {
    TElementary.inplaceSubtract(r,p);
  }
  r=p.subtract(r);
  int n1=calcN(p);
  if (k > m) {
    r=monPro(r,TBigInteger.ONE,p,n1);
    k=k - m;
  }
  r=monPro(r,TBigInteger.getPowerOfTwo(m - k),p,n1);
  return r;
}

static TBigInteger modInverseMontgomery ( TBigInteger a , TBigInteger p ) { if ( a . sign == 0 ) { throw new ArithmeticException ( "BigInteger not invertible" ) ; } if ( ! p . testBit ( 0 ) ) { return modInverseHars ( a , p ) ; } int m = p . numberLength * 32 ; TBigInteger u , v , r , s ; u = p . copy ( ) ; v = a . copy ( ) ; int max = Math . max ( v . numberLength , u . numberLength ) ; r = new TBigInteger ( 1 , 1 , new int [ max + 1 ] ) ; s = new TBigInteger ( 1 , 1 , new int [ max + 1 ] ) ; s . digits [ 0 ] = 1 ; int k = 0 ; int lsbu = u . getLowestSetBit ( ) ; int lsbv = v . getLowestSetBit ( ) ; int toShift ; if ( lsbu > lsbv ) { TBitLevel . inplaceShiftRight ( u , lsbu ) ; TBitLevel . inplaceShiftRight ( v , lsbv ) ; TBitLevel . inplaceShiftLeft ( r , lsbv ) ; k += lsbu - lsbv ; } else { TBitLevel . inplaceShiftRight ( u , lsbu ) ; TBitLevel . inplaceShiftRight ( v , lsbv ) ; TBitLevel . inplaceShiftLeft ( s , lsbu ) ; k += lsbv - lsbu ; } r . sign = 1 ; while ( v . signum ( ) > 0 ) { while ( u . compareTo ( v ) > TBigInteger . EQUALS ) { TElementary . inplaceSubtract ( u , v ) ; toShift = u . getLowestSetBit ( ) ; TBitLevel . inplaceShiftRight ( u , toShift ) ; TElementary . inplaceAdd ( r , s ) ; TBitLevel . inplaceShiftLeft ( s , toShift ) ; k += toShift ; } while ( u . compareTo ( v ) <= TBigInteger . EQUALS ) { TElementary . inplaceSubtract ( v , u ) ; if ( v . signum ( ) == 0 ) break ; toShift = v . getLowestSetBit ( ) ; TBitLevel . inplaceShiftRight ( v , toShift ) ; TElementary . inplaceAdd ( s , r ) ; TBitLevel . inplaceShiftLeft ( r , toShift ) ; k += toShift ; } } if ( ! u . isOne ( ) ) { throw new ArithmeticException ( "BigInteger not invertible." ) ; } if ( r . compareTo ( p ) >= TBigInteger . EQUALS ) { TElementary . inplaceSubtract ( r , p ) ; } r = p . subtract ( r ) ; int n1 = calcN ( p ) ; if ( k > m ) { r = monPro ( r , TBigInteger . ONE , p , n1 ) ; k = k - m ; } r = monPro ( r , TBigInteger . getPowerOfTwo ( m - k ) , p , n1 ) ; return r ; }
calculates a . modinverse ( p ) based on : savas , e ; koc , c " the montgomery modular inverse - revised "
