Java modular inverse

Question

I'm doing some error correction in Java and to cut a long story short;

Under mod 11:

-4 mod 11 = 7

This I've confirmed by using Google's calculator and a couple of online modulo calculators, but I cannot for the life of me figure out how to do it in Java.

I'm thinking that I need to use an inverse table to find the correct number but I seem to be going round in circles.

Any input would be appreciated.

Thank in advance

Tony

NPE · Accepted Answer · 2011-10-23T22:29:38.397

6

The following will compute n mod 11 for any integer n:

(n % 11 + 11) % 11

The result of n % 11 is in the range -10...10. The subsequent addition and the second modulo operation add 11 to n % 11 iff the latter is negative.

This formula works for any base: just replace 11 with another positive integer.

edited Oct 23 '11 at 22:29

answered Oct 23 '11 at 22:24

NPE

486,780
108
951
1,012

1

Or in general for `n` mod `y`: `(n % y + y) % y`. – clstrfsck Oct 23 '11 at 22:26
Thank you very much! That was driving me crazy :) – Tony Oct 23 '11 at 22:26

score 3 · Answer 2 · edited May 23 '17 at 11:53

3

It'd be pretty simple to just write a mod function which does what you require. Example here:

private int mod(int x, int y)
{
    int result = x % y;
    if (result < 0)
    {
        result += y;
    }
    return result;
}

It's much clearer than using % 11 + 11) % 11, and the operation makes sense immediately when you look at it. mod(32, 11) is more clearly 32 mod 11 than (32 % 11 + 11) % 11, and it saves an extra % operation.

edited May 23 '17 at 11:53

Community

1
1

answered Oct 23 '11 at 22:28

... and it costs an extra test and branch. – user207421 Oct 24 '11 at 02:25
[This](http://stackoverflow.com/questions/989943/weird-objective-c-mod-behavior/990007#990007) answer and comments on it provide my reasoning. Mod is likely a more expensive CPU operation compared to a test and branch. It may not even end up branching. – Oct 24 '11 at 03:22
Yes, I read it. I guess I will never understand why computer programmers are so terrified of arithmetic, given that formula translation is how it all started. – user207421 Oct 24 '11 at 03:52

score 1 · Answer 3 · answered Oct 23 '11 at 22:26

1

According to the Java Language Spec, Java's % operator is a remainder operator, not a modulo operator.

answered Oct 23 '11 at 22:26

ObscureRobot

7,306
2
27
36

score 0 · Answer 4 · answered Jul 09 '22 at 16:04

0

I have a method that can calculate the mode inverse of a. TC O(logm) SC O(logm). We are using the Euclid algorithm: “a and m are co-primes if GCD(a,m) == 1”. Please use the link below.

Stackoverflow post

answered Jul 09 '22 at 16:04

Mohammad

6,024
3
22
30

score 0 · Answer 5 · answered Oct 23 '11 at 22:25

0

I think if you take the positive modulo (4 mod 11) and subtract from the latter value it should give you the right answer every time. (i.e. 11 - (4 mod 11) = 7) I haven't really gone through and tested it but it seems to make sense.

answered Oct 23 '11 at 22:25

Josh

36
3

score 0 · Answer 6 · answered Oct 23 '11 at 22:26

0

Try using BigInteger#mod.

answered Oct 23 '11 at 22:26

Trevor Tippins

2,827
14
10

Java modular inverse

6 Answers6