Z_3 de Asal Sayılar

Teorem : p asal => p ≡ ± 1 ( mod 3)

İspat : Z_3 ün elemanları {0,1,2} olmak üzere, p asal ise, 3 e tam bölünemez haliyle ya 1 ya da 2 kalanını vereceğinden, asal sayıların Z_3 de alabileceği değer ± 1 dir.

A question of modulo

Example 2.1.9 Suppose we want to compute 432^678 (mod 987). The basic trick is to

start with a number and keep squaring:

432^2 = 186624 ≡ 81 432^4 ≡ 81^2 ≡ 639 432^8 ≡ 639^2 ≡ 690 ...432^512 ≡ 858

Since 678 = 512 + 128 + 32 + 4 + 2,

432 678 ≡ (81)(639) ...(858) ≡ 204

Calculations with exponents involve not-too-many multiplications. If the numbers have

several hundred digits, however, it is necessary to design special subroutines to do the

multiplications.

The idea behind fast exponentiation is that if the exponent is a power of 2 then we can

exponentiate by successively squaring:

x^8 =((x^2)^2)^2,

x^256 = (((((((x^2)^2)^2)^2)^2)^2)^2)^2.

If the exponent is not a power of 2, then we use its binary representation, which is just a

sum powers of 2:

x^291 = x^256 × x^32 × x^2 × x^1.

Thus to raise x to power n requires only about log n operations.

Theorem 2.1.12

Theorem 2.1.12 If gcd(n1,n2) = 1, then the pair of congruences x ≡ a (mod n1),

x≡ a (mod n2) has a unique solution x ≡ a (mod n1n2).

Definition 2.1.10 The multiplicative group of Zn is

Z*n = {a Є Zn|gcd(a, n)=1}.

In particular, if n is a prime, then Z*n = {a|1 ≤ a ≤ n - 1}.

Definition 2.1.11 The order of Z*n is defined to be the number of elements in Z*,namely |Z*n|.

2.1.3 Congruences

2.1.3 Congruences

Let n be a positive integer.

Definition 2.1.8 If a and b are integers, then a is said to be congruence to b modulo n,

written a ≡ b (mod n), if n devides (a - b). The integer n is called the modulus of the

congruence.

Theorem 2.1.10 (properties of congruences) For all a, a1,b,b1,c Є Z, the following are

true.

1. a ≡ b (mod n) if and only if a and b leave the same remainder when divided by n.

2. (reflexivity) a≡ a (mod n).

3. (symetry) If a ≡ b (mod n), then b ≡ a (mod n).

4. (transitivity) Ifa ≡ b (mod n), and b ≡ c (mod n), then a ≡ c (mod n).

5. If a ≡ a1 (mod n), and b ≡ b1 (mod n), then a + b ≡ a1 + b1 (mod n) and

ab ≡ a1b1 (mod n).

Definition 2.1.9 The integers modulo n, denoted Zn, is the set of (equivalence classes

of integers) {0, 1, 2,... ,n- 1}. Addition, subtraction, and multiplication in Zn are per-

formed modulo n.

Example 2.1.6 Z25 = {0, 1, 2,... ,24}.In Z25, 13 + 16 = 4, since 13 + 16 = 29=4(mod 25). Similarly, 13 · 16 = 8 in Z25.

2.1.2 Euclidean Algorithms 2

Theorem 2.1.7 If a and b are positive integers with a>b, then gcd(a, b)=gcd(b, a mod b).

The Euclidean algorithm consists of performing the following sequence of divisions Then

the greatest common divisor will be

gcd(a, b)=gcd(b, r1)=gcd(r2,r1)=···= gcd(rn, 0) = rn.

Hence, it follows that gcd(a, b)=rn.

Theorem 2.1.8 The above algorithm has a running time of O ((ln n)^2) bit operations.

The Euclidean algorithm can be extended so that it not only yields the greatest common

divisor d of two integers a and b, but also integers x and y satisfying ax + by = d.

Theorem 2.1.9 Extended Euclidean algorithm has running time of O((ln n)2) bits op-

erations.

Since the Euclidean algorithm computes the greatest common divisors, it can be used

to determine if a positive integer a modulo n. However it does not compute the value of the multiplicative inverse.