# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# # Factoring challenge
#
# ## Problem 1
# - Given `N` which is a product of two primes `p` and `q` such that 
# ```
# | p - q | < 2 * fourth_root_of(N)
# ```
# - Find `p` and `q` 
#
# ```
# 179769313486231590772930519078902473361797697894230657273430081157732675805505620686985379449212982959585501387537164015710139858647833778606925583497541085196591615128057575940752635007475935288710823649949940771895617054361149474865046711015101563940680527540071584560878577663743040086340742855278549092581
# ```
#
# - Hint: show that: 
#
# ```
# given:
# A =  (p + q) / 2 
# N = p * q
# | p - q | < 2 * fourth_root_of(N)
#
#
# Then:
# 1. A >= sqrt(N)
# 2. A is an integer
# 3. A = Ceiling(sqrt(N))
# 4. There exists an x such that 
#      p = A - x
#      q = A + x
#      which is x = sqrt(A^2 - N)
# ```
#
# ## Problem 2
# - Given `N`  which is a product of two primes `p` and `q` such that
# ```
# | p - q | < 2 ^ 11 * fourth_root_of(N)
# ```
# - Find `p` and `q` 
# - Hint: show that
# ```
# sqrt(N) <= A <= sqrt(N) + 2^20
# ```
#
# ## Problem 3
# - Given `N`  which is a product of two primes `p` and `q` such that
# ```
# | 3p - 2q | <  fourth_root_of(N)
# ```
# - Find `p` and `q` 
# - Hint: show that
# ```
# sqrt(6N) <= (3p + 2q) / 2 <= sqrt(6N + sqrt(N)/4)
# ```

from gmpy2 import mpz
import gmpy2


# # SOLUTION FOR PROBLEM 1

# +
def get_ceiling_sqrt(N):
    i, r = gmpy2.isqrt_rem(N) 
    if r > 0:
        return i + 1 
    else:
        return i
    
def find_pq(A, N):
    A_squared_minus_N = A**2 - N
    x = gmpy2.isqrt(A_squared_minus_N)
    p = A - x
    q = A + x
    return p, q


# +
N_string = '179769313486231590772930519078902473361797697894230657273430081157732675805505620686985379449212982959585501387537164015710139858647833778606925583497541085196591615128057575940752635007475935288710823649949940771895617054361149474865046711015101563940680527540071584560878577663743040086340742855278549092581'

N = mpz(N_string)
A = get_ceiling_sqrt(N)

p, q = find_pq(A, N)

N_from_pq = gmpy2.mul(p, q)

print("N: ", N)
print("p: ", p)
print("q: ", q)
print("p*q: ", N_from_pq)

assert N == N_from_pq


# -

# # SOLUTION FOR PROBLEM 2

def find_pq(N):
    start = gmpy2.isqrt(N) + 1
    end = start + mpz(2)**mpz(20)
    
    for A in range(start, end):
        A_squared_minus_N = A**2 - N
        x, r = gmpy2.isqrt_rem(A_squared_minus_N)
        if r == 0:
            p = A - x
            q = A + x
            if N == gmpy2.mul(p, q):
                return p, q
    return None, None


# +
N_string = '648455842808071669662824265346772278726343720706976263060439070378797308618081116462714015276061417569195587321840254520655424906719892428844841839353281972988531310511738648965962582821502504990264452100885281673303711142296421027840289307657458645233683357077834689715838646088239640236866252211790085787877'

N = mpz(N_string)
p, q = find_pq(N)

print("p:", p)
print("q:", q)


# -

# # SOLUTION FOR PROBLEM 3

def find_pq(N):
    sixN = 6 * N
    start = gmpy2.isqrt(sixN)
    sqrtNdiv4, _ = gmpy2.f_divmod(gmpy2.isqrt(N), 4)
    end = start + sqrtNdiv4
    
    for A in range(start, end):
        z = gmpy2.mul(A, A) - sixN
        if z < 0: continue
        i, r = gmpy2.isqrt_rem(z)
        if r != 0: continue
            
        # try 3p < 2q
        p, r = gmpy2.f_divmod(A - i, 3)
        if r != 0: continue
        q, r = gmpy2.divmod(A + i, 2)
        if r != 0: continue
        if gmpy2.mul(p, q) == N:
            return p, q
        
        # try 2q < 3p
        p, r = gmpy2.f_divmod(A + i, 3)
        if r != 0: continue
        q, r = gmpy2.f_divmod(A - i, 2)
        if r != 0: continue
        if gmpy2.mul(p, q) == N:
            return p, q
    
    return None, None


# +
N_string = '720062263747350425279564435525583738338084451473999841826653057981916355690188337790423408664187663938485175264994017897083524079135686877441155132015188279331812309091996246361896836573643119174094961348524639707885238799396839230364676670221627018353299443241192173812729276147530748597302192751375739387929'
N = mpz(N_string)

p, q = find_pq(N)

print("p:", p)
print("q:", q)
# -



StarcoderdataJupyterScriptsDedupFiltered