• 0

Calculating 13 (mod 2436) (Modulo)


Question

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!

Link to comment
https://www.neowin.net/forum/topic/553858-calculating-13-mod-2436-modulo/
Share on other sites

11 answers to this question

Recommended Posts

  • 0
  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?

  • 0
  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?

  • 0

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

  • 0
  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.

  • 0
  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.

  • 0
  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!

  • 0

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.

  • 0

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.

This topic is now closed to further replies.
  • Recently Browsing   0 members

    • No registered users viewing this page.
  • Posts

    • ALL surveys are voluntary and very few attempt to track the same percipients over time. That doesn't mean they are invalid. Value doesn't claim it is an aggregate of their entire user base, that is why they call it as survey, which means exactly what it is. Yes, if Value created an anonymized collection of ALL users, that would be more accurate than a survey, but that is something they choose not to do. Just like elections are more accurate than political surveys.
    • Just use AI...chatgpt or Copilot will write code for you, then test that and tweak it if needed.
    • One UI 8 reveals Samsung's upcoming tri-fold phone by Taras Buria Samsung Galaxy Flex G prototype shown earlier this year. Source: Samsung Samsung was the pioneer of mainstream foldable phones. Despite the rocky start, the company cemented itself as the go-to option for those who want something more exciting than the standard, boring slab phone. However, during recent years, Samsung foldable phones became a bit stagnant and a target of heavy criticism in light of China-made ultra-thin devices and even tri-folding phones. Now, Samsung is getting ready to strike again. The South Korean giant is holding a special event next week where it is expected to unveil a bunch of new folding phones, including a cheaper Z Flip FE variant. However, the most exciting part of the announcement could be Samsung's first tri-folding smartphone, details about which were discovered in the latest One UI 8 beta build. The uncovered animations reveal a device that is similar to the Galaxy Fold 6 with one extra screen. It shows a tri-camera module and the location of its NFC chip. The inner display houses a punch-hole camera in the upper-right corner. Judging by the looks of it and another punch-hole camera, it appears that when fully unfolded, the outer screen will sit between two panels. Samsung seems to be taking a different route than Huawei, equipping its smartphone with two inward-folding hinges (as shown by the recent Galaxy Flex G concept). It is worth noting that those hinges are not identical, and the phone will have a strict folding procedure. Another animation revealed the phone displaying a warning not to fold the camera side first to prevent screen damage from the camera island. The device name is currently unknown, and the One UI 8 beta build does not reveal much except for "MULTIFOLD7" with its "vertical main," "main," and "reverse main" displays. The exact naming and renders could leak days ahead of the presentations, so Samsung fans should stay tuned for more details. Source: Android Authority
    • In the civilized world, yes. But not in the US of A...
    • The entire western economy is based on the lie that internet ads lead to real sales.
  • Recent Achievements

    • Week One Done
      Devesh Beri earned a badge
      Week One Done
    • Week One Done
      956400 earned a badge
      Week One Done
    • First Post
      loose_observer earned a badge
      First Post
    • Week One Done
      BeeJay_Balu earned a badge
      Week One Done
    • Week One Done
      filminutz earned a badge
      Week One Done
  • Popular Contributors

    1. 1
      +primortal
      449
    2. 2
      ATLien_0
      158
    3. 3
      +FloatingFatMan
      150
    4. 4
      Nick H.
      65
    5. 5
      +thexfile
      62
  • Tell a friend

    Love Neowin? Tell a friend!