Let a
and b
be positive integers.
The extended Euclidean algorithm is an efficient way to find integers u,v
such thata * u + b * v = gcd(a,b)
Later, when we learn to decrypt RSA, 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 thatp * u + q * 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.
You are now level Current level