Mỗi nhận xét sửa đổi câu hỏi ban đầu: OP phỏng đoán rằng 100 chữ số $y_n$ Trong $\{0,1,2,3,4,5\}$ sở hữu của họ có được bằng cách sử dụng biểu thức C(++) tương đương với rand()%6 với rand() sử dụng PRNG (không mã hóa) dựa trên Trình tạo đồng dư tuyến tính, với mã tương đương với
tĩnh không dấu dài x;
int rand(void) {
x = 214013*x+2531011; // hay là 22695477*x+1
return (int)((x>>16)&0x7FFF);
}
Thông báo rằng $x$ ít nhất là 32 bit, nhưng chỉ có 31 bit bậc thấp mới quan trọng do (x>>16)&0x7FFF và C biểu diễn không dấu dài phép nhân với việc cắt bớt các bit bậc cao không phù hợp với biến.
Trừu tượng hóa các chi tiết lập trình, phỏng đoán là $x$ phát triển mỗi $x_{n+1}:=a\cdot x_n+b\bmod m$ với $m=2^{31}$ và $(a,b)$ đối với một số hằng số cố định được cho là một trong hai $(214013,2531011)$ hoặc $(22695477,1)$. Và rand() đầu ra bit 30â¦16 của $x$ do đó $y_n:=\lfloor x_n/2^{16}\rfloor\bmod 6$ được trao cho $n=0$ đến $99$ (với hạt giống là một số nguyên chưa biết $x_{-1}$ trong một số phạm vi phi vật chất, vì chỉ $x_{-1}\bmod m$ sẽ quan trọng; và tốt hơn hết là chúng ta nên cố gắng tìm $x_0$ dù sao).
OP hỏi liệu có thể xác nhận hoặc xác nhận phỏng đoán đó không và (nếu đúng) tìm $(a,b)$ được sử dụng và dự đoán những gì tiếp theo trong trình tự.
Đúng, điều đó là có thể, với sự tự tin tuyệt vời. Trạng thái hiệu quả của các PRNG được xem xét có 31 bit, chỉ có hai PRNG được xem xét, chúng có thể sử dụng được cho mục đích mô phỏng, do đó chúng ta có thể tìm thấy trạng thái của chúng và trạng thái nào được sử dụng nhiều hơn một chút $31+1=32$ chút thông tin; và chúng tôi nhận được $100\cdot\log_2(6)\approx258,5$ bit, sẽ cung cấp nhiều xác nhận.
Đơn giản nhất là thử cho cả hai phỏng đoán $(a,b)$, và khám phá các giá trị có thể có của $x_0$. Chúng là duy nhất $2^{31}$, biết $y_0$ cho phép giảm một cách có hệ thống theo hệ số $6$. Mỗi người theo dõi $y_i$ tiếp tục loại bỏ $5$ ứng cử viên ra khỏi $6$. Nếu không có ứng cử viên sống sót qua tất cả các $y_i$, giả thuyết bị bác bỏ. Nếu một trận đấu được tìm thấy, chúng tôi biết đó $(a,b)$ chúng tôi đã sử dụng và có thể tính toán bổ sung $y_i$. Việc triển khai thành thạo bằng ngôn ngữ được biên dịch sẽ mất như một giây trên PC để bàn hiện đại.
Nhưng có lẽ muốn phá vỡ mọi thứ trong thời gian thực với CPU \$0,5 hiện đại chạy từ pin \$0,2 hoặc bị kẹt vào một máy tính lập trình của những năm 1970, hoặc là ENIAC. nhận xét rằng $6$ là số chẵn và số chia là $2^{16}$. Nó theo sau $y_n\bmod 2$ là một chút $16$ của $x_n$. Cũng nhận xét rằng kể từ khi $m$ là một sức mạnh của hai, sự thay đổi của một chút trong $x_n$ không lan truyền đến các bit bậc thấp hơn của $x_{n+1}$. Nếu theo bit 16 của $x_n$ chỉ phụ thuộc vào 17 bit thấp của $x_0$. Chúng tôi biết bit 16 của $x_0$, do đó cần kiểm tra nhiều nhất $2^{16}$ ứng cử viên cho các bit 15â¦0 của $x_0$. Sau đó chúng ta có thể tìm thấy 14 bit khác như trên. Điều đó phân chia và chinh phục cách tiếp cận sẽ cho phép giải quyết các tham số lớn hơn nhiều, ví dụ: Biến đổi x loại uin64_t và trả về x>>33, trên một CPU hiện đại.
Tôi tự hỏi chúng ta có thể làm gì nếu $a$, $b$ và/hoặc $m$ không rõ.
Ghi chú ở trên:
- Nó sử dụng quy ước thống trị trong khoa học máy tính (và mật mã với một vài ngoại lệ như DES): bit được tính từ 0 (bit bậc thấp), do đó nếu một số nguyên không âm $v$ được biểu diễn ở dạng nhị phân như $k$ chút ít $b_j$, sau đó $v=\sum b_j$ với $0\le j<k$. Trong quy ước big-endian, bit 0 được viết ở bên phải: $6\times7=42$ trong số thập phân là $110\times111=101010$ ở dạng nhị phân.
- biến máy tính
x ít nhất là 32 bit, nhưng chỉ có vấn đề 31 bit thứ tự thấp (0 đến 30) và được sử dụng trong $x_n$, do đó $0\le x_n<m=2^{31}$. đầu ra của rand() ít nhất là 16 bit, nhưng chỉ có 15 bit thứ tự thấp (0 đến 14) và tất cả các bit khác đều bằng 0, do đó $0\le$rand()$\le$RAND_MAX$=2^{15}-1$. Nếu $0\le i<15$ sau đó cắn $j$ đầu ra của rand() phù hợp với bit $j+16$ của x. Nó đi sau bit 0 của $y_n$ phù hợp với bit 16 của $x_n$.
Nhận xét (ngoài chủ đề) về mã hiện tại:
- Nó cố gắng sử dụng khả năng tăng tốc được thực hiện bởi
6 bằng nhau. Tôi duy trì đây là không phải cần thiết để đạt được thời gian thực hiện tính bằng giây, nếu
- chúng tôi khám phá các giá trị có thể có của $x_0$, chứ không phải là hạt giống nhiều bước trước đó.
- chúng tôi sử dụng nó $x_0$ là 31 bit, do đó chúng tôi có thể hạn chế tìm kiếm bên ngoài thành [
0, 0x7ffffffff] đó là $2^{31}$ ứng viên $x_0$.
- chúng tôi sử dụng mà chúng tôi biết $y_0$, do đó mà $x_0=2^{16}\cdot(6\cdot u+ y_0)+v$ vì $0\le u<\lceil2^{15}/6\rceil$ và $0\le v<2^{16}$, giới hạn trong khoảng $2^{31}/6$ ứng cử viên cho $x_0$.
- chúng tôi tối ưu hóa bài kiểm tra để kiểm tra ứng viên $x_0$ chống lại $y_1$ trong vòng lặp bên trong trên $v$.
- Bản chất của không bắt buộc ghi chú tăng tốc
6 chẵn là trước tiên tìm các bit 16â¦0 của $x_0$ phù hợp với các giá trị $y_0$ được thu thập, sau đó là các bit 30–¦17. Mã không làm điều đó! Với tốc độ tăng tốc đó, thời gian thực hiện sẽ giảm xuống còn một phần nghìn giây.
- Chúng ta cần các giá trị đầy đủ của $y_n$ được thu thập (trong cả tìm kiếm không được tối ưu hóa và phần thứ hai của tìm kiếm được tối ưu hóa), nhưng chúng dường như không có sẵn trong đầu vào, mà tôi đoán là $y_n\bmod2$. Hơn nữa, tôi không hiểu tại sao đó là mảng hai chiều
KẾT QUẢ[3][7].
- Khi nào $x_0$ được tìm thấy, nếu cần tìm hạt giống (hay đúng hơn là bit 30–¦0 của số đó) một số bước đã biết trước đó, điều đó có thể được thực hiện hiệu quả bằng cách quay lại LCG bằng cách sử dụng $x_{n-1}:=a^{-1}\,(x_n-b)\bmod m$ ở đâu $a^{-1}$ là nghịch đảo mô-đun của $a$ modulo $m$.
Đây là mã làm việc không có tăng tốc tùy chọn (do đó có khả năng hoạt động với mô đun giảm cuối cùng lẻ $r$ câu hỏi có ở đâu 6). Hãy thử nó trực tuyến!
#include <stdint.h>
#include <stdio.h>
#include <inttypes.h>
#define A 214013 // cho VC; 22695477 cho BC
#define B 2531011 // cho VC; 1 cho trước công nguyên
#define R 6 // mô đun, trong [2, 32768]
// static_assert(A > 0 && A % 8 == 5, "A mod 8 phai la 5");
// static_assert(B > 0 && B % 2 == 1, "B mod 2 phai la 1");
// static_assert(R >= 2 && R <= 32768, "R must be in [2, 32768]");
// quyết định modulo, giảm khi R là lũy thừa của hai
#define M ((uint32_t)(((R-1)&R)!=0 ? 0x8000 : R)<<16)
// Chuỗi yn cho VC (a=214013, b=2531011), n=6, seed=1639326023
// Nếu R là lũy thừa của hai, ceil(16/log2(R))+1 mục là đủ
// Mặt khác, đó là các mục ceil(31/log2(R)), do đó 12 cho R=6.
const int16_t y[] = {
0,5,3,0,4,3,1,0,4,5,4,4,4,5,5,3,0,2,0,5,4,5,0, // 0, 2,5,1,3,5,5,5,
};
// nghịch đảo mô-đun INVA của A modulo M
#define INVA (IN_A(IN_A(IN_A(IN_A((uint32_t)A))))&(M-1))
#define IN_A(v) (v*(2-v*A))
int main(void) {
// quyết định bắt đầu từ x0 sao cho khớp với y0
const uint32_t y0 = y[0], y1 = y[1];
int32_t x0 = (int32_t)(((M >> 16) - y0) / R * R + y0) << 16 | 0xffff;
uint32_t tìm thấy = 0;
printf("trình tạo: ((int)((x = %" PRIu32 " * x + %" PRIu32 ") >> 16) & 0x7fff) %% %u\n",
(uint32_t)A, (uint32_t)B, (không dấu)R);
trong khi (x0 >= 0) {
uint32_t x1 = A * (uint32_t)x0 + B;
làm {
// khẳng định( (x0 >> 16) % R == y0);
// khẳng định( x1 == A * (uint32_t)x0 + B);
if (((x1 >> 16) & 0x7fff) % R == y1) {
uint32_t x = x1;
số nguyên;
for (n = 2; n < sizeof(y) / sizeof(*y); ++n)
if ((((x = A * x + B) >> 16) & 0x7fff) % R != y[n])
goto nxt;
//đã tìm ra giải pháp
x = (INVA * ((uint32_t)x0 - B)) & (M - 1);
printf("x0 co the la %" PRId32 ", that la seed=%" PRIu32
" modulo 0x%" PRIx32 ", mang lại:\n", x0, x, M);
// chứng minh luận điểm bằng cách hiển thị đầu ra
cho (n = 0; n < sizeof(y) / sizeof(*y) + 8; ++n)
printf(" %d", ((int)((x = A * x + B) >> 16) & 0x7fff) % R);
printf("\n");
++tìm thấy;
}
nxt: x1 -= (uint32_t)A;
} while (((x0--) & 0xffff) != 0);
x0 -= (int32_t)(R - 1) << 16;
}
printf("đã tìm thấy %" PRIu32 " giải pháp%s\n", đã tìm thấy, đã tìm thấy > 1 ? "s" : "");
trả về 0;
}
// năng suất:
// trình tạo: ((int)((x = 214013 * x + 2531011) >> 16) & 0x7fff) % 6
// x0 có thể là 531633902, tức là seed=1639326023 modulo 0x80000000, mang lại:
// 2 3 4 1 5 1 1 5 4 0 3 2 2 5 5 3 5 5 3 4 0 1 1 4 1 3 3 2 5 4 4
// tìm được 1 lời giải
