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

Bài viết 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ế.
Nội dung trích xuất từ tài liệu:
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