Почему работа со списком медленнее, чем работа с пустым массивом

Question

Я делаю проект по шифрованию данных с использованием алгоритма RSA, и для этого я взял файл .wav в качестве ввода и прочитал его, используя wavfile, и я могу применить ключ (3, 25777), но когдаЯ применяю ключ дешифрования (16971,25777), он выдает неправильный вывод, например:

Вывод, который я получаю:

                    [[     0 -25777]
                    [     0 -25777]
                    [     0 -25777]
                    ...
                    [-25777 -25777]
                    [-15837 -15837]
                    [ -8621      1]]

вывод, который я хочу:

                    [[ 0 -1]
                    [ 2 -1]
                    [ 2 -3]
                    ...
                    [-9 -5]
                    [-2 -2]
                    [-4  1]]

Это происходило только с частью расшифровки массива, поэтому я решил преобразовать 2d массив в 2d список.После этого он дает мне желаемый результат, но требует много времени, чтобы применить ключи ко всем элементам списка (16 минут, в случае массива это было 2 секунды).Я не понимаю, почему это происходит и есть ли другое решение этой проблемы?

Вот часть шифрования и дешифрования программы:

    #encryption
    for i in range(0, tup[0]): #tup[0] is the no of rows
        for j in range(0, tup[1]): #tup[1] is the no of cols
            x = data[i][j] 
            x = ((pow(x,3)) % 25777) #applying the keys
            data[i][j] = x #storing back the updated value

    #decryption
    data= data.tolist() #2d array to list of lists 
    for i1 in (range(len(data)):
        for j1 in (range(len(data[i1]))):
            x1 = data[i1][j1] 
            x1 = (pow(x1, 16971)%25777) #applying the keys
            data[i1][j1] = x1 

Ждем предложений.Спасибо.

Answer 1

Появление чего-то вроде pow(x1, 16971) должно дать вам паузу. Это почти для любого целого числа x1 даст результат, который 64-разрядный тип int не может содержать. Именно поэтому numpy дает неверный результат, потому что numpy использует 64-битные или 32-битные целые числа на самых распространенных платформах. Это также причина, по которой простой питон медленный, потому что он может обрабатывать большие целые числа, но это дорого.

Способ обойти это - применить модуль между умножениями, чтобы числа оставались небольшими и легко обрабатывались с помощью 64-битной арифметики.

Вот простая реализация:

def powmod(b, e, m):
    b2 = b                         
    res = 1                        
    while e:                       
        if e & 1:                  
            res = (res * b2) % m   
        b2 = (b2*b2) % m        
        e >>= 1                 
    return res

Например:

>>> powmod(2000, 16971, 25777)
10087
>>> (2000**16971)%25777
10087
>>> timeit(lambda: powmod(2000, 16971, 25777), number=100)
0.00031936285085976124
>>> timeit(lambda: (2000**16971)%25777, number=100)
0.255017823074013