Write down a polynomial time algorithm if a given integer $N$ can be expressed as $a^b$ for positive integers $a,b$ with $b \geq 2$. The running time of the algorithm should be $\operatorname{poly}(\log N)$.
(Obviously, you are expected to write this function without using some built-in test within Sage to check if an integer is a perfect power).
def is_perfect_power(N):
'''
Should return either False,
or a pair of integers (a,b) such that N = a^b with b > 1.
'''
pass
The RSA cryptosystem is a very popular system that is used in many practical applications and relies on the hardness of "factoring". For a brief description, two large prime numbers are picked at random and let number $N = pq$. Furthermore, an "exponent" $e$ is chosen so that $\gcd(e, (p-1)(q-1)) = 1$ (in most implementations, $e$ is either $3$ or $65537$, but in this problem we will set $e = 3$).
A message $m$ is thought of as an element of $\mathbb{Z}_N^\ast$, and the encryption of $m$ is simply $\operatorname{enc}(m) = m^e \bmod{N}$.
Thus anyone with the knowledge of just $N$ and $e$ can encrypt any message. However, without the factors of $N$ (assuming that factoring integers is a hard problem) turns out that computing $m$ from $\operatorname{enc}(m)$ (in general) is hard. This ensures that only a person who knows the factorisation of $N$ can recover the intended message $m$ from $c$. However, one needs to be careful in implementing this in practical scenarios.
If $m$ is too small (say $m \ll N^{1/12}$), then $m^3 \ll N$ and hence $c = m^3$ even without the mod. Computing cube-roots over integers is of course trivial and we can easily recover $m$ from $c$. So the standard approach is to ''pad'' $m$ into a larger string $m'$ so that $(m')^e$ definitely wraps around $N$ often. Some bad implementations of RSA might end up doing this padding in a predictable way such as $m \rightarrow m' = 1111\cdots 10m$ and compute $c = (m')^e \bmod{N}$ as the encryption. You have to show why this is a TERRIBLE idea by using the techniques of Qn 4 from Part A of this problem set.
Below is a bad implementation of RSA.
def generate_key(return_private_key = False):
e = 3 # This is the exponent we want
while(True):
p = Integer(randint(2**1000, 2**1024))
if p.is_prime() and gcd(e, p-1) == 1: break
while(True):
q = Integer(randint(2**1000, 2**1024))
if q.is_prime() and gcd(e, q-1) == 1: break
N = p*q
if return_private_key:
return (e, N, p, q)
else:
return (e, N)
def pow_mod(m, e, N):
if e == 0: return 1
if e == 1: return (m % N)
s = pow_mod(m, e//2, N)
if e % 2 == 0:
return (s * s) % N
else:
return (s * s * m) % N
def vanilla_RSA_encrypt(m, e, N):
if m > N or gcd(m, N) != 1: raise ValueError("Constraint on m and N failed")
return pow_mod(m, e, N)
def pad_message(m):
'''
Expects a message m with no more than 29 digits.
Returns a number m1 consisting of 546 digits:
pad_message(m) = 516 ones, followed by zeros, followed by m
'''
if len(str(m)) >= 30: raise ValueError(f"{m} is too long")
return int( ("1" * 516) + ("0" * 30) ) + m
def padded_RSA(m, e, N):
'''
Pads the message m using the above padding function, and then applies the RSA encryption on it.
'''
return vanilla_RSA_encrypt(pad_message(m), e, N)
Now let us generate the keys etc. and a random message of about 80 bits.
e, N = generate_key()
while(True):
m = randint(1,2**80)
if gcd(m,N) == 1: break
We are now going to encrypt $m$ using the padding function defined above, and here is a specific value instantiation.
N = 110475443751958845306143886778425046782064103827594367775863319218549890843522733269989775298217479906444000317035215078636093378717273996048245187798421883851380294073419729111369495264048695080185077090847662159692176535167781755002916746570980633467199208401881304433054573301204193892218625443357644182780864370482261764231452793082111167796158570848691855083795596935906526380372448058344499011116036053211663184196339908792442299765542660512666035653711488943865395007571216192543614770625472487157280530801016848604709366430428835362565508211618524261516798405718322699220933684453434088397251352568660906921
e = 3
padded_RSA(m, e, N) = 82528186845679773516278133812223459542051590946443386965114675192394954205835087606281228746865004910659048095916434637976266114221141192950941209811973168285106508732328185461902088564565973617087820188377641821780879543116140550343702867436024697924795945579221959323209622222933100302467314679930070319447957559778248129385358222914966689829516153845234163669840541699936595377894676078741532488692531671413133002809296514323084674612073788677508848513573282103259966814399768644808177705327121133462036182337983085063936664878130322957687127864567627148909721446268828983809423633290059319047693746979758768413(For this question, you can use the built in LLL() and factor() method. But you are NOT allowed to use the function small_roots(); you have to put in some effort to implement the method described in Part-A Qn4. :-) )
Sage has a built in function for factoring polynomials (over rationals, or over finite fields) and also for computing the LLL basis. Here are some examples.
R.<x> = PolynomialRing(QQ)
(x^9 - x).factor()
# LLL Example
M = Matrix(QQ, [vector([71, 64]), vector([10, 9])])
v = M.LLL()[0] # The first element of the LLL basis is the short-ish vector found
v