Nghịch đảo của phép toán $(a,b) \mapsto a \oplus b\oplus ((a \land b) \ll 1)$ với độ dài bit cố định

Dominic van der Zypen

12:38, 15/07/2023

Lý lịch. trong họ giấy về sơ đồ mật mã NORX, các tác giả sử dụng phép tính xấp xỉ nhanh + bằng thao tác bitwise (mất ít chu kỳ CPU hơn so với phép cộng thích hợp) bằng cách sử dụng công thức $$a+b \; \xấp xỉ \; a \oplus b \oplus ((a \land b) \ll 1)$$ ở đâu $\oplus$ là bitwise XOR và $\land$ là bit AND, và $\ll$ dịch trái 1 vị trí. (Mục đích của $((a \land b) \ll 1)$ là để mô phỏng hoạt động "carry-bit".)

Xây dựng câu hỏi. Có thể xem đây là một hoạt động $+^{n}_\sim : \{0,1\}^n\times \{0,1\}^n \to \{0,1\}^n$, Được định nghĩa bởi $(a, b) \mapsto a \oplus b \oplus ((a \land b) \ll 1)$. Vì $b\in \{0,1\}^n$ chúng tôi nhận được một bản đồ $s^n_b: \{0,1\}^n\to \{0,1\}^n$ Được định nghĩa bởi $$a \mapsto a +^{n}_\sim b.$$

Là $s^n_b$ tiêm (và do đó tính từ) cho tất cả $n\in\mathbb{N}$ và $b\in \{0,1\}^n$?

0 + 0

kelalaka

12:42, 15/07/2023

Đó là một nửa cộng. Để sử dụng nó cho n-bit, bạn cần Full-adder để truyền bá.

Hồi đáp

poncho

12:49, 15/07/2023

Đây có phải là một câu hỏi bài tập về nhà?

Hồi đáp

kelalaka

17:56, 15/07/2023

Trên thực tế, $s_b^n$ không được xác định rõ. Điều gì xảy ra với lần mang cuối cùng?

Hồi đáp

Điểm:2

Crypto

Daniel S

13:47, 15/07/2023

Vâng, để xem ghi chú này $a$ có thể được tính theo bit từ bit có ý nghĩa nhỏ nhất. Chúng tôi viết $c$ vì $a+^n_\sim b$ và $x_i$ cho $i$chút của $x$. Quan sát rằng: $$a_0=b_0\oplus c_0$$ $$a_i=b_i\oplus c_i\oplus (a_{i-1}\wedge b_{i-1})$$ vì $1\le i\le n-1$.

Đáng buồn thay, không có chức năng nghịch đảo bit 4 bit đến 1 bit đẹp $(b,c)\mapsto a$ ví dụ. $a_2$ là một chức năng của $b_0$, $b_1$, $b_2$, $c_0$ và $c_1$.

0 + 0

Phan Văn Trường

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

EN: Inverses of the operation $(a,b) \mapsto a \oplus b\oplus ((a \land b) \ll 1)$ for fixed bit length

TH: ผกผันของการดำเนินการ $(a,b) \mapsto a \oplus b\oplus ((a \land b) \ll 1)$ สำหรับความยาวบิตคงที่

RO: Inversurile operației $(a,b) \mapsto a \oplus b\oplus ((a \land b) \ll 1)$ pentru lungime fixă de biți

RU: Обратные операции $(a,b) \mapsto a \oplus b\oplus ((a \land b) \ll 1)$ для фиксированной битовой длины

VI: Nghịch đảo của phép toán $(a,b) \mapsto a \oplus b\oplus ((a \land b) \ll 1)$ với độ dài bit cố định

Đă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.