Method InverseMod

src/cryptlib/integer.cpp:2116–2139

}

Integer Integer::InverseMod(const Integer &m) const
{
    assert(m.NotNegative());

    if (IsNegative() || *this>=m)
        return (*this%m).InverseMod(m);

    if (m.IsEven())
    {
        if (!m || IsEven())
            return Zero();  // no inverse
        if (*this == One())
            return One();

        Integer u = m.InverseMod(*this);
        return !u ? Zero() : (m*(*this-u)+1)/(*this);
    }

    SecBlock<word> T(m.reg.size * 4);
    Integer r((word)0, m.reg.size);
    unsigned k = AlmostInverse(r.reg, T, reg, reg.size, m.reg, m.reg.size);
    DivideByPower2Mod(r.reg, r.reg, k, m.reg, m.reg.size);
    return r;
}

// ********************************************************