<jupyter_start><jupyter_text>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 integer3. 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)```<jupyter_code>from gmpy2 import mpz
import gmpy2<jupyter_output><empty_output><jupyter_text>SOLUTION FOR PROBLEM 1<jupyter_code>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<jupyter_output>N:  179769313486231590772930519078902473361797697894230657273430081157732675805505620686985379449212982959585501387537164015710139858647833778606925583497541085196591615128057575940752635007475935288710823649949940771895617054361149474865046711015101563940680527540071584560878577663743040086340742855278549092581
p:  13407807929942597099574024998205846127479365820592393377723561443721764030073662768891111614362326998675040546094339320838419523375986027530441562135724301
q:  13407807929942597099574024998205846127479365820592393377723561443721764030073778560980348930557750569660049234002192590823085163940025485114449475265364281
p*q:  179769313486231590772930519078902473361797697894230657273430081157732675805505620686985379449212982959585501387537164015710139858647833778606925583497541085196591615128057575940752635007475935288710823649949940771895617054361149474865046711015101563940680527540071584560878577663743040086340742855278549092581
N:  1797693134862315907729305190789024733617976978[...]<jupyter_text>SOLUTION FOR PROBLEM 2<jupyter_code>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)<jupyter_output>p: 25464796146996183438008816563973942229341454268524157846328581927885777969985222835143851073249573454107384461557193173304497244814071505790566593206419759
q: 25464796146996183438008816563973942229341454268524157846328581927885777970106398054491246526970814167632563509541784734741871379856682354747718346471375403
p: 25464796146996183438008816563973942229341454268524157846328581927885777969985222835143851073249573454107384461557193173304497244814071505790566593206419759
q: 25464796146996183438008816563973942229341454268524157846328581927885777970106398054491246526970814167632563509541784734741871379856682354747718346471375403<jupyter_text>SOLUTION FOR PROBLEM 3<jupyter_code>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)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.08336227856894755, 'fraction_numerical': 0.5043417853421327, 'mean_word_length': 5.321624588364434, 'pattern_counts': {'":': 0, '<': 26, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '459377', 'license': 'MIT', 'n_tokens_mistral': 4217, 'n_tokens_neox': 2509, 'n_words': 362, 'path': 'simple-exercises/basic-cryptography/6-factoring-challenge.ipynb', 'repo_name': 'mithi/algorithm-playground', 'size': '5758'}