Блог пользователя rhezo

Автор rhezo, история, 8 лет назад, По-английски

I need to do integer division, that is floor of A/B. Eg: 5/2 = 2.

Now consider the modulo to be prime, multiplying A with inverse of B and taking modulo is wrong.

What I said above is true because , 6 * inverseOf(2) = 3. But 5 * inverseOf(2) is not equal to 2.

So how can I do this?

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +37 Проголосовать: не нравится

If I understood correctly, what you want is to find some function f such that given A mod P = a , B mod P = b , then floor(A/B) = f(a,b) . This is obviously impossible. Consider this simple example:

Take P = 7. Since floor(11/3) = 3, then f(4,3) should be 3. But since floor(4/3) = 1, then f(4,3) should be 1 and we have a contradiction.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    No I meant that once we have a and b(as defined above), can we find A/B(integer division) as (a*inverse(b)) mod P? But I guess it can't be done.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      No, we cannot do that. Modular inverse has nothing to do with integer division, even though names sound similar.

      Another example: suppose P = 11, A = 13 (2 modulo P), B = 2. Then inverse(B) = 6 (because 2·6 = 12 = 1), but A·inverse(B) = 1, which is obviously not the answer expected.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

What about using the fact that Integer division of A by B is same as (A — A % B) / B ? After this you can use modular inverses, either directly if prime or using extended euclid algorithm.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится -7 Проголосовать: не нравится

    Looks good, but for this I would have to maintain A%B too always. Since I wanted to do everything modulo some prime P initially, I would maintain everything modulo P only and it can get messy if B changes over many queries. For a single B, this would work I think.

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

You may find A mod (B*n) = a, then A/B = a/B mod n