java - 反转 int 溢出

Question

int num = -340721550;
int multi =  -214882771;
int result = num * multi; // = 10

如果我知道 multi 和 result，我怎样才能在不暴力破解的情况下返回到 num？

或者提高我的暴力破解方法的速度

public static int multiInverse(int multi, int result){
    for (int i = Integer.MIN_VALUE; i <= Integer.MAX_VALUE; i++){
        if (multi * i == result){
            return i;
        }
    }
    return -1;
}

Answer 1

正如 prior answer 中指出的那样，可以通过计算已知除数的逆模 2^32 来解决该问题。 java.math.BigInteger 有一个 modInverse可以使用的方法。

正如答案中所指出的，相对于模基不是素数的数字没有倒数。在二的幂的背景下，这意味着偶数没有倒数。我通过将除数和乘积均减半来解决这个问题，直到除数为奇数。

不幸的是，我的方法所能做的就是在int算术中找到一个结果，使得divisor * result == Product。这样的数字可能不止一个，因此不一定是您一开始使用的数字。

  private static final BigInteger modulo = BigInteger.ONE.shiftLeft(32);

  public static int unoverflowDivide(int product, int divisor) {
    if (divisor == 0)
        throw new IllegalArgumentException("No solution");
    while((divisor & 1) == 0){
      if ((product & 1) == 1)
          throw new IllegalArgumentException("No solution"); 
      divisor >>= 1;
      product >>= 1;
    }
    BigInteger bigDivisor = BigInteger.valueOf(divisor);
    BigInteger bigProduct = BigInteger.valueOf(product);
    BigInteger bigInverse = bigDivisor.modInverse(modulo);
    BigInteger bigResult = bigInverse.multiply(bigProduct);
    return bigResult.intValue();
  }