Số học mô-đun đơn giản cho mô-đun lũy thừa hai

C.S.

14:13, 04/09/2023

Tại sao nếu $q$ là một số nguyên luỹ thừa hai, sau đó thực hiện phép tính modulo số học $q$ (cộng và nhân) rất hiệu quả và đơn giản?

0 + 0

thực hiện

số học mô-đun

forest

23:00, 04/09/2023

Tôi đang bỏ phiếu để đóng câu hỏi này vì đó là về hiệu quả của hoạt động toán học đơn giản trong máy tính và không dành riêng cho mật mã.

Hồi đáp

Mark

23:30, 04/09/2023

điều đáng nói là điều này có thể liên quan đến mật mã --- một điểm khác biệt (đáng kể) giữa Sabre và Kyber lọt vào vòng chung kết PQC của NIST là Sabre có mô-đun power-of-two $2^{13}$ (và giảm mô-đun nhanh), trong khi Kyber sử dụng một mô-đun thân thiện với NTT, thừa nhận các thuật toán nhân hiệu quả hơn (nhưng phức tạp hơn). Điều này đã dẫn đến nghiên cứu mật mã so sánh cả hai và thậm chí tìm ra cách nhúng phép nhân lũy thừa hai vào vòng thân thiện với NTT.

Hồi đáp

Điểm:3

Crypto

poncho

14:23, 04/09/2023

Tại sao nếu $q$ là một số nguyên luỹ thừa hai, sau đó thực hiện phép tính modulo số học $q$ (cộng và nhân) rất hiệu quả và đơn giản?

Bởi vì các bộ xử lý đã có các phép toán cộng và nhân hiệu quả trên phạm vi lớn vừa phải (32 hoặc 64 bit) và phép toán modulo rất hiệu quả (chỉ cần loại bỏ các bit ở trên $q$, đơn giản và hoạt động với một hằng số). Và, bởi vì đối với nhiều phép toán (bao gồm cộng và nhân), các bit bậc cao hơn không ảnh hưởng đến các bit bậc thấp hơn, đôi khi chúng ta thậm chí không phải làm điều đó - chúng ta có thể bỏ qua chúng...

0 + 0

Phan Văn Trường

Câu hỏi này là trong các ngôn ngữ khác:

EN: Straightforward modular arithmetic for power-of-two moduli

TH: เลขคณิตโมดูลาร์ที่ตรงไปตรงมาสำหรับโมดูลัสยกกำลังสอง

RO: Aritmetică modulară simplă pentru puterea a doi module

RU: Простая модульная арифметика для модулей степени двойки

VI: Số học mô-đun đơn giản cho mô-đun lũy thừa hai

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.