Basic Number Theory

1. Euclid's Lemma

   1. According to Euclid's lemma , given two integers a & b , such that a >= b >= 0, then we can say that

   2. According to euclid's lemma , for given 2 positive integers x and y , gcd(x,y) = gcd(y,x%y), where % is the mod operation.

   3. proof of correctness: The given hypothesis can easily be proven by the use of induction hypothesis. a = (q_0)*(b) + r_0

      b = (q_1)*(r_0) + r1

      r_0 =( q_2)*(r_1) + r_2

      ...

      ...

      ...

      r_k-1 = (q_k+1)*(r_k) + 0

   4. Since remainder can be negative it'll surely reach 0 at some moment ( at r_k = 1 for sure ) , so the chain will have an end thus, if we go above the equations from the below , we could see that G.C.D of the numbers will be r_k , as if we go backward substituting the remainders , we observe that r_k divides both a & b and is therefore a factor of them both.

   5. why is it the greatest : we could see this from the fact that ,

      • r_k-2 = (q_k)*(r_k-1) + r_k ,if we say that ther's gcd of r_k-1 and r_k-2 c , this clearly implies the fact that c <= r_k or else r_k-2 wont be divisible by c. and also we've gcd(r_k-1,r_k) = r_k , and since c is the gcd of one step above c <= r_k maximum value c can have is r_k therefore it is the gcd of a & b.

      • if we assume a >= b >= 0 ( for no loss of generality , in other cases a & b could be simply swapped to get their gcd )

        gcd_function(a,b){
        	if(b==0)
        		return a;
        	return gcd_function(b,a%b);
        }
        

• Extended Euclid's Algorithm

  • Theorem : if d divides both integers a & b such that d = ax + by , where x & y are integers then , d is gcd of a, b

    • now , that d is a divisor of both a & b , then d <= gcd(a,b) , by definition of gcd . Also d = ax + by , and as gcd(a,b) divides both a & b then d >= gcd(a,b) , therefore this implies d = gcd(a,b).

  • Pseduo-code :

    • Given two integers a & b , return integer x & y & d such that d = ax + by is the gcd of a & b .

    extended_euclid(int a , int b){
    
        if( b== 0)
            return (1,0,a);
    
        (x',y',d') = extended_euclid(b,a%b);
    
        return (y',x' - (a/b)*(y'), d')
    }
    
    

RSA Encryption

• The RSA algorithm is an asymmetric cryptography algorithm; this means that it uses a public key and a private key (i.e two different, mathematically linked keys). As their names suggest, a public key is shared publicly, while a private key is secret and must not be shared with anyone.

Algorithm

The main steps of the RSA encryption could be stated as :

1. Generating the Keys : we choose 2 large prime numbers p1 and p2 , so that factorising their product will be a herculean task.

   1. Calculate their product x = p1 * p2.
   2. Calculate the toitent function defined as ϕ(n)=(p1−1)(p2−1)
   3. next we choose an integer e , such that e is **co-prime i.e gcd(e,**ϕ(n)) = 1 to the toitent product , calculated in the previous step. The pair (n,e) makes up the public key.
   4. Calculate an integer d such that , e*d = 1 mod ϕ(n) , for finding d we use the extended eucledian algorithm , the generated key d , becomes the decryption key.
   5. Thus we have generated 2 sets of keys ,
      1. Public Key : { e , n }
      2. Private Key : { d , n }

2. Encryption

   For any given plain text p , to generate the cipher text c , we do the following operation

   c = pow(p , e) mod n.

3. Decryption

   For any given cipher text c , to generate the plain text p , we do the following operation

   p = pow(c , d) mod n.

   crypto-mania-/rsa at main · KarmanjyotSingh/crypto-mania-