from sage.misc.prandom import randrange, randint

print '='*16
print 'LEVEL 1'
print '='*16

p = 1019
q = 509
print 'p', p
print '='*16


d = randrange(3, 9)
d = 5

# m is an integer
m = int(float(p)**(1/(d)))

m= 44

kk = 2323

mat = identity_matrix(ZZ, d+1)
mat2 = mat.insert_row(0, [pow(m, i)*kk for i in range(d+1)]).transpose()

print mat2
print '='*16

mat3 = mat2.insert_row(d+1, [p*kk]+[0]*(d+1))
print mat3
print '='*16

L3 = mat3.LLL()

print L3
print '='*16

rows_L3 = L3.rows()
rows_L3 = rows_L3[:-1]

rows_L3= filter(lambda x: abs(x[d+1]) == 1, rows_L3)

polys= [ZZ['x'](list(x)[1:]) for x in rows_L3]

#print L3.rows()

x = PolynomialRing(IntegerRing(), 'x').gen()

# f(m), g(m) are 0 mod p
# g(x) = x - m
# f is monic, small coeffs in Z, irreducable
# f has no root in Q


g = (x - m)

print 'm', m
print 'degree', d
print '='*16

polys = filter(lambda x: x.is_irreducible(), polys)
#print 'polys', polys

for pol in polys:
    f = pol
    print 'f(m) mod p', f(m) % p
    print 'f(x)', f
    print '='*16

print 'g(x)', g

print '='*16

f = polys[1]

print '='*16
print 'LEVEL 2: find a & b'
print '='*16

def check_smooth(n, B):
    listz = list(factor(n))
    for x in listz:
        if x[0]>B:
            return False

    return True

c = 2022

print 'c', c

a_ = None
b_ = None

B = 9
m = m # Level 1

def rarb(c, B, B_, m, d):
    for ra in xrange(-c, c+1):
        for rb in xrange(1, c+1):
            zx = abs(ra-rb*m)
            if check_smooth(int(zx), B): # m from Level 1
                norm = f(ra/rb) * power(rb,d)
                if check_smooth(norm, B_):
                    return ra, rb

    return None, None # should not happen :x

a_, b_ = rarb(c, B, B, m, d)
print 'a', a_
print 'b', b_

print '='*16