Có cách nào để tìm $g,P$ cho kích thước chu kỳ tối đa trong BlumâMicali với $x_{i+1} = g^{x_i} \mod P $ và $x_0 = g$ không?

Đối với một số $g$ và nguyên tố $P$ trình tự $$x_{i+1} = g^{x_i} \mod P $$ $$ x_0 = g$$ có thể chứa tất cả các số từ $1$ đến $P-1$ và với điều này, nó là một hoán vị giả ngẫu nhiên của những con số đó (EDIT: dường như không phải vậy).

Có cách nào (nhanh chóng) để tìm các giá trị lớn/an toàn cho $P$ và liên quan $g$ mà vẫn có thể tạo ra mọi số từ $1$ đến $P-1$?

Vài ví dụ:

Với $P=5, g=3$ trình tự sẽ là $$\begin{split} &[3, 3^3\equiv 2, 3^{2} \equiv 4, 3^{4} \equiv 1] \mod 5 \ \equiv&[3, 2, 4, 1] \mod 5 \end{split}$$

Hoặc là $P=23, g=20$ các giá trị sẽ là: $$[20,18,2,9,5,10,8,6,16,13,14,4,12,3,19,17,7,21,15,11,22,1]$$ hoặc $P=59, g=39$

Có vẻ như không phải mọi $P$ có một giá trị như vậy $g$. Trong một số thử nghiệm chạy nhỏ $P$ thường không có nhiều hơn một phù hợp $g$.
[ 107: 94]
[ 359: 97]
[ 467: 72]
[ 587: 150,375]
[ 719: 284]

cho đến nay chỉ $P=587$ có nhiều hơn một $g$ trong lần chạy thử nghiệm của tôi. (Chỉnh sửa: Tôi chỉ kiểm tra $P=2q+1$ với $q$ một số nguyên tố, khác $P$ cũng có thể hoạt động)

câu hỏi phụ:
sẽ nhiều $g$ được phổ biến hơn cho lớn hơn $P$?
Hoặc sẽ lớn hơn $P$ có xu hướng không có $g$ ở tất cả?

câu hỏi chính:
Có cách nào (nhanh chóng) để tìm các giá trị lớn/an toàn cho $P$ và một liên quan $g$ ?

Tôi e rằng tôi có thể đưa ra rất ít cách chứng minh, nhưng tôi có một số quan sát và kinh nghiệm.

Thứ nhất, bản đồ sẽ chỉ là một hoán vị nếu $g$ là một gốc modulo nguyên thủy $P$. Chúng tôi lưu ý rằng có $\phi(P-1)$ căn nguyên thủy và các số nguyên tố có nhiều căn nguyên thủy sẽ có nhiều hơn $g$ mà hoán vị có thể là một chu kỳ đầy đủ. Các số nguyên tố có tỉ lệ nghiệm nguyên thủy lớn nhất có dạng $P=2q+1$ ở đâu $q$ cũng là nguyên tố. Lưu ý rằng tất cả các ví dụ của bạn đều thuộc dạng này.

Tiếp theo, chúng tôi lưu ý rằng không phải tất cả các hoán vị đều có thể xảy ra vì chúng tôi sẽ luôn có chuỗi $P-1\mapsto 1\mapsto g$. Chỉ một tỷ lệ $1/(P-1)(P-2)$ hoán vị sẽ có thuộc tính này và chỉ $1/(P-2)(P-3)$ chu kỳ đầy đủ sẽ có thuộc tính này. Chúng tôi cũng lưu ý rằng các giá trị chẵn luôn ánh xạ tới dư lượng bậc hai và các giá trị lẻ luôn ánh xạ tới các giá trị không dư lượng bậc hai (với các hạn chế hơn nữa đối với các bội số/lũy thừa khác chia $P-1$). Đây là một hạn chế mạnh mẽ hơn mà chỉ một tỷ lệ $1/\binom{P-1}{(P-1)/2}$ của các hoán vị có thuộc tính này. Tôi không rõ ngay tỷ lệ các chu kỳ đầy đủ sẽ đáp ứng hạn chế của anh ấy.

TRONG TIẾN TRÌNH