Incorrect modulo results in Java

Question

I'm trying to run some elliptic curve results in java, but the modulo operator doesn't seem to output the right results.

int a = 17;
double previousx = 4; 
double previousy = 14;
double xnew;
double ynew;
double sigma;
double convert;

for (int i = 1; i < 10; i++) {
    convert = 0;
    for (int j = 0; i<60; j++) {
        if (((2 * previousy * j) % 59) == 1) {
            convert = j;
            break;
        }
    }

    sigma = ((3 * Math.pow(previousx, 2) + a) * convert) % 59;
    xnew = ((sigma * sigma) - (2 * previousx)) % 59;
    ynew = (sigma * (previousx - xnew) - previousy) % 59;
    System.out.println((Math.pow(2, i)) + "x P: " + xnew + "," + ynew + " Sigma:" + sigma);
    previousx = xnew;
    previousy = ynew;
}

output of the first iteration:

2.0x P: 8.0,-57.0 Sigma:55.0

8 and 55 are correct, but -57 mod 59 = 2 and not -57. How do I fix this?

See [Mod in Java produces negative numbers](http://stackoverflow.com/a/5385053/1762224) — Mr. Polywhirl, Mar 09 '14 at 17:40
Look at http://stackoverflow.com/questions/4403542/how-does-java-do-modulus-calculations-with-negative-numbers — Dmitry Bychenko, Mar 09 '14 at 17:40

score 8 · Answer 1 · answered Mar 09 '14 at 17:39

8

8 and 55 are correct, but -57 mod 59 = 2 and not -57. How do I fix this?

The % operator in Java isn't modulus - it's the remainder operator. It's behaving entirely correctly according to the language specification. When you suspect that Java is misbehaving, it's always worth checking the specification to see whether it's actually your expectations which are incorrect.

If you want a modulus operator, you just need to check whether the result is negative, and if so add the divisor again:

int remainder = (2 * previousy * j) % 59;
int modulus = remainder < 0 ? remainder + 59 : remainder;
if (modulus == 1) {
    ...
}

Alternatively, in your case:

int remainder = (2 * previousy * j) % 59;
if (remainder == 1 || remainder == -58) {
    ...
}

... and adjust the rest of your uses of % as appropriate too, of course.

Additionally, as Stijn de Witt mentioned, it looks like you've got a typo in your inner loop condition.

answered Mar 09 '14 at 17:39

Jon Skeet

1,421,763
867
9,128
9,194

Damn, you jumped right on this question Jon. Do you have an RSS feed of the latest SO questions? – Mr. Polywhirl Mar 09 '14 at 17:41
@Mr.Polywhirl: No, but I can hit my "new questions" bookmark pretty rapidly ;) – Jon Skeet Mar 09 '14 at 17:41
2

I thought I might beat Jon for once, lol. Not a chance of course :) – Stijn de Witt Mar 09 '14 at 17:43
1

@StijndeWitt: Well you spotted something that I hadn't - I was posting mostly based on the last sentence of the post... – Jon Skeet Mar 09 '14 at 17:43

score 3 · Answer 2 · answered Mar 09 '14 at 17:40

It looks to me like you have a typo in the inner loop:

for (int j = 0 ; i<60 ; j++)

It says i<60 in a loop that is iterating over j...

I'd try fixing that.

As to the original question... Can you reduce your test case? If you maintain that modulo is not working correctly for some numbers then why not make a single statement that does a modulo on those numbers and prints the results?

Incorrect modulo results in Java

2 Answers2