Integer Arithmetic

In integer arithmetic, we use a set and few operations. We are familiar with this set and corresponding, but they are reviewed here to create a background for modular arithmetic.

( i ) Set of Integers : The set of integers, denoted by 'Z', contains all integral number ( with no fractions ) from negative infinity to positive infinity. Which is shown as follows


Z = { -∞, ........, -2, -1, 0, 1, 2, ............., +∞ }.


( ii ) Binary operations : In cryptography, we are interested in three binary operations applied to the set of integers. The binary operation takes two integers and create one output. Three common binary operations defined for  integers are addition, subtraction and multiplication. Each of these operations takes two input ( a, b ) and creates one output ( c ) as shown in the following figure.







The following shows the results of the three binary operations on two integers because each input can be either positive or negative, we can have four case for each operation.

Add : 5 + 9 = 14;  ( -5 ) + 9 = 4; 5 + ( -9 ) = -4; ( -5 ) + ( - 9 ) = -14.
Subtract : 5 - 9 = -4;  ( -5 ) - 9 = -14; 5 - ( -9 ) = 14; ( -5 ) - ( - 9 ) = 4.
Multiplication : 5 * 9 = 45;  ( -5 ) * 9 = -45; 5 * ( -9 ) = -45; ( -5 ) * ( - 9 ) = 45.

( iii ) Integer division : In integer arithmetic, if we divide a/n, we can get q and r. The relationship between these four can be shown as follows

a = q * n + r

In this relation, a is called the dividend, q is called quotient, n is called the divisor and r is called the remainder. Note that this is not an operation, because the result of dividing a by n is two integers q and r  we can call it division relation.


Example : Assume that a = 255 and n = 11 we can find q = 23 and r = 2 using the division algorithm.

( iv ) Two restrictions : When we use the above division relationship in cryptography, we impose in two relationships. First we require that the divisor be a positive integer ( n > 0 ), and second we require that he remainder be a non-negative integer ( r ≥ 0 ). The following block diagram illustrate the basic concepts of division algorithm for integers.




Graph of division algorithm



Starting from '0', the graph shows how we can reach the point representing the integer 'a' on the number line. In case of a positive integer 'a', we need to move ( q * n ) units to the right and then move extra 'r' units in the same direction, In case of negative  integer 'a', we need to move ( q- 1) * n units to left ( q is negative in this case ) and then move extra 'r' units int he opposite direction. In both cases the value of  'r' is positive.


Comments

Post a Comment

Popular posts from this blog

Euclid's Algorithm to find greatest common divisior

Image
Greatest common divisor One integer often needed in cryptography is the greatest common divisor of two positive integers. Two positive integer may have many common divisor but only one greatest common divisor. For example, the common divisor of 12 and 140 are 1, 2 and 4. However, 4 is the greatest common divisor.       The greatest common divisor of two integers is largest integer which can divide both given integers. The following block diagram illustrate the basic of the greatest common divisor of 12 and 140. " Euclidean Algorithm " Finding the greatest common divisor ( GCD ) of two positive integers by listing all common divisor is not practical, when the two number integers are large. Fortunately, more than 2000 years ago a mathematician named Euclid develop an algorithm that can find the greatest common divisor of two positive integers. The Euclidean algorithm is based on the following two facts: 1. gcd ( a, 0 ) = a 2. gcd ( a, b ...
Read more

Algebraic System or Algebraic Structure and Group

Algebraic System or Algebraic Strucure " A non-empty set 'G' together with a binary operation ' O' is called an algebraic system or algebraic structure and is denoted by (G,O), (N,+).  " Group "A non-empty set 'G' together with a binary operation 'O' is said to be a group, if the following laws holds for all the operations 'O'." Group holds the following given four laws :    (a) Clouser Law   : 'G' is cloused under the binary operation 'O' that is ( a O b ) = ( b O a )  ∀ a, b ᗴ G . (b) Associative Law : The associative law for the operation holds that is  a O ( b O c ) = ( a O b ) O c  ∀ a, b, c ᗴ G. (c) Existence of Identity Element :  The identity element exists in 'G' that is there exists an element e  ᗴ  G such that a  ᗴ   e = e  ᗴ  a = a  ∀ a  ᗴ G. (d) Existence of Inverse Element :  The inverse element of all the elements of 'G' exists that is for every a  ᗴ...
Read more

Symmetric key cryptography

Image
Symmetric key cryptography started thousand years ago, when people needed to exchange secrets (for example in a war ). We still mainly uses symmetric key cryptography in our network security. However, today ciphers are much more complex. Let us first discuss traditional algorithms, which were character oriented. Then we discuss modern one which are nit oriented. Traditional ciphers : We briefly introduce some traditional ciphers, which are character oriented. Although these are now obsolete, the goal is to show how modern cipher evolved from them. We can divide traditional symmetric key ciphers in to two broad categories namely -- substitution ciphers and traditional ciphers, as shown in the following figure. Substitution ciphers : A substitution cipher substitute one symbol with another. If the symbol in the plain text are alphabetic character, we replace one character by another. For example, we can replace character 'a' with character 'd' ,  and characte...
Read more