Modulo arithmetic

As explained in Real-World Cryptography

Modular arithmetic is arithmetic in which values are identified according to their remainders after division by a fixed modulus.

Modulo arithmetic makes numbers wrap around after reaching a fixed modulus. With modulus 5, 6 becomes 1, 7 becomes 2, and 5 is represented as 0. section 5.2.1

Use remainders to perform modular arithmetic:

• Divide a number by the modulus and keep the remainder: 7 = 5 × 1 + 2, so 7 is congruent to 2 modulo 5. section 5.2.1
• Reduce multiplication the same way: 3 × 2 = 6, which becomes 1 modulo 5. section 5.2.1
• Recognize inverses among the nonzero values: modulo 5, 3 and 2 are inverses because their product is 1. section 5.2.1

Figure 5.5 The group of integers modulo the prime number 5 can be pictured as a clock that resets to 0 after the number 4. Thus 5 is represented as 0, 6 as 1, 7 as 2, 8 as 3, 9 as 4, 10 as 0, and so on.

Picture the values as a clock that resets to 0 after 4: 5 becomes 0, 6 becomes 1, and 10 becomes 0. section 5.2.1

How Real-World Cryptography covers it

How deep it goes

Defines remainders, demonstrates multiplication and inverses, and connects the operation to multiplicative groups.

Examples

Uses a clock analogy, division by 5, and the product 3 × 2 modulo 5.

What it assumes

Builds from ordinary division and multiplication before introducing congruence notation and group operations.

What you can do after

Apply modular reduction to simple divisions and multiplications, and identify multiplicative inverses modulo 5.

How it connects

Connects modular arithmetic with group theory, prime numbers, modular multiplication, inverses, and Diffie–Hellman.

liveBookmanning.com

Read Real-World Cryptography on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Hacking CryptographyArithmetic in which values are identified according to their remainders modulo a specified integer.
• 

  liveBookmanning.com
  Grokking Data StructuresModular arithmetic is arithmetic in which values are considered equivalent when they have the same remainder under a specified modulus.

Compare how 3 books explain modulo arithmetic →

Related concepts

• size_timplemented by · size_t is an unsigned integer type in C and C++ used to represent object sizes and related counts.
• dataset splitused by · A dataset split is the division of a dataset into distinct subsets assigned different purposes, such as training, validation, or testing.
• integer wraparoundimplemented by · Integer wraparound is arithmetic behavior in which an out-of-range fixed-width integer result cycles or is reduced modulo the type’s representable range.
• elliptic curve point additionused by · Elliptic-curve point addition combines two curve points according to the curve's group law to produce another curve point.
• unsigned integerimplemented by · An unsigned integer is an integer type or representation whose values are nonnegative, with its representable range determined by its bit width and applicable rules.

This explainer was generated by Manning's knowledge graph from the text of Real-World Cryptography. The section links point to the parts of the book it draws on.