Custom Search

## Monday, 8 July 2013

### Modulo (Number Theory)

Hello my friend Share Mathematics: D
This time I will discuss what it modulo

little review
Modulo was used to calculate the remainder of the division
and can be applied to calculate the day before / after having regard to whether it is a leap year or not

sample case
if today Sunday the 25th of January 2015 then 19 years later 25 January fall day?

his manner
19 mod 4 = 3 (three as the rest of the division of 19 divided by 4)

why in mod 4? because leap falls every 4 years
nah +3 added later in the day (as that in question and the "later" if the "previous" live in less alone

then
19 mod 7 = 5 (five as the rest of the division of 19 divided by 7)
why in the mod 7? because in one week there are 7 days ==> nah here to determine the

then we add to previous results which then becomes 7 + 3 + 3 = 10

the earlier in the matter, 25 January 2015 fell Sunday
the 25 January in the year 2034 fall day .... ???

easy way, we obtain the result data is added
Sunday + 10 days = Wednesday

so 25 January 2034 year fell Wednesday

# Check for proof deh ^ _ ^: D

Cool right?

Let Cekidot ....: D
to listen to his theory

theory of Numbers
The theory of numbers (number theory) is fundamental in understanding the theory of cryptographic algorithms.
Numbers are intended are integers (integer).
modulo arithmetic
Modulo arithmetic (modular arithmethic) plays an important role in the integer computing, especially in cryptographic applications. Operators used in modulo arithmetic is mod. Mod operator, if used in the division of integers giving the rest of the division as the change. For example, 53 mod 5 results = 10 and the rest = 3. Then 53 mod 5 = 3.
Definition: Suppose is an integer and is an integer> 0 Operation mod gives remainder when divided.

Euclidean algorithm

Euclidean algorithm is an algorithm to find the GCD of two integers.
Euclid, the inventor of the Euclidean algorithm, was a Greek mathematician who wrote the algorithms in his famous book, Element.
Given two non-negative integers m and n (m ³ n). Euclidean algorithm follows seek the greatest common divisor of m and n.
relative Prima
Definition: Two integers are relatively prime and said if FPB / GCD (x, y) = 1
example:
7 and 11 are relatively prime because FPB / GCD (7,11) = 1 31 and 268 are relatively prime because FPB / GCD (31.268) = 1. 9 and 132 not relatively prime because FPB / GCD (9, 132) = 3 . If and are relatively prime, then it can be found integers and such that.
Example: Numbers 20 and 3 are relatively prime because gcd (20, 3) = 1, or can be written to and.

Feedback Modulo (modulo Inverse)

if a and m are relatively prime and m> 1, then we can find the inverse (inverse) of amodulo m. Reversal of a modulo m is an integer (a inverse) so sehinggaa (a inverse) congruent to 1 (mod m).

congruence Lanjar

-Kekongruenan Shaped tapering is congruent ยบ ax b (mod m) with madalah positive integers, a and b are arbitrary integers, and x is a variable integer.

-Value-Value x sought as follows: ax = b + miles that can be compiled into x = (b + km) / a and k is any integer. Assessed for k = 0, 1, 2, ... and k = -1, -2, ... which produces x as integer

THEOREM (Chinese Remainder Theorem) Let m1, m2, ..., mn are positive integers such that the United Nations (mi, mj) = 1 for i <> j. Then the system is congruent tapering x congruent ak (mod mk) has a unique solution modulo m = m1 × m2 × ... × mn.

Modulo Arithmetic and Cryptography

Use of Number Theory In Merkle-Hellman Cryptographic Systems (Knapsack) Merkle-Hellman Cryptographic an asymmetric key system, which means that the communication system requires two key is a public key and a private key. Already described in the foregoing discussion that algoritmasuperincreasing knapsack algorithm is weak, because chiperteks plainteksnya can be easily decrypted within tapering. While the algorithm nonsuperincreasing normal knapsack or knapsack is a difficult group knapsack algorithm (in terms of computation) because it requires exponential time in order to solve it. However, Martin Hellman and Ralph Merkle find a way to modify superincreasing knapsack into non-superincreasing knapsack using the public key (for encryption) and private key (for decryption). The public key is a sequence of non-superincreasing while the private key remains a superincreasing row. Modifications done using modulo arithmetic.

Modulo arithmetic suitable for cryptography because of two reasons:
1. Therefore, the values of modulo arithmetic is the finite set (0 to modulus m - 1), then we do not need to worry about the result of the calculation is outside the set.

2. Because we are working with integers, then we do not worry about losing information due to rounding (round off) as the real number operations.

Theorem 3. (The Fundamental Theorem of Arithmetic). Every positive integer greater than or equal to 2 n can be expressed as multiplication of one or more primes.

Theorem 4 (Fermat's Theorem). If p is a prime number and aadalah integer that is not divisible by p, namely the United Nations (a, p) = 1, then ap-1 congruent to 1 (mod p) Euler function f

F define the Euler function f (n) for n> = 1, which states the number of positive integers <n that are relatively prime to n

Theorem 5. If n = pq is a composite number with p and q prime, then f (n) = f (p) f (q) = (p - 1) (q - 1). Theorem 6. If p primes and k> 0, then f (pk) = pk - p k-1 = p k-1 (p - 1).

Knapsack algorithm

Knapsack algorithm is one of the public-key cryptographic algorithm that is useful for maintaining the confidentiality beam. Called public key cryptography (public-key cryptography) due to the encryption key is not secret and can be known by anyone (made public), while the key for decryption is known only to the recipient of the message (because it's a secret).

a. General Knapsak general form knapsack:
b. Knapsack Superincreasing superincreasing row is a sequence in which each value in the row is greater than the sum of all previous values. Example: is superincreasing row, but it is not.

The use of modulo arithmetic and Relative Prima at Knapsack

In the Merkle-Hellman cryptography, keys used consisted of public knapsack.Kunci is 'hard' knapsack, while the private key is 'easy' (superincreasing knapsack), which combined with two additional numbers, ie multiplier (multiplier) and modulus are used to transform superincreasing knapsack into the hard knapsack. The same numbers are used to change the number of subsets of the hard knapsack into a number of subsets of superincreasing knapsackyang can be solved in polynomial time order.