Count power of big numbers and then apply modulo on this numbers

Question

I have this example code in which I have very big numbers as you see. The problem is that when I use this algorithm for some small numbers, it works well, but when I use it for big numbers like in this example, this algorithm is so slow.

Can you tell me why this algorithm is so slow for that big numbers? How can I make it faster?

n = 11698030645065745910098695770921
e = 9569991810443215702618212520777
d = 7874909554574080825236064017913
m = 104228568138
m = int(m)
e = int(e)
n = int(n)
def preparation(m, n):
    block_lenght= len(str(n)) - 1
    m = [str(m)[i:i+block_lenght] for i in range(0, len(str(m)), block_lenght)]
    return m

def encrypt(m, n, e):
    m = preparation(m, n)

    power = [int(i) ** e for i in m]

    modulo = [i%n for i in power]

    total_sum = sum(modulo)

    return total_sum

m = encrypt(m, n, e)
print("m = ", m)

Answer 1

Your spelling of length is unconventional, and will cause errors.

Calculating the full result will generate a large number, slowing computation. It's better to reduce the partial results as you compute the power, and keep the partial result mod n - you'll probably want to use binary exponentiation instead of the ** operator so that you can apply the modulus to the intermediate results.

I don't see what m = int(m) and similar lines are intended to achieve - probably worth a comment there.

How is the final (partial) block handled? That seems to be missing altogether.

Answer 2

Avoid the amount of duplicated/useless operations

The function int is called on integers which is useless.

The str function is called many times on the same inputs which can be avoided with temporary variables.

You iterate (indirectly) 3 times over the result of preparation2, this could be done with a single operation.

At this stage, you can write something like:

def preparation2(m, n):
    n_str = str(n)
    m_str = str(m)
    block_len = len(n_str) - 1
    return [m_str[i:i+block_len] for i in range(0, len(m_str), block_len)]

def encrypt2(m, n, e):
    return sum((int(i)**e) % n for i in preparation2(m, n))

Builtin

The pow builtins takes up to 3 arguments and actually perform what you are trying to achieve in a much more efficient way.

def encrypt2(m, n, e):
    return sum(pow(int(i), e, n) for i in preparation2(m, n))

Final code and benchmark

I wrote the following code to test the original code and the improved code and ensuring that the behavior is not broken on inputs of increasing sizes:

def preparation(m, n):
    block_lenght= len(str(n)) - 1
    m = [str(m)[i:i+block_lenght] for i in range(0, len(str(m)), block_lenght)]
    return m

def encrypt(m, n, e):
    m = preparation(m, n)

    power = [int(i) ** e for i in m]

    modulo = [i%n for i in power]

    total_sum = sum(modulo)

    return total_sum


def preparation2(m, n):
    n_str = str(n)
    m_str = str(m)
    block_len = len(n_str) - 1
    return [m_str[i:i+block_len] for i in range(0, len(m_str), block_len)]

def encrypt2(m, n, e):
    return sum(pow(int(i), e, n) for i in preparation2(m, n))


import time

TEST_CASES = [
    (116, 956, 787, 10),
    (1169, 9569, 7874, 10),
    (116980, 956999, 787490, 104),
    (1169803, 956999, 787490, 104),
    (11698030, 9569991, 7874909, 1042),
    (11698030645, 95699918104, 787490955457, 10422),
    (116980306450657459, 956999181044321570, 787490955457408082, 104228568),
    (11698030645065745910098695770921, 9569991810443215702618212520777, 7874909554574080825236064017913, 104228568138),
]
SEP = "      "
print("Comparison", SEP, "Original solution", SEP, "Improved solution")
for (n, e, d, m) in TEST_CASES:
    start = time.perf_counter()
    out = encrypt(m, n, e)
    time_sol1 = time.perf_counter() - start

    start = time.perf_counter()
    out2 = encrypt2(m, n, e)
    time_sol2 = time.perf_counter() - start
    if out != out2:
        print("Different outputs", SEP, out, SEP, out2)
        break
    else:
        print("Times", SEP, time_sol1, SEP, time_sol2)

And the results:

Comparison        Original solution        Improved solution
Times        4.408881068229675e-05        2.5639310479164124e-05
Times        0.00031274929642677307        1.0897871106863022e-05
Times        0.587213734164834        2.9506627470254898e-05
Times        0.5985749792307615        2.992432564496994e-05
Times        62.84936385508627        3.45488078892231e-05

Then the original code becomes too slow to have results while the improved code still runs instantly....

Making things clearer

In could be an idea to make the behavior of preparation clearer, with a better name and with a clearer signature:

• as we do not really need n but just its length, we could provide directly the required block_len

• we could provide the stringified version of m directly.

You get something like:

def split_str_in_blocks(s, block_len):
    return [s[i:i+block_len] for i in range(0, len(s), block_len)]

def encrypt2(m, n, e):
    block_len = len(str(n)) - 1
    return sum(pow(int(b), e, n) for b in split_str_in_blocks(str(m), block_len))