When I tried to use this function to solve a CTF challenge, I found this problem.
from sage.all import *
from CryptoAttack.shared import rth_roots
c = 7267288183214469410349447052665186833632058119533973432573869246434984462336560480880459677870106195135869371300420762693116774837763418518542884912967719
e = 21
q = 9908484735485245740582755998843475068910570989512225739800304203500256711207262150930812622460031920899674919818007279858208368349928684334780223996774347
print(list(rth_roots(GF(q), c, e)))
all roots is 5107403174087968514895196615086317015893364083544151712088580833567342249591496357809721197485282001189625323559339471469178086856747368087781854865266446.
but when I made this change
def roots_of_unity(ring, l, r):
"""
Generates r-th roots of unity in a ring, with r | l.
:param ring: the ring, with order n
:param l: the Carmichael lambda of n
:param r: r
:return: a generator generating the roots of unity
"""
assert l % r == 0, "r should divide l"
x = ring(3)
while x ** l != 1:
x += 1
print(x)
g = x ** (l // r)
for i in range(r):
yield int(g ** i)
I replace the initial value of x with 3, I got the right solution
When I tried to use this function to solve a CTF challenge, I found this problem.
I got this output
all roots is
5107403174087968514895196615086317015893364083544151712088580833567342249591496357809721197485282001189625323559339471469178086856747368087781854865266446
.but when I made this change
I replace the initial value of x with 3, I got the right solution