Tìm hạt giống cho 5 byte PRNG

Question

Một ý tưởng cũ, nhưng kể từ đó, tôi không thể tìm kiếm một số cách hợp lý để giải quyết vấn đề được nêu ra. Vì vậy, tôi "phát minh ra" (xem bên dưới) rất nhỏ gọn và theo quan điểm của tôi, PRNG hợp lý, nhưng tôi không thể tìm ra các thuật toán để xây dựng các giá trị giống phù hợp với nó ở độ sâu bit lớn. Giải pháp hiện tại của tôi chỉ đơn giản là brute-buộc, nó chạy thời gian là O (n^3).

Các máy phát điện

Ý tưởng của tôi đến từ XOR vòi (thực chất LFSRs) một số máy 8bit cũ được sử dụng để tạo ra âm thanh. Tôi đã sử dụng XOR như một cơ sở trên C64, cố gắng kết hợp các opcodes và trải nghiệm kết quả. Các giải pháp làm việc cuối cùng trông như thế này:

asl 
adC#num1 
eor #num2 

Đây là 5 byte trên 6502. Với num1 cũng lựa chọn và num2, trong accumulator nó lặp qua tất cả 256 giá trị trong một trật tự dường như ngẫu nhiên, có nghĩa là, nó trông ngẫu nhiên hợp lý khi được sử dụng để điền vào màn hình (tôi đã viết một bản demo 256b nhỏ trở lại sau đó về điều này). Có 40 cặp num1 & thích hợp cho việc này, tất cả đều mang lại chuỗi tìm kiếm phong nha.

Khái niệm có thể được khái quát hóa tốt, nếu trình bày bằng C tinh khiết, nó có thể giống như thế này (BITS là độ sâu bit của chuỗi):

r = (((r >> (BITS-1)) & 1U) + (r << 1) + num1)^num2; 
r = r & ((1U<<BITS)-1U); 

mã C Đây là lâu hơn vì nó được khái quát hóa, và ngay cả khi người ta sẽ sử dụng chiều sâu đầy đủ của một số nguyên không dấu, C sẽ không có logic mang theo cần thiết để chuyển bit cao của sự dịch chuyển sang thao tác thêm.

Để biết một số phân tích hiệu suất và so sánh, hãy xem bên dưới, sau câu hỏi.

Vấn đề/câu hỏi (s)

Vấn đề cốt lõi với các máy phát điện là tìm num1 và num2 thích hợp mà sẽ làm cho nó lặp trên toàn bộ chuỗi có thể có của một độ sâu bit nhất định. Ở phần cuối của phần này tôi đính kèm mã của tôi mà chỉ brute-lực lượng nó. Nó sẽ kết thúc trong thời gian hợp lý lên đến 12 bit, bạn có thể chờ tất cả 16 bit (có 5736 cặp có thể cho điều đó bằng cách này, được mua lại với một tìm kiếm đầy đủ qua đêm), và bạn có thể nhận được một vài 20 bit nếu bạn kiên nhẫn. Nhưng O (n^3) là thực sự khó chịu ...

(Ai sẽ nhận được để tìm ra chuỗi 32bit đầy đủ đầu tiên?)

câu hỏi thú vị khác phát sinh:

• Đối với cả hai num1 và num2 chỉ các giá trị lẻ mới có thể tạo chuỗi đầy đủ. Tại sao? Điều này có thể không khó (logic đơn giản, tôi đoán), nhưng tôi chưa bao giờ chứng minh điều đó một cách hợp lý.

• Có một thuộc tính phản chiếu dọc theo num1 (giá trị gia tăng), có nghĩa là, nếu 'a' với một 'b' num2 cho trước một chuỗi đầy đủ, thì 2 phần bổ sung 'a' (trong bit đã cho chiều sâu) với cùng một num2 cũng là một chuỗi đầy đủ. Tôi chỉ quan sát điều này xảy ra đáng tin cậy với tất cả các thế hệ tôi đã tính toán.

• Thuộc tính thú vị thứ ba là cho tất cả các cặp num1 & num2 kết quả chuỗi dường như tạo thành các vòng tròn thích hợp, ít nhất là số 0 dường như luôn là một phần của một vòng tròn.Không có tài sản này, tìm kiếm bạo lực của tôi sẽ chết trong một vòng lặp vô hạn.

• Phần thưởng: PRNG này đã được biết trước đây chưa? (và tôi chỉ tái phát minh ra nó)?

Và đây là mã tìm kiếm lực lượng của vũ phu (C):

#define BITS 16 

#include "stdio.h" 
#include "stdlib.h" 

int main(void) 
{ 
unsigned int r; 
unsigned int c; 
unsigned int num1; 
unsigned int num2; 
unsigned int mc=0U; 

num1=1U; /* Only odd add values produce useful results */ 
do{ 
    num2=1U; /* Only odd eor values produce useful results */ 
    do{ 
    r= 0U; 
    c=~0U; 
    do{ 
    r=(((r>>(BITS-1)) & 1U)+r+r+num1)^num2; 
    r&=(1U<<(BITS-1)) | ((1U<<(BITS-1))-1U); /* 32bit safe */ 
    c++; 
    }while (r); 
    if (c>=mc){ 
    mc=c; 
    printf("Count-1: %08X, Num1(adc): %08X, Num2(eor): %08X\n", c, num1, num2); 
    } 
    num2+=2U; 
    num2&=(1U<<(BITS-1)) | ((1U<<(BITS-1))-1U); 
    }while(num2!=1U); 
    num1+=2U; 
    num1&=((1U<<(BITS-1))-1U); /* Do not check complements */ 
}while(num1!=1U); 

return 0; 
} 

này, để hiển thị nó đang làm việc, sau mỗi lần lặp sẽ đưa ra các cặp tìm thấy nếu nó chiều dài chuỗi là bằng hoặc lâu hơn so với trước đó. Sửa đổi hằng số BITS cho các trình tự các độ sâu khác.

Seed săn

tôi đã làm một số vẽ đồ liên quan đến hạt. Đây là một hình ảnh đẹp thể hiện tất cả các độ dài chuỗi 9bit:

Các chấm trắng là những chuỗi dài đầy đủ, trục X là dành cho num1 (thêm), trục Y là dành cho num2 (xor), sáng hơn dấu chấm, chuỗi dài hơn. Độ sâu bit khác trông rất giống nhau trong mô hình: tất cả chúng dường như được chia thành 16 gạch chính với hai mẫu lặp lại với phản chiếu. Sự tương tự của gạch không hoàn chỉnh, ví dụ trên một đường chéo từ góc trên bên trái để phía dưới bên phải là hiển thị rõ ràng trong khi nó đối diện vắng mặt, nhưng đối với chuỗi dài đầy đủ tài sản này có vẻ đáng tin cậy.

Dựa vào này có thể giảm bớt công việc thậm chí nhiều hơn bởi các giả định trước, nhưng điều đó vẫn còn O (n^3) ...

phân tích hiệu suất

Tính đến hiện tại chuỗi dài nhất có thể được tạo ra là 24bits: trên máy tính của tôi, nó mất khoảng 5 giờ để brute-force một chuỗi 24bit đầy đủ cho việc này. Điều này vẫn chỉ là như vậy cho các bài kiểm tra PRNG thực như Diehard, do đó, bây giờ tôi thay vì đi theo một cách tiếp cận riêng.

Trước tiên, điều quan trọng là phải hiểu vai trò của trình tạo. Điều này không có nghĩa là sẽ là một máy phát điện rất tốt cho nó đơn giản, đó là mục tiêu là thay vì sản xuất số lượng phong nha blazing nhanh. Trên khu vực này không cần phải nhân/chia hoạt động, một Galois LFSR có thể tạo ra hiệu suất tương tự. Vì vậy, máy phát điện của tôi là sử dụng bất kỳ nếu nó có khả năng tốt hơn này.

Bài kiểm tra tôi đã thực hiện là tất cả các máy phát 16bit. Tôi đã chọn độ sâu này vì nó cung cấp độ dài chuỗi hữu ích trong khi các con số vẫn có thể bị chia nhỏ thành hai phần 8 bit giúp có thể trình bày các biểu đồ bit chính xác khác nhau để phân tích trực quan.

Cốt lõi của các thử nghiệm đang tìm kiếm mối tương quan giữa các số trước đó và hiện được tạo. Đối với điều này tôi sử dụng X: Y lô mà thế hệ trước là Y, hiện tại X, cả hai bị phá vỡ đến thấp/cao phần như trên đã đề cập cho hai đồ thị. Tôi đã tạo ra một chương trình có khả năng vẽ sơ đồ những bước này trong thời gian thực để cũng có thể kiểm tra gần như thế nào các con số theo nhau, làm thế nào các đồ thị lấp đầy. Ở đây rõ ràng chỉ có kết quả cuối cùng được hiển thị khi các máy phát chạy qua chu trình 2^16 hoặc 2^16-1 (Galois) đầy đủ của chúng.

Lời giải thích của các lĩnh vực:

• Những hình ảnh bao gồm các đồ thị 256x256 8x2 làm cho tổng kích thước hình ảnh 2048x512 (kiểm tra xem chúng ở kích thước gốc).

• Biểu đồ trên cùng bên trái chỉ xác nhận rằng thực sự là một chuỗi đầy đủ được vẽ, nó chỉ đơn giản là một ô X = r % 256; Y = r/256;.

• Biểu đồ dưới cùng bên trái cho thấy mọi số thứ hai chỉ vẽ theo cùng một cách như trên cùng, chỉ cần xác nhận rằng các số xuất hiện ngẫu nhiên một cách hợp lý.

• Từ biểu đồ thứ hai, hàng trên cùng là biểu đồ tương quan byte cao. Việc đầu tiên trong số họ sử dụng thế hệ trước, tiếp theo bỏ qua một số (do đó sử dụng thế hệ thứ 2 trước đó), và như vậy cho đến thế hệ thứ 7 trước.

• Từ hàng thứ hai, hàng dưới cùng là biểu đồ tương quan byte thấp, được tổ chức theo cách tương tự như trên.

Galois máy phát điện, 0xB400 tap thiết

Đây là máy phát điện được tìm thấy trong Wikipedia Galois example. Đó là hiệu suất không phải là tồi tệ nhất, nhưng nó vẫn chắc chắn không thực sự tốt.

Galois máy phát điện, 0xA55A tap thiết

Một trong những Galois đàng hoàng "hạt giống" Tôi tìm thấy. Lưu ý rằng phần thấp của các số 16bit có vẻ tốt hơn rất nhiều so với ở trên, tuy nhiên tôi không thể tìm thấy bất kỳ "hạt giống" Galois nào sẽ làm mờ byte cao.

máy phát điện của tôi, 0x7F25 (ADC), 0x00DB (EOR) hạt giống

này là tốt nhất của máy phát điện của tôi, nơi các byte cao giá trị EOR là zero. Hạn chế byte cao là hữu ích trên các máy 8bit kể từ đó tính toán này có thể được bỏ qua cho mã nhỏ hơn và thực hiện nhanh hơn nếu mất hiệu suất ngẫu nhiên là giá cả phải chăng.

máy phát điện của tôi, 0x778B (ADC), 0x4A8B (EOR) hạt giống

Đây là một trong những hạt giống chất lượng rất tốt bằng cách đo của tôi.

Để tìm hạt giống với mối tương quan tốt, tôi đã xây dựng một chương trình nhỏ mà sẽ phân tích chúng một mức độ nào, giống như cách cho Galois và mỏ. Các ví dụ "chất lượng tốt" được xác định chính xác bởi chương trình đó, và sau đó tôi đã thử nghiệm một vài trong số chúng và chọn một trong số đó.

Một số kết luận:

• Các máy phát điện Galois có vẻ là hơn cứng nhắc hơn tôi. Trên tất cả các đồ thị tương quan, các mẫu hình học xác định có thể quan sát được (một số hạt giống tạo ra các mẫu "bàn cờ", không được hiển thị ở đây) ngay cả khi nó không bao gồm các dòng. Máy phát điện của tôi cũng cho thấy các mẫu, nhưng với nhiều thế hệ chúng phát triển ít được xác định.

• Một phần kết quả của trình tạo Galois bao gồm các bit trong byte cao dường như vốn cứng nhắc mà thuộc tính dường như không có trong trình tạo của tôi. Đây là một giả định yếu nhưng có lẽ cần một số nghiên cứu thêm (để xem nếu điều này luôn luôn như vậy với máy phát điện Galois và không phải với tôi trên các kết hợp bit khác).

• Trình tạo Galois thiếu 0 (khoảng thời gian tối đa là 2^16-1).

• Hiện tại, không thể tạo một bộ hạt giống tốt cho máy phát điện của tôi trên 20 bit.

Sau đó, tôi có thể tìm chủ đề sâu hơn để thử nghiệm máy phát điện với Diehard, nhưng hiện tại việc thiếu khả năng tạo ra hạt giống đủ lớn khiến nó không thể.

Answer 1

Đây là một dạng của thanh ghi phản hồi thay đổi phi tuyến tính. Tôi không biết nếu nó đã được sử dụng như vậy, nhưng nó giống như phản hồi thay đổi tuyến tính đăng ký phần nào. Đọc trang này Wikipedia làm giới thiệu về LSFR. Chúng được sử dụng thường xuyên trong việc tạo số ngẫu nhiên giả.

Tuy nhiên, trình tạo số ngẫu nhiên giả của bạn vốn không tốt ở chỗ có mối tương quan tuyến tính giữa bit thứ tự cao nhất của số được tạo trước đó và bit thứ tự thấp nhất của một số được tạo tiếp theo. Bạn chuyển bit B cao nhất ra, và sau đó bit thứ tự thấp nhất của số mới sẽ là XOR hoặc B, bit thứ tự thấp nhất của hằng số bổ sung num1 và bit thứ tự thấp nhất của hằng số XORed num2, vì phép cộng nhị phân là tương đương độc quyền hoặc ở bit đặt hàng thấp nhất. Rất có thể PRNG của bạn có những thiếu sót tương tự khác. Tạo ra các PRNG tốt là khó.

Tuy nhiên, tôi phải thừa nhận rằng mã C64 nhỏ gọn dễ chịu!