Cho (ví dụ) các số nguyên tố khác nhau $p,q$ với $2 p+1$, và $4 p+3$ số nguyên tố cũng vậy (tương tự cho $q$).
Để cho
$$N = (4 p+3)\cdot (4 q+3)$$
Với trình tự này
$$s_{i+1} = s_i^4 \mod N$$
sẽ có $p\cdot q$ yếu tố (trong hầu hết các trường hợp) cho $s_0 = r^4 \mod N$ cho hầu hết các giá trị ngẫu nhiên $r$.
Tùy theo lựa chọn $r$ liên quan $s_0 = r^4 \mod N$ sẽ (hầu như luôn luôn) là thành viên của 1 trong 4 chuỗi độ dài khác nhau $p \cdot q$.
Câu hỏi:
$\text{ }\mathrm{ I }.$ Có một cách dễ dàng để kiểm tra nếu một ngẫu nhiên $r$ dẫn đến một thành viên của chuỗi $S_1,S_2,S_3,S_4$?
$\mathrm{II}.$ Hoặc chúng ta có thể sản xuất ngẫu nhiên $r'$ đó là tất cả các thành viên của cùng một chuỗi?
(Cả hai đều không bị rò rỉ thông tin bí mật. Các thông tin liên quan $s_0$ hoặc khác $f(r)$ cũng có thể được so sánh)
(Giảm nó xuống dưới 4 chuỗi có cùng kích thước cũng sẽ hữu ích.)
Thêm chi tiết: Nếu chúng ta làm $\mathrm{II}.$ chúng tôi cũng cần phải đảm bảo các liên quan $s_0$ không tuân theo một trật tự đã biết. Ví dụ. nếu chúng ta sản xuất $r'$ với một thành viên chuỗi được chọn cố định $s_m$ và $r' = s_m^{4^r} \mod N$ chúng tôi luôn biết vị trí chính xác liên quan đến $s_m$ Cho mọi $r$ $\mapsto s_{m+r+1}$.
trường hợp đặc biệt: Đối với một số $r$ trình tự sẽ chỉ có $p,q$ hoặc $1$ thành phần. Chúng tôi bỏ qua chúng ở đây. Để tránh điều đó chúng ta cần chọn $r$ với
$$r\in[2,N-1] $$
$$r\mod (4 p+3)\not=0 $$
$$ r\mod (4 q+3)\not=0 $$
$$ r \not\in\{r_*^{2p+1} \mod N \}\land r \not\in\{r_*^{2q+1} \mod N \}$$
Các đối thủ cũng sẽ có thể tạo các thành viên ngẫu nhiên đó tại máy của anh ấy. Cho 2 ngẫu nhiên $r$ anh ta không nên biết khoảng cách chỉ số giữa các liên quan của họ $s_0$ giữa các chuỗi mục tiêu. Nếu anh ta bằng cách nào đó biết điều đó trong 2 lần ngẫu nhiên $r$ anh ta sẽ không thể dễ dàng tính toán nó cho lần thứ 3 ngẫu nhiên $r$ (trong hầu hết các trường hợp). số mũ $\alpha = 4$ có thể được thay thế bằng một giá trị tương đương khó tính toán.
Ví dụ: $N= 7849=47 \cdot 167$ sẽ sản xuất $4$ dãy có độ dài $451 = 11 \cdot 41$
(cộng với các trường hợp đặc biệt về độ dài $11,41,1$)
