18-08-2014, 10:58 AM
RSA Theory The problem Given N=pq where p and q are distinct primes ia[Eqn1] gcd(e,|O(n)=1 ia[Eqn2] c=me mod n, o i0 m
RSA Theory
The problem
Given
N=pq where p and q are distinct primes ia[Eqn1]
gcd(e,|O(n)=1 ia[Eqn2]
c=me mod n, o i0 m<n ia[Eqn3]
ed i0 1 (mod | O (n) ia[Eqn4]
Prove that
m = cd mod o, 10 m < n
Basic number theory
We will use these principles of number theory in our proof below
A prime number is defined as an integer, greater than one .Which only has positive integer divisors (factors) of the number one and itself. Two numbers a and b which have no common factors other than one are said to be coprime or relatively prime.