Skip to content

Latest commit

 

History

History
51 lines (31 loc) · 2.69 KB

week8_2020101058_lecture_2 .md

File metadata and controls

51 lines (31 loc) · 2.69 KB
Raw

This is a correction docuement, due to a week of holiday from 2nd to 6 oct the numbering of notes was decremented by 1,

i.e week 8 was denoted as week 7, Sorry for the inconvenience, this will not happen again.

Euclid's GCD Algorithm

  • The Euclidean algorithm is an efficient method for computing the greatest common divisor of two integers, without explicitly factoring the two integers.

  • It is used in countless applications, including computing the explicit expression in Bezout's identity, constructing continued fractions, reduction of fractions to their simple forms, and attacking the RSA cryptosystem. Furthermore, it can be extended to other rings that have a division algorithm, such as the ring Q[x] of polynomials with rational coefficients.

The Euclidean algorithm is basically a continual repetition of the division algorithm for integers. The point is to repeatedly divide the divisor by the remainder until the remainder is 0. The GCD is the last non-zero remainder in this algorithm.

long long int gcd(long long int a,long long int b)
{
    if(b==0)return a;
    else return gcd(b, a % b);
}
  • The worst case for this will come when the two numbers will be fibonacci numbers

Extended euclid's algorithm. (Modular division)

The extended Euclidean algorithm is an algorithm to compute integers x and y such that

ax+by=gcd(a,b)

  • given a and b.

  • The existence of such integers is guaranteed by Bézout's lemma.

  • The extended Euclidean algorithm can be viewed as the reciprocal of modular exponentiation.

  • By reversing the steps in the Euclidean algorithm, it is possible to find these integers x and y. The whole idea is to start with the GCD and recursively work our way backwards. This can be done by treating the numbers as variables until we end up with an expression that is a linear combination of our initial numbers.

chinese remainder theorem

  • The Chinese remainder theorem is a theorem which gives a unique solution to simultaneous linear congruences with coprime moduli. In its basic form, the Chinese remainder theorem will determine a number ppp that, when divided by some given divisors, leaves given remainders

RSA

  • RSA is an encryption algorithm, used to securely transmit messages over the internet. It is based on the principle that it is easy to multiply large numbers, but factoring large numbers is very difficult

  • Public key cryptography

  • Fermat's little algorithm

    • Fermat’s little theorem states that if p is a prime number, then for any integer a, the number a^p – a is an integer multiple of p.

Pardon for not following the readme file format and syntax, I was not aware of that up until now, But I will correct it.