Modular arithmetic

As the name says, LongModulus is a pretty long (lengthy) class implementing modular arithmetic for a long modulus. As overflow is a problem, I implemented two subclasses, one for moduli not using the highest non-sign bit (i.e., smaller than \$2^{62}\$) and one for the others.

The code uses Guava and Lombok. As usual, feel free to ignore my slightly deviating coding conventions.

My concerns are speed and correctness. I've already written a thorough test (not given here as the question is already very long), but haven't benchmarked anything yet.

The TODO markers shows the places I'd like to improve (or features currently missing like pow with negative exponent, but this is not a bug as I haven't needed it yet).

IntModulus

```
import static com.google.common.base.Preconditions.checkArgument;
import lombok.Getter;

/**
* This class provides common modular arithmetic.
* Results of all methods are ints guaranteed to be non-negative and less then modulus.
*/
public final class IntModulus {
private IntModulus(int modulus) {
this.modulus = modulus;
}

public static IntModulus newModulus(int modulus) {
checkArgument(modulus>0);
return new IntModulus(modulus);
}

public int pow(long base, long exp) {
checkArgument(exp>=0); //TODO allow negative exponents
if (modulus==1) return 0;
if (exp==0) return 1;
return powInternal(mod(base), exp);
}

private int powInternal(int base, long exp) {
assert base>=0;
if (base0; exp>>=1) {
if ((exp&1) != 0) result = mul(result, x);
x = square(x);
}
return result;
}

private int square(int x) {
return mul(x, x);
}

public int mul(long x, long y) {
return mul(mod(x), mod(y));
}

public int mul(int x, int y) {
return mod((long) x * y);
}

public int add(int x, int y) {
return mod(x + y);
}

public int sub(int x, int y) {

Assert statements

They're awesome. I should use them more myself, but they're not always appropriate. Let's start with when they're appropriate and then look at how you've used them.

Assert statements are fantastic for internally checking conditions during development. They get compiled away in our release build, so use them liberally anywhere we need to check a precondition... internally, in places where we have direct control on the input and if conditions don't meet our expectations, something is wrong that the dev needs to look into right now. When I say internal, I really mean internal. I'm not up to speed with Java's scoping keywords, but in C# this would be in private, internal, and (maybe) protected methods. Anytime we're in a public method, we need to be a bit more robust with our argument checking, because we have zero control over what the client hands us.

So, back to how you used them.

@Override public final long pow(long base, long exp) {
        checkArgument(exp>=0);  //TODO allow negative exponents
        if (exp==0) return 1;
        base = mod(base);
        assert base>=0;
        if (base0; exp>>=1) {

The method is public and you've done some proper argument checking. (At least I'm going to assume that returning the base is appropriate if it's < 1. Is it?) So, that's good! However, does it really make sense to Assert on a condition that has been gracefully handled? I don't think it does. Minimally, it can cause confusion for someone coming behind you wondering "why are we asserting this in s public method when we've handled that case right there.

Like I said, asserts are awesome, but try to keep them in places where there're likely to catch actual bugs.

StackExchange Code Review Q#94383, answer score: 7