Calculating 13 (mod 2436) (Modulo)

[spartyjohnson]

I feel so very stupid right now. I understand modulus...this is not a hard task. What I am having difficulty with is how to calculate something similar to above (a = b (mod m) <-- note parenthesis, this makes it different from modulus). I am writing the answer to a Java project for my Discrete Math class. I have searched google, answers.com and neowin for how to calculate this, but to no avail. I think I need to take a break and see if I can get some neowin assistance.

What I do know is that a -13 should be a multiple of 2436...however when I do this I don't get the same answer my professor, and sites on the internet show.

Also a mod m == b mod m. But that doesn't seem to work for me either.

Is anybody on Neowin able to help here? Thank you!

[benjaminzsj]

a is the remainder, is this your confusion?

[spartyjohnson]

  benjaminzsj said:

a is the remainder, is this your confusion?

You are thinking Mosulus, I am looking for Modulo. I think I figured it out somewhat though. In the example above it would be 937 is congruent to 13 (mod 2436)...this is because 937*13 = 12181 and is one off of a multiple of 2436. I don't quite understand why. My current algorithm works, but is dog slow.

I am using relatively small numbers too (in the billions). Anybody know a good method for calculating Modulo in Java?

[mpat1024]

13 mod 2436 is just 13.

Basically divide 13 by 2436 and take the remainder.

2436 mod 13 is 5, as 2436/13 = 187 r.5

[spartyjohnson]

  mpat1024 said:

13 mod 2436 is just 13.

Basically divide 13 by 2436 and take the remainder.

2436 mod 13 is 5, as 2436/13 = 187 r.5

Again, that is not the issue. Noticed parenthesis--> 13 (mod 2436).

The answer is not 13 in this case.

I have figured this part out. My next question is: I am having trouble writing a Java Method for calculating MODULO. Could anybody provide such info on a method?

[mastermate]

  spartyjohnson said:

I don't get the same answer my professor, and sites on the internet show.

What answer do they show?

[azcodemonkey]

You're looking for congruence, right?

b = c (mod m)

so

(b-c)/m would be congruent if the result is an integer, as I understand it.

I ran a test from 1 to 25000 and came up with:

13

2449

4885

7321

9757

12193

14629

17065

19501

21937

24373

http://mathworld.wolfram.com/Congruence.html

[spartyjohnson]

  mastermate said:

What answer do they show?

They show 937...which I partially understand now. I am beginning to believe that "congruent" means off by 1. So 937 * 13 = 12181 and 12180 is a multiple of 2436 (2436*5). Thus 937 is congruent to 13 (mod 2436). I think I may have figured out that I can use the Chinese Remainder Thereom to find the modulo. Can anybody confirm this? And could anybody provide any insight as to how?

I guess I should explain the project a little. We are writing an RSA Encryption/Decryption algorithm. Part of calculating the decryption key uses your existing private keys and the modulo (Not Modulus) to find the inverse of the encryption key (Exponent as it is called). So since this is dealing with encryption/decryption keys they can become very large (to deter cracking). My current algorithm is very slow, and this is for small keys. So could anybody help?

  azcodemonkey said:

You're looking for congruence, right?

b = c (mod m)

so

(b-c)/m would be congruent if the result is an integer, as I understand it.

I ran a test from 1 to 25000 and came up with:

13

2449

4885

7321

9757

12193

14629

17065

19501

21937

24373

http://mathworld.wolfram.com/Congruence.html

You seem to know what you are taking about. Could I use the Chinese Remainder Thereom to speed up my decryption? See my post above.

Right now finding the inverse key (de) of e takes a few seconds. This is with small numbers too.

[benjaminzsj]

  Quote

I am beginning to believe that "congruent" means off by 1.

This is wrong, you might want to take a close look at the RSA algorithm. "off by 1" is required by RSA, not the definition of congruent. Maybe you were saying ed=1 mod f(n),?where f(n)=(p-1)(q-1).

I don't know about Java, but you can't use int or whatever?is already a simple type in C, they are not big enough. You have to create a new self-defined type to implement RSA.

[spartyjohnson]

  Staind said:

This is wrong, you might want to take a close look at the RSA algorithm. "off by 1" is required by RSA, not the definition of congruent. Maybe you were saying ed=1 mod f(n), where f(n)=(p-1)(q-1).

I don't know about Java, but you can't use int or whatever is already a simple type in C, they are not big enough. You have to create a new self-defined type to implement RSA.

I have some algorithms that I can use for really big numbers. They don't use native data types, but actually store numbers as binary and perform the simple binary algebra. This isn't my problem. I am trying to figure out how this whole modulo thing works. I am going to try the Chinese Remainder Thereom with P,Q, and N and see if it comes up correctly. I also have class tomorrow night, so I am going to ask my professor what I should be doing. Thank you for responding!

[Andareed]

There seems to be a lot of confusion over terminology.

"a modulo n", written "a (mod n)" or "a % n", typically denotes finding the remainder of n divided by a. The term modulus is typically used in RSA and refers to n=pq. It can also refer to the "n" in "a (mod n)". Also note that one style (the one I use) is to bracket "mod n", but it is acceptable to omit the brackets. The two forms mean the same thing (i.e parentheses don't matter).

If a = b (mod n) we say that "a is congruent to b modulo (or mod) n". This means that a - b = kn for some k. So for example 2 = 9 = 16 = 23 (mod 7).

The OP is trying to compute inverses (mod n). That is, given "a" the OP wants to find "b" such that ab = 1 (mod n) with b between 0 and n-1 inclusive. We say that b = a^-1 (mod n). In the example given, the OP notes that 13^-1 = 937 (mod 2436). To see this is true, we note that 13*937 = 1 (mod 2436), since 13*937 - 1 = 5*2436 (so k = 5).

You can do this using the Extended Euclidean Algorithm, which you can read about on wikipedia.

[spartyjohnson]

So this seems to be one of those things in life where we are our worst enemy. The concept is simple, but I failed to allow myself to comprehend this subject. I now get it! I would like to thank those that were able to provide me with the information I needed to get this problem solved.