The RSA code (named after the inventors of the algorithm: Rivest, Shamir and Adleman) essentially can't be cracked, because the integer factorization of large numbers can't be done efficiently. However, in actual practice, mistakes in the protocol or fragments of leaked information can tear the protection to pieces.
Given is a public key s of an RSA code, for example:
8999819799059392865335436053795779676 4647560576999316234221807051424405359 9787269561367974534277303
Your task is to find the secret key, in other words two integer factors of the number $$s$$. Without any extra information, this is a mathematical job for a super computer. However, through espionage, the difference between both integer factors has leaked. For the example above, the difference $$v$$ of the integer factors of $$s$$ equals:
2684778878098787967771714774760768222 33499207622
Do not be afraid: to find the secret key you will only need secondary school algebra and some practical insight in numbers. However, you must correctly add and multiply numbers that are far too large for a calculator. Luckily, Python has no difficulty calculating with large integers without losing accuracy.
Write a function crackRSA which can be used to crack an RSA code of which the key $$s$$ and the difference $$v$$ of two integer factors $$p_1$$ and $$p_2$$ of the key $$s$$ are given. The key $$s$$ and the difference $$v$$ should be passed to the function as arguments. As a result, the functions should return the tuple $$(p1, p2)$$ with both integer factors of $$s$$, to which applies that $$p_1 \leq p_2$$ en $$p_2 - p_1 = v$$.
>>> crackRSA(221, 4)
(13, 17)
>>> crackRSA(2183, 22)
(37, 59)