資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python - 數論變換
數論變換 (NTT) 是數論領域許多計算應用中的一個關鍵組成部分。它在加密、訊號處理、糾錯碼等領域至關重要，因為它可以有效地進行大數乘法和卷積運算。NTT 是一種快速計算多項式乘法模素數整數的方法，與快速傅立葉變換 (FFT) 密切相關。
在本文中，我們將探討兩種在 Python 中實現數論變換的不同方法。我們將深入研究 Cooley-Tukey 演算法，這是將快速傅立葉變換付諸實踐的最流行方法之一。Cooley-Tukey 演算法應用分治策略，將一個大問題分解成較小的子問題，並將解決方案組合起來，從而得到最終的轉換輸出。
透過概述它們的演算法、程式碼示例和輸出示例，我們希望提供對這兩種方法的理解。在本文結束時，讀者將擁有堅實的基礎，能夠有效地實現數論變換並將其功能應用於他們的計算任務。
方法
為了在 Python 中執行數論變換，我們可以遵循以下兩種方法：
使用複數的 Cooley-Tukey 演算法。
使用整數的 Cooley-Tukey 演算法。
讓我們深入瞭解這兩種方法：
方法 1：使用複數的 Cooley-Tukey 演算法
Cooley-Tukey 演算法是一種眾所周知的方法，它利用快速傅立葉變換 (FFT) 方法快速計算離散傅立葉變換 (DFT)。該演算法可以被改編為執行 NTT。
演算法
在 Python 中執行數論變換的演算法如下：
步驟 1 - 匯入 cmath 模組。
步驟 2 - 構建一個以陣列作為引數的函式。
步驟 3 - 在變數 N 中計算並存儲陣列的長度。
步驟 4 - 遞迴計算兩個部分。
步驟 5 - 為範圍“N/2”內的每個索引 k 計算“T”的旋轉因子。
步驟 6 - 將偶數索引元素與其對應的旋轉因子相加，並從這些旋轉因子中減去偶數索引元素，以確定轉換後的值。
步驟 7 - 透過將偶數索引元素與其各自的旋轉因子相加，並從其對應的旋轉因子中減去偶數索引元素，計算轉換後的值。當計算出的轉換後的值已連線時，返回結果。
步驟 8 - 透過傳遞陣列作為引數來呼叫該函式，並顯示結果。
示例
#Import cmath module
import cmath
#A Function is created that takes an array as a parameter
def ftt_cooley_tukey(x):
#Compute the length of an array
N = len(x)
#For if the length is equal to 1 return the original array
if N == 1:
return x
# Take even part
evenPart = ftt_cooley_tukey(x[::2])
# Take odd part
oddPart = ftt_cooley_tukey(x[1::2])
#The twiddle factors for T for each index k are computed
T = [cmath.exp(-2j * cmath.pi * k / N) * oddPart[k] for k in range(N // 2)]
#Return the transformed value
return [evenPart[k] + T[k] for k in range(N // 2)] + [evenPart[k] - T[k] for k in range(N // 2)]
#An instance of the input array
example_array = [1, 2, 3, 4]
output = ftt_cooley_tukey(example_array)
print("Approach 1 - Cooley-Tukey FFT Algorithm with Complex Numbers:")
print("Output Array:", output)
輸出
Approach 1 - Cooley-Tukey FFT Algorithm with Complex Numbers: Output Array: [(10+0j), (-2+2j), (-2+0j), (-1.9999999999999998-2j)]
方法 2：使用整數的 Cooley-Tukey 演算法
Cooley-Tukey 演算法已針對整數修改了 NTT 演算法，以便在使用模運算的有限域上執行。當處理數論和密碼學的應用時，這種方法特別有用，因為計算是在素數整數模下進行的。
演算法
在 Python 中執行數論變換的演算法如下：
步驟 1 - 匯入 numpy 模組。
步驟 2 - 建立一個以陣列、原根和素數值作為引數的函式。
步驟 3 - 遞迴計算偶數和奇數部分。
步驟 4 - 變數 g_squared_mod_p 生成並存儲旋轉因子 g 的 2 次冪模 p。
步驟 5 - 遍歷陣列並計算 (factor * odd[i])%p 並將結果儲存在 term 中。然後計算 (even[i] + term)% p 的第一個分量並將其賦值給 result[i]。然後計算 (even[i] - term)% p 的第二個分量並將其新增到 result[i + N // 2] 中。將 factor 乘以 g_squared_mod_p 以更新它。
步驟 6 - 返回結果。
步驟 7 - 透過傳遞所需的引數來呼叫該函式，並顯示結果。
示例
#Import numpy module
import numpy as np
#Create a function that takes an array, primitive root, and prime.
def ntt_cooley_tukey(x, p, g):
N = len(x)
if N == 1:
return x
# Compute odd and even part
evenPart = ntt_cooley_tukey(x[::2], p, (g * g) % p)
oddPart = ntt_cooley_tukey(x[1::2], p, (g * g) % p)
g_squared_mod_p = (g * g) % p
factor = 1
result = np.zeros(N, dtype=int)
# for the N/2 range
for i in range(N // 2):
term = (factor * oddPart[i]) % p
#Compute the first part of the result
result[i] = (evenPart[i] + term) % p
# Compute the second part of the result
result[i + N // 2] = (evenPart[i] - term) % p
# Update the factor by multiplying with g_squared_mod_p.
factor = (factor * g_squared_mod_p) % p
return result
# An array with some values is created
input_array = np.array([1, 2, 3, 4])
prime = 5
primitive_root = 2 # The primitive root for prime 5
output = ntt_cooley_tukey(input_array, prime, primitive_root)
print("Approach 2 - Cooley-Tukey Algorithm with Integers:")
print("Output Array:", output)
輸出
Approach 2 - Cooley-Tukey Algorithm with Integers: Output Array: [0 0 3 1]
結論
我們研究了兩種在 Python 中將數論變換 (NTT) 演算法付諸實踐的方法。在第一種方法中，使用 Cooley-Tukey 快速傅立葉變換 (FFT) 對複數進行了變換，而在第二種方法中，使用了素數模下的整數。根據當前挑戰的需求，可以使用任何一種方法，因為它具有相對於另一種方法的優勢。複數和基於 FFT 的方法提供了一種簡單而優雅的解決方案，可以進行快速計算。另一方面，基於整數的方法具有在有限域中執行的優勢，這在與數論和密碼學相關的應用中特別有利。
379 次瀏覽
