Factoring with Partial Information of prime

known_p_lsb.sage

"Find P with only knowning 50% of LSB (least significant bit)"

def recover_msb(n, p, known_bits, debug=False) :
    beta = 0.5
    epsilon = beta^2/7
    PR.<x> = PolynomialRing(Zmod(n))
    f = x*(2^kbits) + p
    f = f.monic()
    x = f.small_roots(X=2^(pbits-kbits), beta=0.3)[0]  # find root < 2^kbits with factor >= n^0.3
    return x

if __name__ == "__main__":
    # # # Testing
    # p = random_prime(2^512-1,True,2^511)
    # q = random_prime(2^512-1,True,2^511)
    # n = p*q
    # pbits = p.nbits()
    # kbits = 300
    # partial_p = p & (2^kbits-1)
    # print(f"known p : {partial_p}, {len(bin(partial_p))}")
    # print("lower %d bits (of %d bits) is given" % (kbits, pbits))
    # print(partial_p)
    # x = recover_msb(n, partial_p, kbits)
    # print ((x[0]<<kbits) + partial_p == p)

    # Usage 
    n = 18956251888134383670674909797283145492190249682857271225648059300681610450289065780045478613072429552190902402525718186546315717975774990425764418938322284099579362288083375296029391431472749313291825595487319765433979186982123169833492153488330116822051049637787611093833723833807037901447291681599081947000225889107624683873130783724490622691098991240083278634929761657363219829108886688492233344209291279319686310683281777874252347492241301719331510113561921930755812220941512398122887069727083990278433675206585495594567268869617437008606953911213350117744062715016569545990477117567083508007016872543141956216961
    p = 134920249223843186411051701991286017125642135441890260669870225724135430894926738740720061309374473390691543142666967782191751108242483626968729402814204531528430146828148226100484527081942512839492433235634061013770154277297012655523458361685068156165902985872986695979283233974757891019142477491473106337793
    known_bits = 796
    partial_p = p & (2^known_bits-1)
    x = recover_msb(n, partial_p, known_bits)
    print(f"known: {partial_p}")
    print(f"Missing LSB: {x}")
    print(f"p = {(x<<kbits) + partial_p}")
    print(f"isPrime: {is_prime((x<<kbits) + partial_p)}")

known_p_msb.sage

"Find P with only knowning 50% of MSB (least significant bit)"

def recover_lsb(n, p, debug=False) :
    beta = 0.5
    epsilon = beta^2/7
    kbits = floor(n.nbits()*(beta^2-epsilon))
    PR.<x> = PolynomialRing(Zmod(n))
    f = x + p
    x0 = f.small_roots(X=2^kbits, beta=0.3)[0]  # find root < 2^kbits with factor >= n^0.3
    return x0

if __name__ == "__main__":
    # # Testing
    # p = random_prime(2^512-1,True,2^511)
    # q = random_prime(2^512-1,True,2^511)
    # n = p*q
    # pbits = p.nbits()
    # kbits = floor(n.nbits()*(beta^2-epsilon))
    # partial_p = p & (2^pbits-2^kbits)
    # print("upper %d bits (of %d bits) given" % (pbits-kbits, pbits))
    # x0 = recover_lsb(n, partial_p)

    # Usage 
    n = 144577323082341606781087333127652195614928653924628840063283124688666697172079299540987986466905508888459466234427758008685453349603672093268364681219809070052759188387414913364503551677980960440032525534198537772481074574240349700392333150907937512241296276227852496435058553681077786863331924405426219248647
    partial_p = 11043285040234897370108230348414076720909958796181348046213933603334639323065878778927432781023976397098528035583181448962487564184116786691066219045322752
    x0 = recover_lsb(n, partial_p)
    print(f"known: {partial_p}")
    print(f"Missing LSB: {x0}")
    print(f"p = {x0 + partial_p}")
    print(f"isPrime: {is_prime(x0 + partial_p)}")