Skip to main content

Public Key Mathematics

Modular Inversion​

  • In rings and prime fields, multiplicative inverse might exist
  • Exists when gcd(a,p)=1gcd(a,p)=1
  • For prime fields, gcd(a,p)=,∀a≠0∈GF(p)gcd(a,p)=, \forall a \ne 0 \in GF(p)

Euclidean Algorithm​

  • Calculates the greatest common divisor of two numbers
  • This is the largest number that divides both r0r_0 and r1r_1

Bézouts Identity​

  • Bézouts identity tells us that the greatest common divisor of two numbers can be expressed as the sum of multiples of these numbers

Extended EA​

  • Calculates gcd(r0,r1)gcd(r_0,r_1) as normal, and in addition calculates values of s and t
  • r2=?×r0+?×r1r_2 = ? \times r_0 + ? \times r_1
  • Check slides for formula