# OBLIVI - Editorial

Practise

Contest

Author, Tester, Editorialist: Vaibhav Gupta

## PROBLEM

Find a private key from an RSA public key.

## QUICK EXPLANATION

In breaking RSA mainly you need to factorize N which is of the form N = p*q. And finally use extended euclidean algorithm to find the private key.

## EXPLANATION

1. Congruence of squares

2. Continued fraction factorization

3. Dixon’s factorization method

4. Euler’s factorization method

5. Fermat’s factorization method

6. Pollard’s p-1 algo

7. Shank’s square forms factorization

8. Trial division

9. William’s p+1 algorithm

The Extended Euclidean Algorithm is essentially the Euclidean algorithm (for GCD’s) ran backwards. Your goal is to find d such that ed≡1(modφ(n)).

Recall the EED calculates x and y such that ax+by=gcd(a,b). Now let a=e, b=φ(n), and thus gcd(e,φ(n))=1 by definition (they need to be coprime for the inverse to exist). Then you have:

ex+φ(n)y=1

Take this modulo φ(n), and you get:

ex≡1(modφ(n))

And it’s easy to see that in this case, x=d. The value of y does not actually matter, since it will get eliminated modulo φ(n) regardless of its value. The EED will give you that value, but you can safely discard it.

## ACCEPTED SOLUTION:

cheaters_x’s Solution