Cfrtjryk

I have this example code in which I have very big numbers as you see. 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 is this algorithm 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)

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)



    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 it becomes too slow to have results....