Exercise 4¶

Exercise 4a¶

In [2]:
n = 69189629845368937640576720662244866511517654267613033786225538055857304509
In [3]:
# X is the upper bound on the value of the prime we are looking for
X = 2^(123-83)
In [4]:
# This is the value of p_t given in the exercise; for consistency with earlier exercises, we rename this to a.
a = 7975367974709495237422842361682067456
In [5]:
M_1 = matrix([
    [X^2, a*X, 0],
    [0, X, a],
    [0, 0, n]
])
B_1 = M_1.LLL()
In [6]:
Q_1 = B_1[0][0]*x^2/X^2 + B_1[0][1]*x/X + B_1[0][2]
Q_1.roots(ring=ZZ)
Out[6]:
[(101320256243, 1)]
In [7]:
p = a + Q_1.roots(ring=ZZ)[0][0]
p
Out[7]:
7975367974709495237422842463002323699
In [8]:
p.is_prime()
Out[8]:
True
In [9]:
p.divides(n)
Out[9]:
True
In [18]:
# We also should compute the remaining factor of n
q = n/p
q
Out[18]:
8675415361996408337581654026937922191
In [20]:
q.is_integer()
Out[20]:
True
In [22]:
q = Integer(q)
In [23]:
q.is_prime(), q.divides(n)
Out[23]:
(True, True)
In [24]:
p * q == n
Out[24]:
True

Exercise 4b¶

In [10]:
Mod(p, 2^40)
Out[10]:
101320256243

Exercise 4c¶

In [ ]:

Exercise 4d¶

In [ ]: