Điểm:0

Số khóa không tự nguyện trong mật mã hoán vị

lá cờ au

Tôi đã gặp vấn đề sau từ Lý thuyết và thực hành cuốn sách của Stinson-Paterson. Nó nói như sau:

2.17

(a) Chứng minh rằng một hoán vị $\pi$ trong Mật mã hoán vị là một kei iff không tự nguyện (nếu và chỉ nếu) $\pi(i) = j$ ngụ ý $\pi(j) = > i$, cho tất cả $i,j \in \{1,...,m \}$.

(b) Xác định số lượng khóa không liên quan trong Hoán vị mật mã$m = 2,3,4,5, $ và 6.

Tôi đã chứng minh mục đầu tiên, chỉ ra rằng các chỉ số của $x's$$y's$ giữ nguyên, tuy nhiên tôi không có bất kỳ gợi ý nào để xác định mục thứ hai b, đây là, tôi không chắc về vai trò của khóa trong loại mật mã này; bất kỳ làm rõ, thực sự một câu trả lời rõ ràng sẽ là tốt.

kelalaka avatar
lá cờ in
2, 4, 10, 26, 76, xem http://oeis.org/A000085 , cái đầu tiên; bản sắc và thập tự giá, bạn cần phải thử...
João Víctor Melo avatar
lá cờ au
Thật vậy, tôi muốn một câu trả lời hoàn toàn rõ ràng, nếu không thì nó chẳng có ý nghĩa gì.
kelalaka avatar
lá cờ in
Thật vậy, nó có ý nghĩa. Bạn có muốn chúng tôi đếm tất cả 76 cho bạn? đây là cái thứ ba; danh tính, phần tử đầu tiên cố định phần tử kia được hoán đổi, phần tử thứ hai cố định phần tử kia được hoán đổi và phần tử thứ ba được cố định và các phần tử khác được hoán đổi. Xác định đòi hỏi bàn tay và quan sát, tìm ra công thức là khó khăn. Xem https://mathworld.wolfram.com/PermutationInvolution.html
Điểm:1
lá cờ in

Các phép quay tương ứng một đối một với các hoán vị tự liên hợp (nghĩa là các hoán vị là hoán vị nghịch đảo của chính chúng)

Bộ truyện được đưa ra trong bạn ơi A000085.

Các công thức cho số lượng các hoán vị involution trên $n$ chữ cái là;

$$I(n) = 1 + \sum_{k=0}^{\lfloor (n-1)/2 \rfloor} \frac{1}{(k+1)!} \prod_{i=0} ^k \binom{n-2i}{2}$$

Một chút tính toán tay

Trước hết, hoán vị danh tính $\varepsilon$ luôn là một phép lùi. Ở đây chúng ta sẽ sử dụng ký hiệu một dòng.

  • $m =2 $ sau đó $\varepsilon = (1,2)$$(2,1)$ là các phép quay.

  • $m =3 $ sau đó $\varepsilon = (1,2,3)$, $(1,3,2)$,$(3,2,1)$, và $(2,1,3)$ là 4 có thể.

  • $m =4 $ sau đó $\varepsilon = (1,2,3,4)$

    • sửa trước $(1,a,b,c)$ thì chúng ta có 3, theo trường hợp trước; $(1,2,4,3),(1,4,3,2),(1,3,2,4)$
    • sửa lỗi thứ hai $(a,2,c,d)$ thì ta có 2, $(3,2,1,4),(4,2,3,1)$ (một tồn tại trong trường hợp trước)
    • sửa thứ ba $(a,b,3,d)$ thì ta có 1, $(2,1,3,4)$
    • sửa chữa thứ tư $(a,b,c,4)$ thì ta có 0; tất cả đều tồn tại trước đó.
    • cố định gấp đôi sau đó $(4,2,3,1)$
    • nhân đôi $(3, 4, 1, 2),(2,1,4,3)$

Một mã Sagemath cho 5

p = Hoán vị([1, 2,3,4,5])
cho tôi trong phạm vi (0, giai thừa (5)):
    nếu p == p.inverse():
        in(p)
    p = p.tiếp theo()

với đầu ra

[1, 2, 3, 4, 5]
[1, 2, 3, 5, 4]
[1, 2, 4, 3, 5]
[1, 2, 5, 4, 3]
[1, 3, 2, 4, 5]
[1, 3, 2, 5, 4]
[1, 4, 3, 2, 5]
[1, 4, 5, 2, 3]
[1, 5, 3, 4, 2]
[1, 5, 4, 3, 2]
[2, 1, 3, 4, 5]
[2, 1, 3, 5, 4]
[2, 1, 4, 3, 5]
[2, 1, 5, 4, 3]
[3, 2, 1, 4, 5]
[3, 2, 1, 5, 4]
[3, 4, 1, 2, 5]
[3, 5, 1, 4, 2]
[4, 2, 3, 1, 5]
[4, 2, 5, 1, 3]
[4, 3, 2, 1, 5]
[4, 5, 3, 1, 2]
[5, 2, 3, 4, 1]
[5, 2, 4, 3, 1]
[5, 3, 2, 4, 1]
[5, 4, 3, 2, 1]
kelalaka avatar
lá cờ in
Như chúng ta có thể thấy, việc xác định không nhất thiết có nghĩa là sử dụng các phép tính tay. Sử dụng máy tính chúng ta cũng có thể xá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.