
# n = 22838960456421139208541144997446589236388152104301416644229227629463979063658890632209891439139888443259700039249459716854443727413442318448614788154483848660624621958689637653344984169796089902646052228536164396406557864762046692930673150406297782501442747669434467674752193772987427925523987516304671768036460639490362549001638710740311882014714898506488484077789234138400806779314957572243557386122954643660901208496696659630062897778560202517175743163041838540763904845685205648016360794823430818100775409536294724573825070302903069380915273907360597950163551619974290032737940420590599704559341054254599943188543
# e = 65537
# p = 136134883199125664402919304347145218160348405219117695475270368050419780117740420921873479736982994286078118114849450601432412648851586371377994711652066051282723804633308565405432072345021147854801822690634740270782164339963839172327446982860860009869931898979226690257553221155608620457253941390351540420608

n = 144577323082341606781087333127652195614928653924628840063283124688666697172079299540987986466905508888459466234427758008685453349603672093268364681219809070052759188387414913364503551677980960440032525534198537772481074574240349700392333150907937512241296276227852496435058553681077786863331924405426219248647
e = 23359771

p = 11043285040234897370108230348414076720909958796181348046213933603334639323065878778927432781023976397098528035583181448962487564184116786691066219045322752

beta = 0.5
epsilon = beta^2/7

pbits = p.nbits()
kbits = floor(n.nbits()*(beta^2-epsilon))
pbar = p & (2^pbits-2^kbits)
print("upper %d bits (of %d bits) is given" % (pbits-kbits, pbits))

PR.<x> = PolynomialRing(Zmod(n))
f = x + pbar
print(pbar)

x0 = f.small_roots(X=2^kbits, beta=0.3)[0]  # find root < 2^kbits with factor >= n^0.3

print(x0)
print(pbar)
print(x0 + pbar)
print(is_prime(x0 + pbar))