choose two large prime number p (prime 1) and q (prime 2) n = p x q , where n is called the modulus for encryption and decryption φ = ( p - 1) x ( q -1) is called Euler's totient function for n= pq For a given positive integer n, Euler's totient function ϕ(n) is defined as the number of positive integers less than or equal to n that are coprime (i.e., share no common factors) with n. ϕ( n ) = n ∏ p ∣ n ( 1 − 1 p ) \phi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right) p ∣ n means that p p divides n , and is a prime factor greater than 1 i n example , n=2*3=6 with factors f=1 , 2 , 3 , 4 , 5,6 factors Two numbers are coprime if their greatest common divisor (GCD) is 1 here find gcd(f,n)=1 only 1 and 5 are coprime with 6 φ =1*2 =2 choose e less than φ , such that e is co prime with φ , ie e has no common factor with φ except 1 mathematically : gcd ( e , φ ...
Comments
Post a Comment