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

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)

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

• Not worth an answer yet but the pow builtins takes up to 3 arguments and actually perform what you are trying to achieve. Dec 4, 2018 at 17:52
• Welcome to Code Review! Please explain what you are calculating. Is this an algorithm like RSA? MathJax is available, if you need to type mathematical notation. Dec 4, 2018 at 17:57
• Yes, its part of code for RSA encrypting, this "n", "m", "d" and "e" are generated from another part of code. This "m" is converted text message. Dec 4, 2018 at 18:04

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.

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)

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))

• So I modified my code as you adviced me, but its still slow Dec 4, 2018 at 18:23
• @Brian Oh, I am surprised... Did you notice that the functions names are not exactly the one from your code ? Dec 4, 2018 at 18:24
• Yes, in a minute I modify my question to current form Dec 4, 2018 at 18:27
• Any other advices? My current code you can see in modified top question. Dec 4, 2018 at 18:49
• @Brian I've updated my answer to add more details Dec 5, 2018 at 8:39