solve.py

from math import gcd, isqrt
from Crypto.Util.number import isPrime

# challenge 1: probably can use anything, but pollard-rho works
# edit: sagemath actually is usually faster with just factor()
n = 3078022440801373210337104721383788945269841345540381786461869466047167774292910507898271854415088423387441878003635925671242403990130707600286208825860598185366502783389401946255254009805550183195848597802674713816105514808690440034054131157345378931099830908251595958813150564857519044414566388971863597746025212116903383

x = 2
y = 2
d = 1
g = lambda x : (x * x + 1) % n

steps = 0
while d == 1:
    steps += 1
    x = g(x)
    y = g(g(y))
    d = gcd(abs(x - y), n)

print("took",steps,"steps")
print("factorization:")
print(d, n//d)


# challenge 2: fermat's factorization method
n = 12523075107893791979670086707623506471576547212425605718643256089034062921399670612867694943757055085178349600784468258775145279570350968588029532994484280605541161840043110768095556920359586801820737108058642407027816389045132065321568733220795809976422394948165878992741595084450271085800087160926998447040235530905682615573443593633635200340671667136194543093004548023552293122118621043983922325072588081963997257093699835276232119055313001936359282917797012144687265278587815357965203828734724403209938137378759948258101691362201357271541579478013729291487873561103240859749343463562093825705218044527322177571787
a = isqrt(n) + 1
steps = 0
while True:
    steps += 1
    b2 = a * a - n
    if isqrt(b2)**2 == b2:
        break
    a += 1

p = a - isqrt(b2)
q = a + isqrt(b2)
print("took",steps,"steps")
print("factorization:")
print(p, q)


# challenge 3: pollard's p-1 algorithm
n = 16775456867805984728872686858263669312523071985853423544832928914931466217497916500304025842334595069035893304826620713035067403632775326650638807721909986534273067175278036732714548718290260916614452578629041971960641973778516135495150910189458704151718760604252770859136939228039374420738485738280093347995422837742415700003539840808831343305209121350268278898733608200955655642536521306373413919713006708021680593130914807322718252140665334149540148154741946451629086971070985334632116582612652704935888565314234428659775099169962107057045209761211583044825424787313273960727038228937171903535958015936788395270469
cur = 2
for p in range(2, 10000):
    if not isPrime(p):
        continue
    for _ in range(20):
        cur = pow(cur, p, n)
p = gcd(cur - 1, n)
q = n // p
p, q = sorted([p, q])
print("factorization:")
print(p, q)