1. Trang Chủ
  2. Tự động hoá
  3. 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

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ế. 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à ch

Thể loại Tài liệu miễn phí Tự động hoá

Số trang 9

Ngày tạo 8/15/2019 3:00:41 PM +00:00

Loại tệp PDF

Kích thước 0.77 M

Tên tệp

Tải Về một phương pháp nhân đa thức dựa trên định lý p... (.pdf)

Xem mẫu

  1. 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
  2. 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|
  3. 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|
  4. Công nghệ nghệ thông tin & C Cơ ơ sở sở toán học cho tin học Vi Việc ệc nhân các đa th thứcc bao ggồm m các phép toán sau: Th Thựcc hi hiệện n biến bi n đổ đổii Fourier, nhân các vectơ thu đư đượợcc và th thự ựcc hiện hi n phép bibiếếnn đđổii Fourier ngh nghịchch đđảảo. o. Trong ttấtt ccả các phép toán này ttốn n kém nhnhấtt là phép nhân trong trư trườngng p. Do đó, chúng ta đánh giá đđộ ộ phức tạp của ủa thuật toán dựa tr trên ố phép nhân cần thiết theo modulo pp. ên ssố Đ Định ịnh lý 2. 2 Cho trưtrước ớc hai đa thức có bậc nhỏ hhơn ơn n, trong đó giá tr trịị tuyệt đối của từng hệệ số nhỏ hhơnơn B. N Nếuếu số nguyên nguyên tốtố p th thỏa ỏa m mãnãn các điều điều kiện của Định llý ý 1, vi ệc nhân các việc đa th thức ức trên trên b ằng cách sử dụng thuật toán FFT cần thực hiện n(2 bằng 2 + 3 log(n)) log( )) phép nhân trong trư trường h u hhạnn p. ng hữu Ch ứng minh: M Chứng Mộtột phép nhân FFT (đ (đơn) ơn) riêng bibiệt ệt gồm ba bbư ước ớc sau: 1. Biến Biến đổi Fourier của hai đa thức có bậc bé hhơn ơn n đòi hỏi 2n òi hỏ 2nlog( log(n n)) phép nhân trong trư ng p (chúng ta bi trường biến ến đổi mỗi một đa thức th thành ành một một vector có 22n hệệ số). 2. Nhân các ttọaa đđộộ củủaa hai vectơ vvớii 22n hệ số yêu cầ cầuu 22n phép nhân trong p. 3. Biến Biến đổi Fourier ng ngư ngượcợc của vector với 2n hệệ số đòi hỏi n log (n) phép đòi hỏi hép nhân trong p. Đi Điềềuu này có nghnghĩaĩa llàà m mộộtt phép nhân đơn hai đa th thứứcc ssử ddụng ng thuậ thuậtt toán FFT ccần n có n((2+3 2+3 log ((n)) )) phép nhân trong trư trườ ờng ng p, Đi Điều ều cần CM. Các thuật thuật toán nhân đđược ợc đề xuất có thể sử dụng để tính toán biến đổi ng ngược ợc tr trên ên vành các chu chuỗi ỗi lũy ththừa ừa với các hệ số nguynguyên.ên. Một Một chuỗi nh như ư vvậy ậy có thể đảo ng ngưược ợc khi vvàà chỉ khi hệ số của nó có số mũ thấp nhất bằng 1 hoặc -1. chỉ -1. Sử Sử dụng ph phương ương pháp llặp ặp Newton cho các vành (padded ring) cho phép chúng ta nhanh chóng xác đđịnh ịnh nghịch đảo của chuỗi. Phương chuỗi. Phương pháp Newton tính toán ngh nghịchịch đảo nhanh vvìì ch chỉỉ sử dụng phép nhân, phép cộng ộng vvàà trừ trừ chuỗi. Để biến đổi ng ợc chuỗi có n hệ ngược hệ số chúng ta phải thực hiện log n phép lặp. ặp. Nếu chuỗi lũy thừa có tính nghịch đảo có dạng: n 1 A  X k aj X j, j 0 thì giao th thức ức sau cho phép tìm ngh nghịch ịch đảo của nó với n hệ số: Thuật toán 1. Đ Thuật Đảo ảo ng ngược ợc chuỗi lũy thừa bằng cách sử dụng ph phương ương pháp llặp ặp Newton Newton. 3. S SỬ Ử DỤNG ĐỊNH LÝ PHẦN D DƯƯ TRUNG HOA Đ ĐỂ PHÂN CHIA TÍNH TOÁN GI GIỮA ỮA CÁC BỘ VI XỬ LÝ Đ Để giảm gi m độ đ ph phứức tạạp p tính toán ccủaa thu thuậtt toán trên, chúng ta ssử dụng d ng định đ nh lý ph phần n dư Trung Hoa. Cách ti tiếpp ccậận n này sẽ s cho phép chúng ta thay th thế phép nhân đơn trong trư trườ ờng ng p bằằng ng nhi nhiều u phép nhân nh nhỏ hơn trong trưtrường ng p. Một Một ưu điểm điểm khác của cách tiếp cận này là kh năng phân chia tính toán trong trư khả trườ trường ng p giữa giữa các bộ vi xử lý. Để đạt đđược ợc mục đích, trước hết phải ttìm trước ìm ra các ssố ố nguyên t pi cho phép th nguyên tố thực ực hiện ý ttưởng ởng đề xuất trong thực tế. 190 Nguyễn Nguyễn Thị Thu Nga Nga,, “Về Vềề một ph phương ương pháp nhân đa th thức ức … biến nhanh.”” ến đổi Fourier nhanh
  5. Nghiên cứu khoa học công nghệ Định lý 3 Cho f(X) = fn-1 X n-1 + … + f1X + f0, g(X) = gn-1 Xn-1 +• • •+ g1X+g0 là các đa thức với hệ số nguyên, sao cho |fi|
  6. Công nghệ thông tin & Cơ sở toán học cho tin học Chứng minh: Vì ⌊log2(pi)⌋ = ⌊log2(pj)⌋ cho tất cả i,j; nên chúng ta có thể giả định rằng chi phí để thực hiện phép nhân trong mỗi phần tử trường Fpi là như nhau. Phép nhân các đa thức sử dụng biến đổi Fourier nhanh FFT gồm ba bước sau: 1. Sự giảm các hệ số modulo đòi hỏi phải thực hiện c1k2n phép nhân trong trường pi. Mỗi hệ số đa thức có độ chính xác k liên quan đến số đo của số pi. Do đó, một hệ số duy nhất có thể được giảm bằng cách sử dụng (1∕2)c1k phép nhân trong trường pi (Thuật toán 2). Bởi vì chúng ta có hai đa thức như vậy, mỗi một trong số chúng đều có n hệ số, và số các số nguyên tố là k, thì tổng số phép nhân cần thiết bằng (1/2) c1.k.2.n.k = c1k2n. 2. Chúng ta sử dụng thuật toán nhân nhanh FFT trong các trường pi với i ∈ {1 ,. . . , k}: (a) Biến đổi Fourier của hai đa thức bậc nhỏ hơn n đòi hỏi phải thực hiện 2nlog(n) phép nhân trong trường pi (các đa thức được biến đổi thành các vectơ với 2n hệ số), (b) Việc nhân hai vectơ mà mỗi vectơ có 2n hệ số đòi hỏi thực hiện 2n phép nhân trong trường pi, (c) Biến đổi Fourier ngược đối với vector có 2n hệ số cần nlog (n) phép nhân trong trường pi. 3. Sử dụng định lý phần dư Trung Hoa cho phép tạo ra các hệ số của tích nhờ c2k2n phép nhân trong trường pi. Kết quả trên là do mỗi một lời giải của hệ phương trình x ≡ ai mod pi có thể được tạo nên nhờ sử dụng (1/2)c2k2 phép nhân trong trường pi. Bởi vậy, chúng ta phải tạo ra 2n hệ số, thì tổng số phép nhân cần thiết bằng (1/ 2)c2k2 • 2n = c2k2n. Do đó, thuật toán mô tả trong Định lý 3 đòi hỏi thực hiện: c1k2n + kn (2+3 log (n)) + c2k2n phép nhân trong trường pi. Bây giờ chúng ta so sánh độ phức tạp tính toán của các thuật toán được mô tả trong các định lý 2 và 3. Để làm điều này, trước tiên chúng ta phải đưa vào một thước đo thống nhất về độ phức tạp tính toán của cả hai thuật toán. Trong trường hợp này là số phép nhân trong trường p. Chúng ta có thể đưa ra kết luận sau: - So sánh thuật toán mới với phương pháp áp dụng phép biến đổi Fourier nhanh cả để nhân các đa thức và nhân các số. Nếu chúng ta giả định rằng số pi chứa trong một thanh ghi bộ xử lý, thì độ phức tạp tính toán của thuật toán nhân đa thức và các hệ số của nó nhờ sử dụng phép biến đổi Fourier nhanh FFT khoảng: O((n log n)(k log k)). Còn thuật toán của chúng ta có độ sự phức tạp tính toán: O(kn log n + k2n). Giả sử rằng k = O(n), thì chúng ta thấy rằng thuật toán dựa hoàn toàn trên phép biến đổi Fourier FFT nhanh hơn nhiều. Độ phức tạp tính toán của nó là O(n2 log2n) trong khi thuật toán đề xuất hoạt động trong khoảng thời gian O(n3). Giả sử rằng các hệ số đa thức nhỏ hơn và k= O(log n). Khi đó, thuật toán dựa hoàn toàn trên phép biến đổi Fourier FFT nhanh có sự phức tạp tính toán O(n log2n log log n) trong khi phương pháp đề xuất có phức tạp tiệm cận O(n log2 n). Vì vậy, thuật toán hiệu quả nhân nhanh đa thức đã được phát triển. Hệ quả 1. Nếu k = O(log n), thì độ phức tạp tính toán của thuật toán đề xuất nhỏ hơn độ phức tạp tính toán của thuật toán nhân chỉ dựa trên việc sử dụng phép biến đổi Fourier FFT và bằng: O(n log2 n), Trong khi độ phức tạp tính toán của thuật toán dựa trên phép biến đổi FFT khoảng: O(n log2 n log log n). 192 Nguyễn Thị Thu Nga, “Về một phương pháp nhân đa thức … biến đổi Fourier nhanh.”
  7. Nghiên ccứu ứu khoa học công nghệ Như đã đã minh chchứng ứng trong các thực nghiệm, thuật toán đề xuất có ưu đi ểm rrõ ràng điểm trong trường trường hợp hệ số của các đa thức có giá trị cỡ vvài ài trăm bit. Có ngh nghĩa ĩa là l à ứng dụng có ệu quả đối với các giá trị bé của k và n. hiệu 4. K KẾT ẾT QUẢ THỰC HIỆN TR TRÊN ÊN BỘ BỘ VI XỬ LÝ 64 BIT Chúng tôi đđãã ththực ực hiện thuật toán nhân nhanh đa thức tr trên ên bbộ ộ vi xử lý vvới ới kiến trúc 64-bit 64 bit ssử ử dụng ththư ư vi viện ện OpenMP. Các kết quả thời gian thu đđược ợc chứng minh rằng nhờ kết hợp ợp biến đổi Fourier nhanh với định lý phần ddư ư Trung Hoa đđãã làm ttăngăng một một cách đáng kể tốc ốc độ tính toán. Để so sánh kết quả các phép đo, ta cũng xác định tthời ời gian thực hiện thuật toán nhân đa th thức ức bằng ph ương pháp cổ phương cổ điển. Các kết quả so sánh thời gian tính bằng thuật toán cổ điển với thời gian thực hiện tr thuật trên ên các bbộ ộ vi xử lý đa llõi õi (4 nhân) ddựa ựa trên trên bi biến ến đổi ổi Fourier vvàà định định lý phần ddưư Trung Hoa đưđược ợc trình trình bày bày trong các bảng bảng 1 và và 2. Hình 1 và 2 trình bày gigiải ải thích bằng đồ họa của các kết quả thu đđư ược. ợc. Cần llưu ưu ý rằng rằng cả hai tọa độ trên hoành đđộ ộ và và tung đđộộ đđược ợc biểu diễn trong thang lôgarít. ảng 1. So sánh phương pháp nhân ccổ Bảng ổ điển với thuật toán đề xuất nhân hai đa ththức ức bậc n/2 - 1 với với hệ số 256 bit bit.. Hình 1. So sánh ttốc ốc độ thực hiện các thuật toán nhân các đa thức với hệ số 256 bit bit. Tạp ạp chí Nghi Nghiên ên cứu cứu KH&CN quân uân sự, sự, Số 599, 022 - 2019 20 9 193
  8. Công nghệ nghệ thông tin & C Cơ ơ sở sở toán học cho tin học ảng 2. So sánh phương pháp ccổ Bảng ổ điển với thuật toán đề xuất nhâ nhân n hai đa th thức ức bậc n/2 - 1 với với các hệ số 512 bit bit.. Hình 2. So sánh tốc tốc độ thực hiện của các thuật toán nhân đa thức với các hệ số 512 bit bit. 5. K KẾT ẾT LUẬN Bài báo đđãã phân tích chi ti tiết ết về ph phương ương pháp nhân đa th thức ức vvàà chuỗi chuỗi lũy thừa đư được ợc đề xuất dựa tr xuất trên ên ý ttư ưởng ng ttận ận dụng tối đa khả năng tính toán của bộ vi xử lý đa nhân hiện đại và ssửử dụng định lý phần ddư ư Trung Hoa. Thu Thuật ật toán tr trên ên đư được ợc thực hiện bằng sử dụng chuẩn lập trình chuẩn trình song song m mở ở OpenMP. Thuật Thuật toán dựa tr trên ên đđịnh ịnh lý phần ddưư Trung Hoa (CRT) và bi biến ến đổi Fo urier nhanh Fourier (FFT) nên ssử ử dụng trong tr ờng hợp số lư trường lượng ợng các hệ số của đa thức lớn hhơn ơn nhi nhiềuều so với độộ chính xác của chúng, khi đó tính toán đđư ược ợc thực hiện trtrên ên các đa ththức ức hoặc chuỗi lũy thừa ừa với sự rút gọn modulo các hệ số đa thức. Các kết kết quả kiểm định, đánh giá thu đư đượcc cho thấy th y phương pháp đđề xuấ xu ấtt có ý ngh nghĩa ĩa thựựcc ti tiễn n cao. Thu Thuậtt toán đđề xuấấtt đãđ đư đượ ợcc so sánh vvớii việ vi c th thựcc hiện hi n thuật thu t toán ccổ điđiển n nhân các hhệệ số ố trong các trưtrườờng ớn. Kết quả thực nghiệm chỉ ra rằng thu ng p lớn. ật toán dựa thuật trên đđịnh ịnh lý phần ddưưT Trung rung Hoa (CRT) và bi biến ến đổi Fourier nhanh (FFT) đềề xuất nhanh 194 Nguyễn Nguyễn Thị Thu Nga Nga,, “Về Vềề một ph phương ương pháp nhân đa th thức ức … biến nhanh.”” ến đổi Fourier nhanh
  9. Nghiên cứu khoa học công nghệ hơn nhiều lần, ngay cả khi không thực hiện nhân song song. So sánh với thuật toán nhân đa thức bằng phương pháp cổ điển với độ phức tạp O (n2) (Bảng 1 và 2) cũng chỉ rõ ưu điểm tuyệt đối của thuật toán đề xuất. Có thể kết luận rằng các thuật toán đề xuất đã tạo ra một phương pháp mới hiệu quả nhân nhanh các đa thức ứng dụng trong thực tiễn; đặc biệt là trong các ứng dụng mật mã. Bài báo này được hỗ trợ một phần bởi đề tài PTNTĐ17.01 từ Phòng thí nghiệm Trọng điểm về Công nghệ Mạng và Đa phương tiện, Viện Hàn lâm KH&CN Việt Nam. TÀI LIỆU THAM KHẢO [1]. K. Lauter, “Computing modular polynomials”, Journal of Computational Mathematics, pp. 195–204, 2005. [2]. A. Chmielowiec, “Szybka transformata Fouriera w kryptografii klucza publicznego”. Centrum Modelowania Matematycznego Sigma, 3 września 2008 [3]. A. Enge, “Computing modular polynomials in quasi-linear time”, Math. Comp., vol. 78, pp. 1809–1824, 2009. [4]. L. Garcia, “Can Schönhage multiplication speed up the RSA encryption or decryption?”, University of Technology, Darmstadt, 2005. [5]. A. Grama, A. Gupta, G. Karypis, V. Kumar, “Introduction to Parallel Computing”, Addison Wesley, 2003. [6]. D. Harvey, “A cache-friendly truncated FFT”, Theoretical Computer Science, vol. 410, pp. 2649–2658, 2014. [7]. P. Montgomery, “Modular Multiplication Without Trial Division”, Mathematics of Computation, vol. 44, str. 519–521, 1985. [8]. J. van der Hoeven, “The truncated Fourier transform and applications”, in: ISSAC 2014, ACM, pp. 290–296, 2014. ABSTRACT A METHOD OF MULTIPLYING POLYNOMIALS BASED ON CHINESE REMAINDER THEOREM AND FAST FOURIER TRANSFORM This paper presents an efficient method of multiplying the polynomials and power series with the integer coefficients in the generation of parameters for public key cryptographic systems, which effectively speed up the implementation of algorithms in real applications. This approach adapts them to parallel computing to maximize the computing power of modern microprocessors. The combination of the Chinese Remainder Theorem and the Fast Fourier Transform made it possible develop a high effective multiplication method. Keywords: Multiply polynomial in parallel; FFT- Fast Fourier Transform; CRT- Chinese Remainder Theorem. Nhận bài ngày 25 tháng 10 năm 2018 Hoàn thiện ngày 21 tháng 11 năm 2018 Chấp nhận đăng ngày 19 tháng 02 năm 2019 Địa chỉ: Viện Công nghệ thông tin, Viện Hàn lâm Khoa học và Công nghệ Việt Nam. * Email: ngant1983@hotmail.com. Tạp chí Nghiên cứu KH&CN quân sự, Số 59, 02 - 2019 195
nguon tai.lieu . vn
Kiến trúc - Xây dựng Tự động hoá Điện - Điện tử Kĩ thuật Viễn thông Cơ khí - Chế tạo máy Năng lượng Hoá dầu Hoá học Sinh học