Сила элементов в списке

Question

У меня есть этот пример кода:

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

Другим способом может быть применение apply map с лямбдой.

http://book.pythontips.com/en/latest/map_filter.html

a_to_power_e = list(map(lambda x : int(x)**e, a))

a_modulo_n = list(map(lambda x : int(x)%n, a_to_power_e))

, если вы хотите использовать одну и ту же функцию более одного раза,Вы можете сделать ниже.

cust_power_func = lambda x : int(x)**e
cust_modulo_func = lambda x : int(x)%n
a_to_power_e = list(map(cust_power_func, a))

a_modulo_n = list(map(cust_modulo_func, a_to_power_e))

Answer 2

Вы можете сначала создать список power, используя встроенную функцию pow или оператор **.См. Ниже для обеих реализаций:

In [1777]: n = 43787
      ...: e = 31
In [1778]: a
Out[1778]: ['1112', '2222', '3323', '4']

In [1781]: power = [pow(int(i),e) for i in a]

ИЛИ

In [1786]: power = [int(i) ** e for i in a]

Затем создайте еще один список modulo для каждого элемента выше созданного списка мощности:

In [1784]: modulo = [i%n for i in power]

In [1785]: modulo
Out[1785]: [19378L, 27732L, 26928L, 30208]

Создана еще одна функция для расчета power.Попробуйте и проверьте, увеличивается ли производительность при этом:

MOD = 1000000007
def fast_power(base, power):
    result = 1
    while power > 0:
        # If power is odd
        if power % 2 == 1:
            result = (result * base) % MOD

        # Divide the power by 2
        power = power / 2
        # Multiply base to itself
        base = (base * base) % MOD