I have this exercise:
Exercice 9 : ( Common RSA primes ) Alice and Bob have generated a set of RSA modules together. Your goel is to find the prime numbers p and q they used to generate these modules, available in the files pk_alice and pk_bob. there is the pka_alice:
93145558017597242451057840020003423492065036505715635939073421584870064178836557007438920905568366141278155363295217244442270120551665563816731464612225841456174904661719015967457696683736586858513914335501922092345895701281682242489324726462415020945038049322877151602626496388802926568113827098181488546541
pka_bob: 130627775975870619265103967461863569685393719623259606834494161761353696231137838485596006850409649916631767658717771142397327842476766835551088514711108732237134464583834085414090472465465656901718533120526240047672780456483182231171430047581628792398849389571220237028177673312592572286345009761324975840273
I tried this python program but it takes forever (never get an output from it):
import sympy
def factorize(n):
factors = sympy.ntheory.factorint(n)
# Les clés du dictionnaire factors contiennent les facteurs premiers et les valeurs correspondent à leurs exposants.
# Si n est le produit de deux nombres premiers, il y aura deux clés avec des exposants de 1.
prime_factors = [factor for factor in factors if factors[factor] == 1]
if len(prime_factors) == 2:
p, q = prime_factors
return p, q
else:
return None, None # La factorisation a échoué
# Remplacez n par la valeur de n que vous souhaitez factoriser
n = 130627775975870619265103967461863569685393719623259606834494161761353696231137838485596006850409649916631767658717771142397327842476766835551088514711108732237134464583834085414090472465465656901718533120526240047672780456483182231171430047581628792398849389571220237028177673312592572286345009761324975840273
p, q = factorize(n)
if p and q:
print(f"Les facteurs premiers de {n} sont {p} et {q}")
else:
print("La factorisation a échoué.")
How can I solve this?
Alice:
p = 11546228166566908996944683360898685003804727870211092212733704895162284555816549530587425586574198315100684457091938790507073108514058962518074083478643487
q = 8067184943331379055883676674511286075021098911943040287647388643355051515709741724813022793998233351188112736071886443985753058022434276985771666457801843
Bob:
p = 11546228166566908996944683360898685003804727870211092212733704895162284555816549530587425586574198315100684457091938790507073108514058962518074083478643487
q = 11313458740934508371320688917048544848372493637810071784612124974863165934304508093282020336767731785955272382720056869761911762809833915572489801623030479
The hint is in the exercise title: "Common RSA primes".
import math
a = 93145558017597242451057840020003423492065036505715635939073421584870064178836557007438920905568366141278155363295217244442270120551665563816731464612225841456174904661719015967457696683736586858513914335501922092345895701281682242489324726462415020945038049322877151602626496388802926568113827098181488546541
b = 130627775975870619265103967461863569685393719623259606834494161761353696231137838485596006850409649916631767658717771142397327842476766835551088514711108732237134464583834085414090472465465656901718533120526240047672780456483182231171430047581628792398849389571220237028177673312592572286345009761324975840273
g = math.gcd(a, b)
print(f'Alice:\np = {g}\nq = {a//g}\n')
print(f'Bob:\np = {g}\nq = {b//g}')