• 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

    • It's a Dell color laser printer. Back when Microsoft kept having these security flaws with the print spooler and recommending you disable it I just got in the habit of it, and I use it so rarely now I just leave it disabled in case another flaw pops up.
    • KDE makes progress toward full Wayland session restore in Plasma 6.5 by David Uzondu In the latest issue of This Week in Plasma, the development team, as usual, brings news of ongoing work for the desktop environment. While KDE continues to polish the recently released Plasma 6.4, work has already taken off on the next major version of Plasma, 6.5. A significant step forward is being made on Wayland session restoration; the xx-session-management-v1 restore protocol has been implemented in Qt 6.10, which means KDE applications and Plasma itself can soon start using it to finally bring proper session restore to Wayland. For more immediate user-facing changes in Plasma 6.5, the Welcome Center application now teaches you about the many available keyboard shortcuts, as well as "what the heck the 'Meta' key is." For those who frequently work remotely, Plasma's built-in RDP server now supports syncing clipboard text between the client and server. The clipboard also received another useful feature, letting you copy the QR code for an item, not just view it. The team is also addressing smaller usability issues across the desktop, including fixes that will land in point releases for Plasma 6.4. Spectacle, for example, will no longer show a ghostly semi-transparent version of its menus in screenshots. The New! badge, which was introduced in Plasma 6.4 is now easier to read with better colors. Other notable UI improvements include: A new button on the "missed notifications" pop-up that lets you view what you actually missed. The Networks widget is now much better at telling you what it is doing, like when it is "looking for wireless networks". Inertial scrolling with touchpads is now active in all QtQuick-based KDE software. As always, the KDE team spent the week squashing bugs across various versions of Plasma and related software. Plasma 6.4.1, which went live this Tuesday, addressed several crashes in the desktop portal implementations and patched the open/save dialog, where apps could insert extra UI elements in the wrong places. It also resolved a recent performance regression affecting some games and fixed a strange issue with drawing tablets where the pointer could disappear when two were connected in different modes. 6.4.1 tackled a particularly odd hardware-specific problem with Samsung Odyssey G5 monitors endlessly turning on and off because of a faulty DDC implementation. KDE responded by blacklisting the device. In addition to that, the update fixed an accessibility regression in Discover, corrected an issue where deleting a favorited app left behind a ghost item you couldn't un-favorite, and restored the Window List widget's ability to minimize windows. As for fixes planned for 6.4.2, here's the full list as outlined by the Plasma team: Fixed a case where System Settings' Flatpak App Permissions page could cause the whole app to crash. Fixed an issue that could sometimes cause Plasma to go back to sleep again right after waking up, when the "Sleep then hibernate" setting is in use. The appearance of text labels in Folder View pop-ups is once again correct. You're no longer erroneously prompted to authenticate for a Wireguard VPN whose credentials are already stored in KWallet, and the wallet is set up to automatically open at login. Fixed an issue in the KDE desktop portal's screenshot implementation that prevented the delay setting from taking effect. Missing app backends listed in Discover's Settings page once again show the correct names. The brightness level shown on System Settings' Display & Monitor page now matches the one shown in Plasma. Fixed an issue that caused the panel to have too much space in it until restarting Plasma if you stop displaying the date on a horizontally-laid-out Digital Clock widget. The older Plasma 6.3.6 fixed video stuttering on variable-refresh-rate screens and patched the Weather Report widget after Environment Canada changed its data format. You can check out the full update on the official KDE Blog.
    • I'm happy with my setup. I have a raid 1 two drive Synology setup that I backup with Time Machine to every so often. What is your setup at home? 
    • Enterprise support (ex. Premier Support) is a bit different cup of coffee. I am not saying it is great, but they have SLAs and I have received solution within hours and even patches within 3 days.
    • Thank you, for not reading the comments above and just reading the root comment... it is just like reading only the headline of an article.
  • Recent Achievements

    • One Year In
      TsunadeMama earned a badge
      One Year In
    • Week One Done
      shaheen earned a badge
      Week One Done
    • Dedicated
      Cole Multipass earned a badge
      Dedicated
    • Week One Done
      Alexander 001 earned a badge
      Week One Done
    • Week One Done
      icecreamconesleeves earned a badge
      Week One Done
  • Popular Contributors

    1. 1
      +primortal
      569
    2. 2
      ATLien_0
      187
    3. 3
      +FloatingFatMan
      184
    4. 4
      Skyfrog
      112
    5. 5
      Som
      108
  • Tell a friend

    Love Neowin? Tell a friend!