SEETF 2022 - To Infinity

to_infinity.sage

from tqdm import tqdm

p = 2**255 - 19
m = 314159265358979323846264338327950288419716939937510582097494459230781640628
cf = continued_fraction((m + 87 * p) / (1 + 63 * p))
s = "".join(["-" * x + "/" for x in cf])[:-1]


def calc(m, s):
    for x in s:
        if x == "-":
            m -= 1
        elif x == "+":
            m += 1
        elif x == "/":
            m = 1 / m
        else:
            raise Exception("Invalid")
    return m


assert calc(GF(p)(m), s) == 0

# find small x,y such that (x/y)=m (mod p)
# because the length of continued fraction tends to be smaller when x,y are smaller
y, x = matrix([[1, m], [0, p]]).LLL()[0]
assert (x / y) % p == m

cf = continued_fraction(x / y)
print(cf)
s = "".join(["-" * x + "/" for x in cf])[:-1]
assert calc(GF(p)(m), s) == 0
print(s)
print(len(s))

# but smallest x,y not necessary have shortest answer
# need some bruteforce
u, v = matrix([[1, m], [0, p]]).LLL()
mn = 10000
niter = 100000
for _ in tqdm(range(niter)):
    a = randint(1, 1000)
    b = randint(1, 1000)
    y, x = a * u + b * v
    assert (x / y) % p == m
    cf = continued_fraction(x / y)
    s = "".join(["-" * x + "/" for x in cf])[:-1]
    # print(len(s))
    if len(s) < mn:
        mna = a
        mnb = b
        mn = len(s)
        mncf = cf
        mns = s
print(mncf)
print(mn)
print(mns)
print(mna, mnb)

# author writeup: https://juliapoo.github.io/ctf/2022/06/11/seetf2022-author-writeup.html#to-infinity