Điểm:1

Tìm $p$ nguyên tố dễ bị tấn công bởi pohlig-Hellman

lá cờ kg

Tôi cần tìm một số nguyên tố $p$ với các ràng buộc sau:

  • $p$ là ít nhất $1000$ bit dài
  • $p-1$ là số trơn có ước lớn nhất dưới đây $1000$
  • bất kỳ yếu tố nào của $p-1$ có thể có mặt nhiều lần

Con số này có tồn tại không? và nếu có, có thuật toán nào để tìm ra nó không?

fgrieu avatar
lá cờ ng
Chào mừng đến với tiền điện tử-SE.Điều này giống như bài tập về nhà, vì vậy tôi sẽ chỉ đưa ra một gợi ý (mạnh mẽ): đề xuất một thuật toán đơn giản xây dựng $r$ được chọn ngẫu nhiên với các đặc điểm được yêu cầu cho $p-1$ (bao gồm cả kích thước), hiện tại bỏ qua yêu cầu đó $p$ là số nguyên tố; sau đó suy ra bằng cách sử dụng [Định lý số nguyên tố](https://en.wikipedia.org/wiki/Prime_number_theorem) giới hạn dưới hợp lý cho xác suất $p=r+1$ là số nguyên tố và từ đó giới hạn trên hợp lý thô về chi phí dự kiến ​​của thuật toán xác suất rõ ràng hiện nay. Thật thông minh khi trả lời câu hỏi của riêng bạn.

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