Number Theory & Cryptography Chapter 4

If a and b have the same remainder when divided by m, we say a is congruent to b modulo m, written as a ≡ b (mod m).

If two numbers are congruent to each other modulo m, their sum and product are also congruent to each other's sum and product modulo m.

The addition operation modulo m, written as '+' or '+m', takes two integers, adds them together, and returns the remainder when the result is divided by m.

The multiplication operation modulo m, written as '∙m', takes two integers, multiplied them together, and returns the remainder when the result is divided by m.

The set of non-negative integers from 0 up to m-1

Performing addition and multiplication using the modulo m operations (+m and ∙m).

Multiplying both sides of a congruence by an integer or adding an integer to both sides of a congruence preserves the congruence.

If 'a' is an integer and 'd' is a positive integer, then there exist unique integers 'q' and 'r' such that 0 ≤ r < d and a = dq + r.

The integer being divided in the division algorithm.

The positive integer by which the dividend is being divided in the division algorithm.

The integer 'q' in the division algorithm (a = dq + r).

The integer 'r' in the division algorithm (a = dq + r), where 0 ≤ r < d.

If 'a' and 'b' are integers, and 'm' is a positive integer, then 'a' is congruent to 'b' modulo 'm' if 'm' divides 'a – b'.

'a' is congruent to 'b' modulo 'm'.

Two integers have the same remainder when divided by m.

The modulus in a congruence relation.

For any integers a, b, and c in Zm, (a +m b) +m c = a +m (b +m c) and (a ∙m b) ∙m c = a ∙m (b ∙m c).

For any integers a and b in Zm, a +m b = b +m a and a ∙m b = b ∙m a

0 is the identity element for addition (a +m 0 = a) and 1 is the identity element for multiplication (a ∙m 1 = a) in Zm.

For any integer a ≠ 0 in Zm, m− a is its additive inverse. That is a +m (m− a ) = 0. Zero is its own inverse.

For any integers a, b, and c in Zm, a ∙m (b +m c) = (a ∙m b) +m (a ∙m c) and (a +m b) ∙m c = (a ∙m c) +m (b ∙m c).

A function that assigns a memory location (h(k)) to a record based on its key (k).

When more than one record is assigned to the same memory location by a hashing function.

h(k) = k mod m. k is any key, (mod m) is the remainder when dividing k by m, and m represents the locations.

A method for collision resolution in hashing. h(k,i) = (h(k) + i) mod m. (i runs from 0 to m − 1).

A secret key used for secure communication between Alice and Bob, based on a discrete logarithm problem.

Finding the exponent needed to raise a base to a given power using large numbers.

A way to verify the sender of a message, ensuring authenticity.

A public key pair (n, e) used for encryption in RSA.

A private key (d) used for decryption in RSA.

A process using the public key to encrypt a message.

A process using the private key to decrypt a message.

Ensuring a message came from the claimed sender using digital signatures.

Mathematical process that uses the private key to change ciphertext into plaintext.

Mathematical process that uses the public key to change plaintext into ciphertext.

A digit appended to a Universal Product Code (UPC) to verify its accuracy.

A formula for calculating check digits for Universal Product Codes (UPC): 3x1 + x2 + 3x3 + etc., mod 10.

A Universal Product Code (UPC) whose check digit satisfies the congruence formula resulting in the sum being a multiple of 10 (remainder is 0).

A digit in the International Standard Book Number (ISBN-10) to verify its validity.

A formula for calculating check digits for International Standard Book Numbers (ISBN-10): 1d1 + 2d2 + 3*d3... (mod 11)

An ISBN number where the check digit makes the checksum congruent to 0 (mod 11).

A simple substitution cipher where each letter is shifted a fixed number of positions down the alphabet.

The process of converting readable information into an unreadable format to secure it.

A public-key cryptosystem that uses modular arithmetic to encrypt and decrypt messages. It relies on the difficulty of factoring large numbers to keep the decryption key secret.

In RSA, a key used for encryption that is freely shared and easily made public.

In RSA, a key used for decrypting messages that are encrypted with the corresponding public key. It is not shared and is kept extremely secret.

A system of arithmetic where numbers 'wrap around' after reaching a specific value (the modulus).

Whole numbers greater than 1 that are only divisible by 1 and themselves.

A method for two parties to securely agree on a shared secret key over an insecure communication channel

In modular arithmetic, a number whose powers generate all the numbers in a reduced residue system.

Gives the remainder when one number is divided by another.