When is modular arithmetic used

What about the number 3? How about this:. Weird, but workable. Cool, huh? Where will the hour hand be in 7 hours? So it must be 2. We do this reasoning intuitively, and in math terms:. So, the clock will end up 1 hour ahead, at Well, they change to the same amount on the clock!

We can just add 5 to the 2 remainder that both have, and they advance the same. For all congruent numbers 2 and 14 , adding and subtracting has the same result. But who cares? We ignore the overflow anyway. See the above link for more rigorous proofs — these are my intuitive pencil lines. You have a flight arriving at 3pm. What time will it land? Suppose you have people who bought movie tickets, with a confirmation number. You want to divide them into 2 groups.

What do you do? Now there are various ways to work in fields and rings, but moduli are easy to understand and analyze and come pre-shipped with algebraic operations. The answer is: cryptographers use different finite constructions and make use of the different properties.

In computer science you almost always consider finite sets implicitly: Integers are defined with certain ranges, depending on their bitsize. Arrays have a maximum length when you limit the index to such a limited integer, etc. The only "unlimited" set is strings if there is no max length , but you don't use strings to use calculate something.

So, almost anything we do happens on finite sets. As you can see, the arithmetics in finite constructions are always there, but they are not mentioned explicitly.

It is already clear from "this is an integer". In symmetric crypto, most of the time the usual calculations on "normal" integers are used. But since most of the systems use different integer sizes in their algorithms, the bitsizes are also given explicity, e. In public key crypto, this is done for a different reason: There are different properties in different constructions, which are used to build public key schemes. Based on the construction we can use different assumptions about computational hardness, e.

These assumptions enable the construction of oneway-trapdoor functions, which are used to build public key cryptosystems. Their entire hardness depends fundamentally on the underlying construction, and therefore it is required to define them explicitly. Sign up to join this community. The best answers are voted up and rise to the top. Stack Overflow for Teams — Collaborate and share knowledge with a private group.

Create a free Team What is Teams? Learn more. What is the importance of Modular arithmetic in cryptography? Ask Question. Asked 9 years, 11 months ago. Active 9 years, 11 months ago. Viewed 16k times. Improve this question. I was tempted to remove the "symmetric" tag as I believe that very few if any symmetric ciphers use modular arithmetic.

Someone correct me if I am wrong though. Show 3 more comments. Active Oldest Votes. They work as one may expect. It is possible to use the same commutative, associative, and distributive laws. Inverse numbers in Z N can be determined in time O log 2 N using the Euclidean algorithm , which allows to compute the greatest common divisor of two integers. The final values of the coefficients a and b are received in the same step when the greatest common divisor of x and y is calculated thus, in the step with the last non-zero remainder.