能否以优于O(N²)的时间复杂度逆转bytes-自然数双射算法？

我实现了一个将bytes映射为自然数的双射算法rank：

def rank(s: bytes) -> int:
    k = 2**8
    result = 0
    offset = 0
    for i, w in enumerate(s):
        result *= k
        result += w
        offset += (k**i)
    return result + offset

目前对应的逆转算法unrank实现如下：

def unrank(value: int) -> bytes:
    k = 2**8
    # 1. 获取长度
    import itertools
    offset = 0
    for length in itertools.count():  #! 循环执行*O(N)*次 !#
        offset += (k**length)  #! 大整数加法是*O(N)*复杂度 !#
        if offset > value:
            value = value - (offset - k**length)
            break
    # 2. 解析字节内容
    result = bytearray(length)
    for i in reversed(range(length)):
        value, result[i] = divmod(value, k)  # 可以用位运算实现，此处忽略复杂度影响
    return bytes(result)

令N≈字节长度≈整数的对数，该逆转算法的最坏时间复杂度为O(N²)。虽然在≤32KiB数据等实用场景下运行良好，但我想知道是否能从根本上优化为时间复杂度更低的实现。

测试用例 #

# 示例/测试用例：

assert rank(b"\"") == 0
assert rank(b"\x00") == 1
assert rank(b"\x01") == 2
...
assert rank(b"\xFF") == 256
assert rank(b"\x00\x00") == 257
assert rank(b"\x00\x01") == 258
...
assert rank(b"\xFF\xFF") == 65792
assert rank(b"\x00\x00\x00") == 65793

assert unrank(0) == b"\"
assert unrank(1) == b"\x00"
assert unrank(2) == b"\x01"
# ...
assert unrank(256) == b"\xFF"
assert unrank(257) == b"\x00\x00"
assert unrank(258) == b"\x00\x01"
# ...
assert unrank(65792) == b"\xFF\xFF"
assert unrank(65793) == b"\x00\x00\x00"

assert unrank(2**48+1) == b"\xFE\xFE\xFE\xFE\xFF\x00"

内容的提问来源于stack exchange，提问作者JamesTheAwesomeDude