Scribd
Upload
5 views13 pages

Understanding Modular Arithmetic Basics

Modular arithmetic is a mathematical concept crucial in cryptography, focusing on the remainder when integers are divided by a modulus. Key properties include commutative, associative, and distributive laws, as well as congruence relations. Important points to remember include that N mod M gives the remainder, and if N is less than M, then N mod M equals N.

Uploaded by

luckymlcvl
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
5 views13 pages

Understanding Modular Arithmetic Basics

Modular arithmetic is a mathematical concept crucial in cryptography, focusing on the remainder when integers are divided by a modulus. Key properties include commutative, associative, and distributive laws, as well as congruence relations. Important points to remember include that N mod M gives the remainder, and if N is less than M, then N mod M equals N.

Uploaded by

luckymlcvl
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

Modular Arithmetic

Modular Arithmetic
• Central mathematical concept in cryptography.
• It is an arithmetic for integers that focus on the
reminder.
• Wrap around after reaching a certain value called
a modulus.
• Definition: “If a is an integer and n is a positive
integer, we define a mod n to be the remainder
when a is divided by n”. The integer n is called the
modulus.
a = qn + r where 0 ≤ r < n; q = [a/n];
Modulus with an analogy
• Clock analogy
Modulus with an analogy
Congruence
• In cryptography, congruence (≡) instead of
equality (=).
Valid or invalid ?
Properties of Modular Arithmetic
• [(a mod n) + (b mod n)] mod n = (a + b) mod n.
• [(a mod n) - (b mod n)] mod n = (a - b) mod n.
• [(a mod n) x (b mod n)] mod n = (a x b) mod n.
Example
Properties of Modular Arithmetic
Property Expression

Commutative laws • (a + b) mod n = (b + a) mod n


• (a x b) mod n = (b x a) mod n

Associative laws • [(a + b) + c] mod n = [a + (b + c)] mod n


• [(a x b) x c] mod n = [a x (b x c)] mod n

Distributive law • [a x (b + c)] mod n = [(a x b) + (a x c)] mod n


Identities • (0 + a) mod n = a mod n
• (1 x a) mod n = a mod n

Additive inverse • For each a  Zn, there exists a ‘-a’ such that
a + (-a)  0 mod n
Exercise
• 18 mod 12
• 24 mod 12
• 32 mod 12
• 4 mod 12
• 8 mod 12
Properties of Congruence
1. a ≡ r (mod n) if r is the remainder obtained
by dividing a by n.
2. Reflexivity : a ≡ a (mod n)
3. Symmetry:
a ≡ b (mod n) implies b ≡ a (mod n)
4. Transitivity:
a ≡ b (mod n) and b ≡ c (mod n) implies
a ≡ c (mod n).
Points to remember
• N mod M = Remainder.
• If N is less than M then N mod M = N.
• For negative numbers consider anti-clockwise
direction.

You might also like