<-- Prev

Modular Arithmetic

Next -->
  • Extended GCD
    20 pts · 15664 Solves · 68 Solutions

    Let $a$ and $b$ be positive integers.

    The extended Euclidean algorithm is an efficient way to find integers $u,v$ such that

    $a \cdot u + b \cdot v = \gcd(a,b)$

    Later, when we learn to decrypt RSA ciphertexts, we will need this algorithm to calculate the modular inverse of the public exponent.

    Using the two primes $p = 26513, q = 32321$, find the integers $u,v$ such that

    $p \cdot u + q \cdot v = \gcd(p,q)$

    Enter whichever of $u$ and $v$ is the lower number as the flag.

    Knowing that $p,q$ are prime, what would you expect $\gcd(p,q)$ to be? For more details on the extended Euclidean algorithm, check out this page.

    You must be logged in to submit your flag.

Level Up

level up icon

You are now level Current level