Điểm:0

Ánh xạ số thành số với entropy thuật toán lớn - cách thực hiện?

lá cờ tf
Tom

Tôi cần tham số hóa một số PRNG, giả sử tôi cần số 32 bit. Nhưng khi các con số trông không ngẫu nhiên lắm, nó sẽ cho kết quả xấu. Những người tạo ra SplitMix cũng gặp vấn đề tương tự (lưu ý rằng theo những gì tôi hiểu thì họ đã không giải quyết đúng):

https://www.pcg-random.org/posts/bugs-in-splitmix.html

Vì vậy, tôi cần một hàm sẽ biến đổi giả sử số 1 thành thứ gì đó như 10011110001101110111100110111001. Nhưng số 10100111101101010110001111100101 với độ phức tạp thuật toán tốt (ý tôi là độ phức tạp Kolmogorov) có thể vẫn tốt tương tự (tất nhiên không nhất thiết phải giống nhau).

Vì vậy, băm bằng cách nhân: x = x*2654435769 mod 2^32 không phải là tùy chọn, bởi vì chúng ta có thể tìm nghịch đảo phép nhân mô-đun, điều này sẽ cho chúng ta 1 hoặc một giá trị nào đó xấu. Tôi đã cố gắng sử dụng bộ trộn bit từ PCG:

uint32_t RXSMXS(uint32_t rxs)
{
    uint8_t r;

    r = rxs >> 28;
    rxs = rxs^(rxs>>(4+r));
    rxs = rxs*277803737;
    trả về rxs^(rxs >> 22);
}

Nhưng có vẻ như nó cũng có thể đảo ngược 1 đến 1 (vấn đề là sự phân biệt, không phải bản thân khả năng đảo ngược). Cùng tiếng thì thầm32:

uint32_t rì rầm32(uint32_t z)
{
z ^= (z >> 16);
z *= 0x85ebca6bul;
z ^= (z >> 13);
z *= 0xc2b2ae35ul;
trả về z^(z>>16);
}

Nó có thể đảo ngược và song phản lực, phải không (vì vậy chúng ta có thể tìm thấy đầu vào mang lại cho chúng ta đầu ra tệ như chúng ta muốn)?

Vì vậy, có một phương pháp nổi tiếng, hiệu quả để làm điều đó? Ý tôi là - lấy một số có độ phức tạp Kolmogorov thấp (hoặc cao) và xuất ra một số có độ phức tạp Kolmogorov cao. Tất nhiên, một chức năng/ánh xạ như vậy sẽ không phải là từ chối, bởi vì chúng tôi chỉ loại bỏ một số giá trị. Vì vậy, các khóa/hệ số khác nhau đôi khi sẽ tạo ra kết quả giống nhau.

Ý tưởng của tôi là xác định một nửa số là hằng số, ví dụ: đặt các bit quan trọng nhất là: 10011110001101110000000000000000 và sau đó chỉ cần chọn ngẫu nhiên các bit ít quan trọng nhất (sau đó có thể là mọi số 16 bit). Và sau đó đặt nó vào bộ trộn bit như thì thầm32 hoặc cái gì khác. Nhưng chúng tôi vẫn không đảm bảo rằng tiếng rì rầm32 sẽ không biến đổi, ví dụ 10011110001101110000000000000011 thành 1, 2 hoặc 3. Vì vậy, có thể tôi sẽ không sử dụng bộ trộn (nhưng những con số như vậy có thể có entropy thuật toán sai ở các bit ít quan trọng nhất).

Bạn có bất kỳ ý tưởng tốt hơn nhưng hiệu quả?

Điểm:1
lá cờ in

Có vẻ như bạn chỉ đang yêu cầu một hàm băm an toàn.

Bạn nói rõ ràng rằng bạn muốn tính toán dễ dàng theo một hướng và khó tính ngược lại. Cái mà chúng ta thường gọi là khả năng chống ảnh hưởng trước yêu cầu này. Thật khó để tìm thấy $x$ để có thể $f(x)=y$.

Tất nhiên, nếu giá trị ban đầu được chọn từ một nhóm nhỏ (entropy thấp), chúng ta vẫn có thể tìm thấy nó thông qua tìm kiếm toàn diện.

Lưu ý số 1 không phải là entropy thấp. Entropy dựa trên các phân phối hoặc tập hợp các giá trị, không phải các số đơn lẻ.

Tom avatar
lá cờ tf
Tom
Tôi nghĩ nhiều hơn về độ phức tạp Kolmogorov của số nhị phân còn được gọi là entropy thuật toán hoặc độ phức tạp thuật toán. Tôi không chắc liệu nó có giống với hàm entropy nhị phân hay không (tôi không thích toán lắm). Và nó không cần phải an toàn. Tôi đã viết về suy nghĩ đảo ngược về phép loại bỏ, ý tôi là quay lại đầu vào, bằng cách sử dụng một số. Tôi sẽ thay đổi một chút trong câu hỏi của tôi.

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