Het RSA-geheimschrift (vernoemd naar de uitvinders van het algoritme: Rivest, Shamir en Adleman) is in principe onkraakbaar, omdat het in twee priemfactoren ontbinden van een zeer groot getal niet efficiënt te doen is. In de praktijk kunnen fouten in het protocol of snippertjes uitgelekte informatie de beveiliging echter om zeep helpen.

Gegeven is een publieke sleutel s van een RSA-geheimschrift, bijvoorbeeld:

8999819799059392865335436053795779676
4647560576999316234221807051424405359
9787269561367974534277303

Jouw taak bestaat erin de geheime sleutel te vinden, ofwel de twee priemfactoren van het getal $$s$$. Zonder extra informatie is dit een rekenklus voor een supercomputer. Door spionage is het verschil tussen beide priemfactoren echter uitgelekt. Voor bovenstaand voorbeeld werd achterhaald dat het verschil $$v$$ tussen beide priemfactoren van $$s$$ gelijk is aan:

2684778878098787967771714774760768222
33499207622

Laat je niet afschrikken: om de geheime sleutel te vinden is nu niet meer dan algebra van de middelbare school en enig praktisch getalinzicht nodig. Je moet wel gehele getallen die veel te groot zijn voor een rekenmachientje exact optellen en vermenigvuldigen. Gelukkig kan Python zonder problemen rekenen met grote gehele getallen, zonder daarbij aan nauwkeurigheid in te boeten.

Opgave

Schrijf een functie kraakRSA waarmee een RSA code kan gekraakt worden waarvan de sleutel $$s$$ en het verschil $$v$$ tussen de twee priemfactoren $$p_1$$ en $$p_2$$ van de sleutel $$s$$ gegeven zijn. De sleutel $$s$$ en het verschil $$v$$ moeten als argumenten aan de functie doorgegeven worden. Als resultaat moet de functie het tuple $$(p1, p2)$$ teruggeven met de twee priemfactoren van $$s$$, waarvoor geldt dat $$p_1 \leq p_2$$ en $$p_2 - p_1 = v$$.

Voorbeeld

>>> kraakRSA(221, 4)
(13, 17)
>>> kraakRSA(2183, 22)
(37, 59)