Division:
If a and b are integers with
a ≠ 0, we say that a
divides b if there is an integer
c such that b = ac,
or equivalently, if b/a is an integer.
When a divides b
we say that a is a factor.
Modular Arithmetic: 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. We use the notation a ≡ b (mod m) to indicate that a is congruent to b modulo m. We say that a ≡ b (mod m) is a congruence and that m is its modulus (plural moduli). If a and b are not congruent modulo m, we write a ≢ b (mod m).
Modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" upon reaching a certain value -- the modulus (plural moduli)
Corollary: 1. If a, b, and c
are integers, where a ≠ 0, such that a |
b and a | c, then a | mb
+ nc whenever m and n are integers.
2. Let m be a positive integer and let a and
b be integers. Then (a + b) mod
m = ((a mod m) + (b mod
m)) mod m and ab mod m =
((a mod m)(b mod m)) mod
m.
The most common representation of a positive integer is a string of bits, using the binary numeral system. The order of the memory bytes storing the bits varies; see endianness. The width or precision of an integral type is the number of bits in its representation. An integral type with n bits can encode 2n numbers; for example an unsigned type typically represents the non-negative values 0 through 2^{n} − 1. Other encodings of integer values to bit patterns are sometimes used, for example Binary-coded decimal or Gray code, or printed character codes such as ASCII.
The algorithms for performing operations with integers using their binary expansions are extremely important in computer arithmetic.
We will describe algorithms for the addition and the multiplication of two integers expressed in binary notation.
A prime is an integer that is divisible by two positive integers, 1 and itself.
Prime numbers are quite important as they are used in modern cryptographic systems. The length of time required to factor large integers into their prime factors is the basis for the strength of these systems.
Definition 1: An integer p greater than 1 is called prime if the only positive factors of p are 1 and p. A positive integer that is greater than 1 and is not prime is called composite.
Definition 2: If n is a composite integer, then n has a prime divisor less than or equal to √ n .
There are few conjectures which have not yet been proved. Below are few conjectures whose proofs has not been found
Greatest common divisor (gcd) The largest integer that divides both of two integers.
Euclidean Algorithm
Computing gcd using prime factorization is
a time consuming process. The Euclidean
algorithm gives an `efficient way
to compute gcd.
Steps
To find gcd(a, b)
Linear Congruences A congruence of the form ax ≡ b (mod m), where m is a positive integer, a and b are integers, and x is a variable, is called a linear congruence.
We need to find the values of x which will solve the congruence. The theorem below, gives one such method to solve congruences.
Theorem 1 If a and m are relatively prime integers and m ≥ 1, then an inverse of a modulo m exists which is unique. And every inverse of a modulo m is congruent to a modulo m.
Let m_{1},m_{2}, ... , m_{n} be pairwise relatively prime positive integers greater than 1 and a_{1}, a_{2}, ... , a_{n} be arbitrary integers. Then, x ≡ a_{1} (mod m_{1}), x ≡ a_{2} (mod m_{2}), x ≡ a_{n} (mod m_{n}) has a unique solution modulo m &euiv; m_{1}m_{2} ∗ ∗ ∗m_{n}. (That is, there is a solution x with 0 ≤ x < m, and all other solutions are congruent modulo m to this solution.)
If p is prime and a is an integer not divisible by p, then a^{p − 1 } ≡ 1 (mod p). Furthermore, for every integer a we have a^{p} ≡ a (mod p).
Congruences are applied in many fields of computer Science, like assigning memory address to file systems, generating pseudorandom numbers, check digits etc.
Records in database are stored and identified using unique id.
These id's are stored at a location formed using
hashing functions.
A hashing function assigns memory address h(k) to a record that has key k.One of the most common used for this is h(k) = k (mod m)
To find h(k), we need only compute the remainder when k is divided by m. Furthermore, the hashing function should be onto, so that all memory locations are possible
Linear congruential method is generaly used for generating pseudorandom numbers.We need four integers
a pseudorandom number {x_{n}} is recursively generated such that 0 ≤ x_{n} < m for all n x_{n+1} = (a x_{n} + c) mod m
These are used to verify correctness of a particular string, and finds its application in digital information, verifying product codes etc.
An extra digit is added at the end of string. This final digit is then checked to see whether the value is correct or not
Cryptography is a way of concealing messages from everyone except from reciever and sender and is also used for authentication
In classical cryptography, the letters were replaced by one less than the position of alphabet (for example: A is replaced by 0, Z by 25) and then adding 3 to the number, which is equivalent to shifting the letter by 3
Private key cryptography requires the key which is used to encrypt the message to be shared between the recieveing and sending parties. Hence, public key cryptosystems where introduced. In this knowing how to send an encrypted message does not help decrypt messages.
In the RSA cryptosystem, each individual has an encryption key (n, e) where n = pq, the modulus is the product of two large primes p and q, and an exponent e that is relatively prime to (p − 1) (q − 1).To produce a usable key, two large primes must be found.
A plaintext message M is converted into a sequence of integers m_{1}, m_{2}, . . . , m_{k} for some integer k. Encryption proceeds by transforming each block m_{i} to a ciphertext block c_{i} . This is done using the function C = M^{e} mod n.
The plaintext message can be quickly recovered from a ciphertext message when the decryption key d, an inverse of e modulo (p − 1)(q − 1), is known. An inverse surely exists because gcd(e, (p − 1)(q − 1)) = 1
RSA is used as public key system as it is easily possible to construct a public key by finding two large primes p and q, and to find an integer e relatively prime to (p − 1) (q − 1). When we know p and q, we can easily compute the inverse d of e modulo (p − 1) (q − 1).
Factorization is difficult as opposed to finding large primes p and q. The most efficient factorization methods known require billions of years to factor 400-digit integers.
Cryptographic protocol is exchange of messages between two parties over an insecure communication channel. This requires forming a key to be shared between both parties.
the following protocol is followed:
The protocol ensures that k1, k2, and the common key are kept secret,no other method is known for finding the shared key using just the public information.