Về một phương pháp nhân đa thức dựa trên định lý phần dư Trung Hoa và phép biến đổi Fourier nhanh

Nghiên cứu khoa học công nghệ VỀ MỘT PHƯƠNG PHÁP NHÂN ĐA THỨC DỰA TRÊN ĐỊNH LÝ PHẦN DƯ TRUNG HOA VÀ PHÉP BIẾN ĐỔI FOURIER NHANH Nguyễn Thị Thu Nga* Tóm tắt: Bài báo trình bày một phương pháp hiệu quả nhân nhanh các đa thức và chuỗi lũy thừa có các hệ số nguyên ứng dụng trong việc tạo các tham số cho các hệ thống mật mã khóa công khai, mà hiệu quả của chúng làm tăng tốc độ thực hiện các thuật toán trong các ứng dụng thực tế. Phương pháp này là thích ứng chúng với tính toán song song cho phép khai thác tối đa khả năng tính toán của các bộ vi xử lý hiện đại. Nhờ kết hợp định lý phần dư Trung Hoa và phép biến đổi Fourier nhanh cho phép phát triển một phương pháp nhân nhanh hiệu quả. Từ khóa: Phép nhân song song đa thức; FFT - Biến đổi Fourier nhanh; CRT - (Định lý phần dư Trung Hoa) Chinese Remainder Theorem. 1. MỞ ĐẦU Năm 1971, Schönhage và Strassen đã đưa ra một thuật toán mới cho phép nhân các số nguyên lớn. Kể từ đó các thuật toán nhân nhanh dựa trên biến đổi Fourier nhanh FFT (Fast Fourier Transform) đã được cải tiến liên tục . Ngày nay, chúng ta có nhiều thuật toán nhân nhanh các số nguyên lớn [1] và nhân nhanh đa thức [7]. Một số thuật toán không phụ thuộc vào kiến trúc bộ xử lý và một số khác được thiết kế giành cho một hệ thống tính toán cụ thể. Mặc dù FFT có một lợi thế so với các thuật toán nhân cổ điển, nhưng phiên bản giành cho các máy tính đa nhân không dễ thực hiện. Ngoài ra, khi nhân các số nguyên lớn bằng phương pháp FFT chỉ hiệu quả khi các số có trên 100.000 bit [4]. Để khắc phục điều này cần tạo một thuật toán cùng một lúc sử dụng FFT và định lý phần dư Trung Hoa CRT (Chinese Remainder Theorem). Định lý phần dư Trung Hoa thường được sử dụng để tăng tốc độ tính toán trong thuật toán mật mã RSA. Việc sử dụng CRT cho phép tách và thực hiện song song các phép toán ký hoặc giải mã. Bài báo trình bày một thuật toán hiệu quả nhân nhanh các đa thức có các hệ số nguyên. 2. BIỂU DIỄN CÁC PHẦN TỬ TRƯỜNG VÀ PHÉP NHÂN NHANH TRONG VÀNH ĐA THỨC Trong phần này sẽ trình bày ngắn gọn về phương pháp tối giản Montgomery. Bổ đề sau đây là cơ sở cho phương pháp tối giản Montgomery [7]: Bổ đề 1. Cho a, b, M, R là các số nguyên sao cho (M, R) = 1, a, b , R2 = <{0,1, . . . , M-1}, 0, R mod M, + , - , ⊙ > Tạp chí Nghiên cứu KH&CN quân sự, Số 59, 02 - 2019 187  Công nghệ thông tin & Cơ sở toán học cho tin học và được định nghĩa như sau: a ± b = a ± b mod M a • b = ab mod M a ⊙ b = abR-1 mod M, thì R1 và R2 đẳng cấu cùng nhau Chứng minh: Chúng ta định nghĩa biến đổi h: R1 → R2 như sau: h (x) = xR mod M Vì M và R nguyên tố cùng nhau, thì R là một modulo M có thể đảo ngược. Điều này có nghĩa là h trong thực tế là một song ánh. Để hoàn thành chứng minh chúng ta phải chỉ ra rằng biến đổi h là một đồng cấu: 1. h(0) = 0, h(1) = R mod M, 2. h(a ± b) = (a ± b)R mod M = (aR ± bR) mod M = h(a) + h(b), 3. h(a • b) = abR mod M = (aRbR)R-1 mod M = h(a) ⊙ h(b). Điều này đã được chứng minh. Giả thiết rằng: n là một số lũy thừa của 2 và lớn hơn bậc tối đa của đa thức đa thức muốn nhân. Giả định rằng giá trị tuyệt đối các hệ số của đa thức nhỏ hơn B. Định nghĩa 1: cho f(X) = fn-1 X n-1 + • • • + f1X + f0 ∈ ℤ[X] và M ∈ ℤ. Chúng ta định nghĩa f(X) mod M như sau: f(X) mod M = (fn-1 mod M)Xn−1 + • • • + (f0 mod M),  M  1  M  1  Trong đó, f i mod M     ,..., 1, 0,1,...,   , với i từ 0 đến n-1  2   2   Nếu lựa chọn được một số hợp lý M thì nhân hai đa thức trong vành (ℤ/Mℤ)[X] cho cùng kết quả như nhân chính các đa thức đó cùng trong vành ℤ[X]. Bổ đề sau chỉ ra cách chọn số M để đạt được kết quả này. Bổ đề 2. Cho f(X) = fn-1X n-1 + … + f1X + f0, g(X) = gn-1 Xn-1 + • • •+ g1X+g0 là các đa thức có hệ số nguyên, sao cho |fi| 2nB2 thì tất cả các hệ số (được mô tả trong định nghĩa 1) của các đa thức f(X), g(X) và h(X) được biểu diễn trong 188 Nguyễn Thị Thu Nga, “Về một phương pháp nhân đa thức … biến đổi Fourier nhanh.” Nghiên cứu khoa học công nghệ vành là phần dư theo modulo M mà không cần rút gọn. Điều đó suy ra phương trình f(X) g(X) mod M = f(X) g(X). Định lý 2. Cho f(X) = fn-1 X n-1 + … + f1X + f0, g(X) = gn-1 Xn-1 +• • •+ g1X+g0 là các đa thức có hệ số nguyên, sao cho |fi|