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ệ Tạp chí Nghiên cứu KH&CN quân sự, Số 59, 02 - 2019 187 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 tố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 tốn song song cho phép khai thác tối đa khả năng tính tố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 tốn mới cho phép nhân các số nguyên lớn. Kể từ đĩ các thuật tố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 tố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 tố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 tốn cụ thể. Mặc dù FFT cĩ một lợi thế so với các thuật tố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. Ngồ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 tố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 tốn trong thuật tố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 tốn ký hoặc giải mã. Bài báo trình bày một thuật tố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 <M <R, q = -M-1 mod R, và t1 = a • b t2 = t1 mod R t3 = t2 • q t4 = t3 mod R t5 = t4 •M t = (t1 + t5)/R. Khi đĩ, một trong những phương trình sau đây là đúng: abR-1 mod M = t hoặc abR-1 mod M = t - M. Trong thực tế, số M thường là số lẻ, và R là lũy thừa của số 2. Điều này cĩ nghĩa là việc giảm và phân chia theo modulo R dẫn đến giảm thích hợp một số lượng bit cao và bit thấp. Thực tế rút gọn Montgomery cho phép thực hiện tính tốn hiệu quả trên vành ℤ/Mℤ. Định lý 1. Cho M và R là các số nguyên dương. Nếu (M, R) = 1,M < R và vành R1 = , R2 = Cơng nghệ thơng tin & Cơ sở tốn học cho tin học Nguyễn Thị Thu Nga, “Về một phương pháp nhân đa thức biến đổi Fourier nhanh.” 188 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. Để hồ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)X n−1 + • • • + (f0 mod M), Trong đĩ, 1 1 mod ,..., 1,0,1,..., , 2 2 i M M f M                    với i từ 0 đến n-1 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 X n-1 + • • •+ g1X+g0 là các đa thức cĩ hệ số nguyên, sao cho |fi| <B và |gi| <B với i = 0, 1 ,. . . , n - 1. Nếu số nguyên M thỏa mãn điều kiện: 2nB2 <M Thì f (X)g(X) mod M = f(X)g(X) Chứng minh: Nếu f(X)g(X) = h(X) = h2n-2 X 2n-2 + • • • + h1X + h0 thì   1 1 0 0 n n i j i j i j h X f X g X                 1 1 1 1 1 0 0 1 0 n i n n i i n i j i j i j n j i j i j f g X f g X                  1 1 1 1 1 1 0 0 0 0 n n n n i i n i j i j i j n j i i i j X f g X f g                     Bởi vì | fi | < B và | gi | < B nên chúng ta cĩ 1 1 2 2 1 10 0 0 1. ( 1) n i n i i i i j n j i j n jj j j h f g f g B i B                   với i từ 0 đến n-1. 1 1 2 2 1 1 10 0 0 2. ( ) n i n i i n i i j n j i j n jj j j h f g f g B n i B                     với i từ 0 đến n-1. Điều đĩ cĩ nghĩa là |hi|<nB 2 với mọi i từ 0 đến 2n - 2. Nếu M>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 Nghiên cứu khoa học cơng nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 59, 02 - 2019 189 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 X n-1 +• • •+ g1X+g0 là các đa thức cĩ hệ số nguyên, sao cho |fi| <B và |gi| <B|. Nếu số nguyên tố p thỏa mãn các điều kiện sau: (1) 2nB2 <p, (2) p = 2 m+1 r + 1 với 2 m+1 ≥ 2n và r ∈ ℤ, thì f(X)g(X) = f(X)g(X) mod p = (f(X) mod p)(g(X) mod p) mod p và trường p cĩ thể sử dụng để nhân đa thức f và g bằng cách sử dụng thuật tốn FFT. Chứng minh: Bởi vì tốn tử mod p đồng cấu tự nhiên của vành ℤ, nên (f(X) mod p)(g(X) mod p) mod p = f(X)g(X) mod p Trên cơ sở của Bổ đề 2 chúng ta cĩ được đẳng thức: f(X)g(X) mod p = f(X)g(X). Như vậy, việc nhân các đa thức f (X), g (X) ∈ ℤ[X] cho cùng kết quả như phép nhân đa thức f(X) mod p, g(X) mod p ∈ p[X] với điều kiện các phần tử của trường p[X] được biểu diễn bằng các số 1 1 ,..., 1,0,1,..., . 2 2 p p        Số nguyên tố cĩ dạng p = 2m+1r + 1 được chọn khi sử dụng thuật tốn FFT, do thực tế là với một số p xác định, trường p cĩ nghiệm nguyên thủy với phần tử đơn vị bậc 2 m+1. Áp dụng biến đổi Fourier nhanh trên trường hữu hạn thay vì trên trường số phức cho phép loại bỏ các phép tốn dài, phức tạp trên số dấu phẩy động và thay bằng các phép tính nhanh trên số nguyên. Điều này cho phép xây dựng một thuật tốn nhanh hơn, bởi vì trên bộ vi xử lý Intel Core 2 thì thực hiện phép nhân các số nguyên khoảng 30 lần nhanh hơn so với thực hiện phép nhân trên số dấu phẩy động. Trường hữu hạn được đề xuất sử dụng vì hai lý do: 1. Tối đa hĩa tốc độ của thuật tốn, 2. Loại bỏ lỗi làm trịn, được đặc trưng bởi các phép tốn trên các số dấu phẩy động. Tất nhiên, ở dây phát sinh câu hỏi về các điều kiện cần phải thỏa mãn sao cho việc thực hiện các thuật tốn nhân đa thức nhanh nhất. Để trả lời câu hỏi này, cần lưu ý rằng phép tốn chính được thực hiện khi nhân đa thức là phép nhân trong trường hữu hạn p. Gồm phép nhân các số nguyên và quy về theo modulo. Tối ưu hĩa việc quy về theo modulo cho kết quả tốt nhất về tốc độ thuật tốn nhân đa thức. Thơng thường, bài tốn quy về theo modulo được giải quyết bằng một trong ba cách: (a) Tìm một số nguyên tố p, sao cho phép tốn rút gọn theo modulo dẫn đến thực hiện một số phép cộng và phép trừ. Thực tế là cĩ rất nhiều số nguyên tố như vậy. Ví dụ: 2224 – 296 + 1 = 296 (2128 - 1) + 1 hoặc 2512 – 232 + 1 = 232 (2480 - 1) + 1. (b) Một phương pháp tối ưu hĩa khác phép rút gọn theo modulo là sử dụng thuật tốn rút gọn Montgomery [7]. Phương pháp này tổng quát hơn và cĩ thể áp dụng cho bất kỳ số nguyên tố nào khác 2. (c) Cuối cùng, cĩ thể sử dụng thuật tốn cổ điển để tính tốn tỉ số và phần dư của phép chia, nhược điểm của phương pháp này là rất khĩ thực hiện một cách hiệu quả [7]. Phương pháp đề xuất trong (a) cho phép tính tích các phần tử phần tử trường hữu hạn chỉ sử dụng một phép nhân số nguyên và chắc chắn là nhanh nhất trong số các phép tính được đề xuất. Các số nguyên tố dạng đặc biệt này cĩ vai trị quan trọng trong mật mã và thường được sử dụng trong các thuật tốn dựa trên đường cong elliptic (FIPS 186-3 và ANSI X509.62). 190 các vectơ thu đư tốn này t của thuật tốn dựa tr hệ số nhỏ h đa th trong trư trư n( vành các chu ch cho các vành (padded ring) cho phép chúng ta nhanh chĩng xác đ chu cộng v lặp. Nếu chuỗi lũy thừa cĩ tính nghịch đảo cĩ dạng: thì giao th Thu Trung Hoa. Cách ti bằ kh trư Vi Đ ức tr Ch 1. Bi ờng 2. Nhân các t 3. Bi Đi 2+3 Các thu ỉ khi hệ số của nĩ cĩ số mũ thấp nhất bằng 1 hoặc ỗi. Ph Đ ng nhi ả năng phân chia tính tốn trong trư ớc hết phải t ệc nhân các ịnh lý 2 ứng minh: ề log ( à tr ật tốn 1. ể gi Nguy ốn kém nh ên b ờng h ến đổi Fourier của hai đa thức cĩ bậc bé h p (chúng ta bi ến đổi Fourier ng u này cĩ ngh ương pháp ừ chuỗi. Để biến đổi ng ức sau cho ảm đ ều phép nhân nh ễn Thị Thu Nga ơn B. N ằng cách sử dụng thuật tốn FFT cần thực hiện n)) phép nhân trong trư ật tốn nhân đ ỗi lũy ợ . Cho trư ữu h Đ 3. S PHÂN CHIA TÍNH TỐN GI ộ ph ìm ra các s đa th c và th ếu số nguy ạn M ọa đ th ảo ng ứ ếp c ất là phép nhân trong trư ên s p ột phép nhân FFT (đ ến đổi mỗi một đa thức th ộ ĩa l ừa với các hệ số nguy Newton tính tốn ngh phép tìm ngh Ử DỤNG ĐỊNH LÝ PHẦN D c tạ ậ ức bao g ự ố phép nhân cần thiết theo modulo ớc hai đa thức cĩ bậc nhỏ h . củ ư à m ược chuỗi lũy thừa bằng cách sử dụng ph p tính tốn c n này s ỏ ố nguy , c hi a hai vectơ v ợc của vector với ộ ược đề xuất cĩ thể sử dụng để tính tốn biến đổi ng hơn trong trư “Về một ph ện phép bi ên t t phép nhân đơn hai đa th ẽ ên t ồm các phép tốn sau: Th ố ờ ược chuỗi cĩ ịch đảo của nĩ với n hệ số: cho phép chúng ta thay th p th ng ủa thu ờ ố p ương pháp nhân đa th ế ỏa m ới 2 p, Đi A X a X ờng ng i cho phép th Cơng ngh n đ ơn) riêng bi n ên. M ịch đảo nhanh v ật tốn trên, chúng ta s p ổi Fourier ngh ờng ãn các hệ 2n ều cần CM. n k j j  p. M gi ành m số yêu c hệ số đ ột chuỗi nh n h 1 0   ỮA CÁC BỘ VI XỬ LÝ ột ữa các bộ vi xử lý. Để đạt đ ệ thơng tin & C p. Do đĩ, chúng ta đánh giá đ ơn n, trong đĩ giá tr đi ơn - ệ số chúng ta phải thực hiện j Ư TRUNG HOA Đ ưu đi ực hiện ý t ều kiện của Định l ệt gồm ba b n ột vector cĩ 2 ầ ịi h ứ 1. S , p địi h u 2 ỏi c s ử dụng ph ì ch ế ểm khác của cách tiếp cận ức ực hi ịch đ . ỏ n phép nhân trong n log (n) ử d ư v phép nhân đơn trong trư ưởng đề xuất trong thực tế. ệ ả n(2 + 3 ư i 2n ụng thu ậy cĩ thể đảo ng ỉ sử dụng phép nhân, phép ương pháp l ơ s biến đổi Fourier nhanh n bi o. Trong t ớc sau: log( n ương pháp l ử d ở tốn học cho tin học ến đ ị tuyệt đối của từng log( n hệ số). phép nhân trong ậ ịnh nghịch đảo của ụng đ ổ ý 1, vi ) phép nhân trong t tốn FFT c Ể i Fourier, nhân ất c n)) phép nhân ặp Newton ịnh lý ph ược mục đích, ả ộ phức tạp ệc nhân các p ư ặp Newton log n các phép . ược tr ợc khi v ờ ần cĩ phép ần dư ng này là .” p. ên à . p Nghiên cứu khoa học cơng nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 59, 02 - 2019 191 Định lý 3 Cho f(X) = fn-1 X n-1 + + f1X + f0, g(X) = gn-1 X n-1 +• • •+ g1X+g0 là các đa thức với hệ số nguyên, sao cho |fi|<B và |gi|<B. Nếu các số nguyên tố pi thỏa mãn các điều kiện sau:       1 2 , 1 , 2 , 3 2 i j k ii i p p M p nB p M         1 14 2mi ip r   khi 12 2m n  và ir  Thì:              mod mod mod modf X g X f X g X M f X M g X M M  và trường pi cĩ thể sử dụng để nhân song song các đa thức f và g bằng sử dụng biến đổi nhanh Fourier (Fast Fourier Transform - FFT). Chứng minh: Chứng minh định lý này sẽ rất giống với chứng minh Định lý 1 vì tốn tử mod M đồng cấu tự nhiên trên vành ℤ thì: (f(X) mod M) (g(X) mod M) mod M = f(X)g(X) mod M. Sử dụng Bổ đề 1 chúng ta cĩ được đẳng thức sau: f(X) g(X) mod M = f(X) g(X). Điều này cĩ nghĩa là phép nhân các đa thức g(X), f(X) ∈ Z [X] cho cùng kết quả như nhân các đa thức g(X) mod M, f(X) mod M ∈ (ℤ/Mℤ) [X] miễn là các phần tử của vành ℤ/Mℤ được biễu diễn bằng các số từ tập hợp: 1 1 ,..., 1,0,1,..., . 2 2 M M        Giả định rằng M là tích của các số nguyên tố khác nhau pi, khi đĩ cĩ thể áp dụng định lý phần dư Trung Hoa và ta cĩ được đẳng cấu sau: ℤ/Mℤ ≃ p1 × • • • × pk . Các đẳng cấu trên cĩ thể mở rộng thành đồng cấu vành đa thức: (ℤ/Mℤ )[X] ≃ p1[X] × • • • × pk[X]. Điều này cĩ nghĩa là phép nhân trong vành (ℤ/Mℤ )[X] cĩ thể được thay thế bởi k phép nhân trong các vành pi[X], và mỗi phép nhân trong chúng cĩ thể được thực hiện một cách độc lập. Điều này cho phép chia tách các phép tính giữa k bộ xử lý (procesor) và thực hiện chúng một cách song song. Ngồi ra, tất cả các số nguyên tố pi = 2 m + 1 ri + 1 được chọn, sao cho phép nhân cĩ thể được thực hiện bằng thuật tốn FFT. Thực tế là mỗi trường pi chứa nghiệm nguyên thủy với phần tử đơn vị bậc 2 m + 1. Cách giải quyết được đề xuất trong định lý trên hiệu quả hơn rất nhiều so với phương pháp tiêu chuẩn được trình bày trong phần trước. Để đảm bảo hiệu suất tối đa tính tốn cần chọn các số nguyên tố pi cĩ thể chứa trong một thanh ghi của bộ xử lý. Điều này dễ dàng thực hiện với các bộ xử lý 32 và 64 bit. Giả sử bây giờ chúng ta đã tìm được k số nguyên tố pi cĩ cùng số bit và thỏa mãn giả thuyết của Định lý 3. Đối với các số như vậy thì định lý sau là đúng: Định lý 4. Cho trước hai đa thức hệ số nguyên bậc nhỏ hơn n, với giá trị tuyệt đối từng hệ số nhỏ hơn B. Nếu các số nguyên tố pi thõa mãn điều kiện định lý 3 và ⌊log2(pi)⌋ = ⌊log2(pj)⌋, khi đĩ khi nhân các đa thức như vậy sử dụng thuật tốn FFT địi hỏi thực hiện   2 21 22 3logc k n kn n c k n   phép nhân trong trường pi. Trong đĩ, c1, c2 là các hằng số xác định. Cơng nghệ thơng tin & Cơ sở tốn học cho tin học Nguyễn Thị Thu Nga, “Về một phương pháp nhân đa thức biến đổi Fourier nhanh.” 192 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 c1k 2n 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 tố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 = c1k 2n. 2. Chúng ta sử dụng thuật tố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ờ c2k 2n 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)c2k 2 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)c2k 2 • 2n = c2k 2n. Do đĩ, thuật tốn mơ tả trong Định lý 3 địi hỏi thực hiện: c1k 2n + kn (2+3 log (n)) + c2k 2n phép nhân trong trường pi. Bây giờ chúng ta so sánh độ phức tạp tính tốn của các thuật tố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 tốn của cả hai thuật tố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 tố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 tốn của thuật tố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 tốn của chúng ta cĩ độ sự phức tạp tính tốn: O(kn log n + k2n). Giả sử rằng k = O(n), thì chúng ta thấy rằng thuật tốn dựa hồn tồn trên phép biến đổi Fourier FFT nhanh hơn nhiều. Độ phức tạp tính tốn của nĩ là O(n2 log2n) trong khi thuật tố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 tốn dựa hồn tồn trên phép biến đổi Fourier FFT nhanh cĩ sự phức tạp tính tố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 tố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 tốn của thuật tốn đề xuất nhỏ hơn độ phức tạp tính tốn của thuật tố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 tốn của thuật tốn dựa trên phép biến đổi FFT khoảng: O(n log2 n log log n). Nghiên c Tạp chí Nghi trong trư hiệu quả đối với các giá trị bé của 64 hợp biến đổi Fourier nhanh với định lý phần d tốc độ tính tốn. Để so sánh kết quả các phép đo, ta cũng xác định t tốn nhân đa th thu đổi Fourier v 2 trình bày gi trên hồnh đ Như đ Chúng tơi đ -bit s ật tốn cổ điển với thời gian thực hiện tr Hình 1. ử dụng th ứu khoa học cơng nghệ ã minh ch ờng hợp hệ số của các đa thức cĩ giá trị cỡ v ên c à đ ải thích bằng đồ họa của các kết quả thu đ ộ v So sánh t ứu KH&CN 4. K ã th ư vi ức bằng ph ịnh lý phần d à tung đ ẾT QUẢ THỰC HIỆN TR ứng trong các thực nghiệm, thuật tốn đề xuất cĩ ực hiện thuật tốn nhân nhanh đa thức tr ện OpenMP. Các kết quả thời gian thu đ ốc độ thực hiện các thuật tốn nhân các đa thức với hệ số 256 bit ộ đ Bảng 1. quân s ương pháp c ư Trung Hoa đư ược biểu diễn trong thang lơgarít. ự, Số k So sánh phương pháp nhân c và 59 n. ổ điển. Các kết quả so sánh thời gian tính bằng , 02 ên các b - 20 ư Trung Hoa đ ợc tr nhân hai đa th 19 ÊN B ình b ộ vi xử lý đa l ài trăm bit. Cĩ ngh Ộ VI XỬ LÝ 64 BIT ày trong các ư ợc. Cần l ức bậc n/2 ên b ược chứng minh rằng nhờ kết ã làm t ổ điển với thuật tốn đề xuất õi (4 nhân) d ộ vi xử lý ăng m hời gian thực hiện thuật b ưu ảng 1 v ý r - 1 v ưu đi ĩa l ột cách đáng kể ằng cả hai tọa độ ới hệ số 256 bit à v à 2. Hình 1 và ểm r ứng dụng cĩ ới kiến trúc ựa tr ên bi 193 õ ràng . ến . 194 Hình 2. xu và s chu (FFT) nên s độ chính xác của chúng, khi đĩ tính tốn đ thừa với sự rút gọn modulo các hệ số đa thức. thự nhân các h trên đ Bài báo đ ất dựa tr ử dụng định lý phần d ẩn lập tr Thu Các k c ti ễn cao. Thu ịnh lý phần d Nguy So sánh t ên ý t ật tốn dựa tr ết quả kiểm định, ệ ễn Thị Thu Nga ình song song m ử dụng trong tr số ã phân tích chi ti ư trong các trư ốc độ thực hiện của các thuật tốn nhân đa thức với các hệ số 512 bit ởng t ật tốn đ ư T ận dụng tối đa khả năng tính tốn của bộ vi xử lý đa nhân hiện đại ên đ rung Hoa (CRT) và bi , ư Trung Hoa. Thu ở OpenMP. ịnh lý phần d ường hợp số l đánh giá thu đư ề ờ “Về một ph Bảng 2. ết về ph xuấ ng t đ p 5. K ã đư lớn. Kết quả thực nghiệm chỉ ra rằng ương pháp nhân đa th So sánh phương pháp c nhâ ương pháp nhân đa th ư ợ Cơng ngh n hai đa th ẾT LUẬN ư Trung Hoa (CRT) và bi ợng các hệ số của đa thức lớn h ư c so sánh v ật tốn tr ợc thực hiện tr ợc cho th ến đổi Fourier nhanh (FFT) ệ thơng tin & C ức bậc n/2 ên đư ấy phương pháp đ ới việ ức ổ điển với thuật tốn đề xuất ức v ợc thực hiện bằng sử dụng ên các đa th c th à chu ực hi ơ s biến đổi Fourier nhanh - 1 v ến đổi Fo ở tốn học cho tin học ới các hệ số 512 bit ỗi lũy thừa đ ện thu ơn nhi ức hoặc chuỗi lũy ề xu ấ ật tốn c thu đề xuất nhanh urier nhanh t cĩ ý ngh ật tốn dựa ư ều so với ợc đề ổ đi .” . . ĩa ển Nghiên cứu khoa học cơng nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 59, 02 - 2019 195 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 tố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 tốn đề xuất. Cĩ thể kết luận rằng các thuật tố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 Hồ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.