บรรจวบ เข้าสู่ระบบ
Score:1
kira avatar Crypto

ค้นหาคนสำคัญ $p$ ที่เสี่ยงต่อโปห์ลิก-เฮลแมน

ธง kg
kira

ต้องหาเบอร์เด็ดๆ $p$ โดยมีข้อจำกัดดังนี้

  • $p$ เป็นอย่างน้อย $1000$ บิตยาว
  • $p-1$ เป็นจำนวนที่ราบเรียบโดยมีตัวประกอบที่ใหญ่ที่สุดอยู่ด้านล่าง $1000$
  • ปัจจัยใดๆ ของ $p-1$ สามารถแสดงได้หลายครั้ง

เบอร์นี้มีอยู่จริงไหม? และถ้าใช่ มีอัลกอริทึมในการค้นหาหรือไม่?

44
0 + 0
fgrieu avatar
ng flag
fgrieu
ยินดีต้อนรับสู่ crypto-SEสิ่งนี้ดูเหมือนการบ้าน ดังนั้นฉันจะให้คำใบ้ (อย่างรัดกุม) เท่านั้น: เสนออัลกอริทึมง่ายๆ ที่สร้าง $r$ ที่สุ่มเมล็ดโดยมีลักษณะเฉพาะที่ขอ $p-1$ (รวมถึงขนาด) โดยไม่สนใจข้อกำหนดในตอนนี้ว่า $p$ เป็นจำนวนเฉพาะ; จากนั้นหาค่าโดยใช้ [ทฤษฎีบทจำนวนเฉพาะ](https://en.wikipedia.org/wiki/Prime_number_theorem) ซึ่งเป็นขอบเขตล่างที่เป็นไปได้สำหรับความน่าจะเป็นที่ $p=r+1$ เป็นจำนวนเฉพาะ และจากขอบเขตสูงกว่าที่เป็นไปได้คร่าวๆ ของต้นทุนที่คาดไว้ของอัลกอริธึมความน่าจะเป็นที่ชัดเจนในขณะนี้ เป็นการฉลาดที่จะตอบคำถามของคุณเอง
2
ตอบกลับ
ธงชาติไทย
Kulap
คำถามนี้เป็นภาษาอื่นๆ:

โพสต์คำตอบ

คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา