ภายใต้เงื่อนไขใดที่เซมิไพรม์ขนาดใหญ่สามารถแยกตัวประกอบได้ โดยเฉพาะอย่างยิ่ง เซมิไพรม์ 400 หลักต่อไปนี้ไม่สำคัญพอที่จะแยกตัวประกอบเป็นจำนวนเฉพาะหรือไม่
6962155154859963260211100482357357666900094513013513488352858667799199787495340476167566639530574848375895722792291996203873323650274512138128403360943634134259376986501375967452208380337012919869885380406071772232795575963202558402893589313281327208179913789760736615950818685956393838601277519011418885197723428318400763080858914698836058070301404903262955501113318317950597435778777212408626799143
"เล็กน้อย" เกือบจะเป็นคำที่ไม่ถูกต้องสำหรับเรื่องนี้ คำถามที่ดีกว่าคือ การพิจารณาปัจจัยอย่างสมเหตุสมผลนั้นสมเหตุสมผลหรือไม่ ประการแรก มีมูลค่าการกล่าวขวัญว่ากึ่งไพรม์ของคุณคือ 400 ทศนิยม ตัวเลข คูณสิ่งนี้ด้วย $\log_2(10)$เราเห็นว่ามันเป็น $\ประมาณ1300$ บิตยาว ซึ่งมีขนาดใหญ่กว่าการบันทึกแฟคตอริ่ง (ของเซมิไพรม์) ที่ใหญ่ที่สุดอย่างมากมาย 829 บิต. ดังนั้น คำตอบคือ "ไม่" เว้นแต่ว่าเซมิไพรม์ของคุณจะมีโครงสร้างพิเศษที่ทำให้ "อ่อนแอ"
เซมิไพรม์มีโครงสร้างพิเศษอะไรบ้าง อนุญาต $N = p_1p_2$ เป็นตัวประกอบ มีผู้สมัครไม่กี่คนที่ทำงานถ้า
หนึ่งใน $p_i$ เป็น เล็ก (พูดอย่างมากที่สุด $\ประมาณ 60$ บิต) จากนั้น วิธีเส้นโค้งวงรี สมเหตุสมผลที่จะวิ่ง
หนึ่งใน $p_i$ เป็นเช่นนั้น $p_i+1$ เป็น เรียบ, เช่น. ปัจจัยสำคัญทั้งหมดของ $p_i+1$ ถูกจำกัดด้วยจำนวนที่น้อยพอสมควร $B$. แล้ว วิลเลียมส์ $p+1$ อัลกอริทึมมีความสมเหตุสมผล.
หนึ่งใน $p_i$ เป็นเช่นนั้น $p_i-1$ เป็น พาวเวอร์สมูท, เช่น. นายกรัฐมนตรีทั้งหมด พลัง ปัจจัยของ $p_i-1$ ถูกจำกัดด้วยจำนวนที่น้อยพอสมควร $B$. แล้ว พอลลาร์ด $p-1$ อัลกอริทึม มีความสมเหตุสมผล
อาจมี "โครงสร้างพิเศษ" อื่น ๆ อีกสองสามอย่างที่ฉันขาดหายไป (ฉันดูเหมือนจะจำได้ถ้า $p_1\ประมาณ p_2$แต่ตอนนี้จำชื่อไม่ได้) โอกาสที่แท้จริงเพียงอย่างเดียวของคุณในการแยกตัวประกอบจำนวนคือการสร้างอย่างไม่ถูกต้อง ซึ่งทั้งหมดข้างต้นจะเป็นตัวอย่าง ดังนั้น เว้นแต่คุณจะมีเหตุผลเฉพาะเจาะจงที่จะคิดว่าตัวเลขเหล่านี้สร้างขึ้นอย่างไม่ถูกต้อง (สมมติว่านี่คือความท้าทายของ CTF) ฉันจะทำ ไม่ต้องพยายามทำลายมัน
หากคุณมีเหตุผลที่จะคิดว่าสิ่งนี้ควรสร้างขึ้นอย่างไม่เหมาะสม แสดงว่ามีการใช้งานสิ่งเหล่านี้อยู่ ตัวอย่างเช่น, ปราชญ์ มีการดำเนินการตาม ECM (ผ่าน GMP-ECM) ใน GMP-ECM หน้าตัวเองฉันยังเห็นการอ้างอิงถึง $p-1$ และ $p+1$แต่ฉันไม่รู้ว่าปราชญ์พยายามทำสิ่งเหล่านี้โดยตรงหรือไม่ (เนื่องจากมีประโยชน์จริง ๆ ก็ต่อเมื่อคุณสงสัยว่ามีการสร้างเซมิไพรม์อย่างไม่ถูกต้อง)
แต่ไม่มีการชนกับ "เซมิไพรม์ที่อ่อนแอ" อย่างใดอย่างหนึ่ง (ซึ่งไม่น่าจะเกิดขึ้นอย่างมากหากสร้างเซมิไพรม์อย่างถูกต้อง --- ดังนั้น เว้นแต่คุณจะมีเหตุผลที่จะคิดว่านี่คือ อ่อนแอ กึ่งไพรม์ RSA อาจไม่คุ้มที่จะตรวจสอบด้วยซ้ำ)
ใช่ เซมิไพรม์ 400 หลักนี้มีจุดอ่อนอย่างมาก ทำให้สามารถแยกตัวประกอบเป็นชั่วโมงได้
ฉันได้แยกตัวประกอบของจำนวนนี้แล้ว ดังนั้นคุณจึงสามารถกรุณาบอกฉันได้ CTF นี้อยู่ที่ไหนเพื่อที่ฉันจะได้รับเครดิต (พูดครึ่งล้อเล่น)
ทั้ง Fermat's ECM และ SNFS จะไม่ช่วยคุณใดๆ ระยะเวลาพอสมควร
ตัวประกอบ p มี 41606 ในหลักที่ 15-19 และ q มี 89827 ในหลักที่ 15-19 บน
อัปเดต (ย้ายมาที่นี่โดยผู้ดูแล)
บางทีวิธีการระดับนี้ ไม่
หรือ/และใช้ตัวคูณ? ไม่
การแจ้งเตือนสปอยเลอร์ - ปัจจัยต่างๆ ระบุไว้ด้านล่าง . . . .
n= 6962155154859963260211100482357357666900094513013513488352858667799199787495340476167566639530574848375895722792291996203873323650274512138128403360943634134259376986501375967452208380337012919869885380406071772232795575963202558402893589313281327208179913789760736615950818685956393838601277519011418885197723428318400763080858914698836058070301404903262955501113318317950597435778777212408626799143
p= 1055314811678641606424788110765439117222699930257095408671007391029759113842109970448108699505224742945927781061767905202515184760446787611555372203775837301834490832771874109424228620164137709228509254318229660698954763303449460372503950485172061048411036447824270015301213488707
คิว= 659723058732168982746927498749697452416263865798534694155775305494810601668451103917887716603988821282535336087463657549
เทคนิคที่ใช้คือลด N ให้อยู่ในรูปพิเศษที่แยกตัวประกอบได้ง่าย
แสดง N เป็นเลขฐานสองและสังเกตเห็น 0 หลายร้อยตัวอยู่ระหว่างตัวเลข 4 ตัว
สิ่งนี้ลดลงเป็นดังต่อไปนี้:
ยังไม่มีข้อความ = ก2^1228+ข2^875+ค*2^353+ง
ที่ไหน ก= 1506291488774150974626762365373 ข= 322571915263178581 ค=576377099039115423 d= 123431
ถือว่าสิ่งนี้เป็นพหุนามใน x โดย x=2:
ยังไม่มีข้อความ = กx^1228+ขx^875+ค*x^353+ง
ปัจจัยนี้อย่างรวดเร็วเพื่อ:
(359561509069941x^353+77)(4189245652768553*x^875 + 1603)
ในความคิดเห็น @Sam Blake ถามคำถามติดตามเกี่ยวกับจำนวนเต็มเพื่อแยกตัวประกอบ:
7215955072690155355400859323297730634528493510676300043022948136348249037517276095868127042993906604904230826475281383188764473510881994780947137238252071087749294743150564851420395422525735221770067605216401023
คำถามคือเซมิไพรม์ที่ 2 นี้ไม่สำคัญจริง ๆ ที่จะแยกตัวประกอบเป็นไพรม์?
เซมิไพรม์นี้ไม่อ่อนแอเพราะไม่ยอมแพ้รูปแบบพิเศษของมันอย่างง่ายดาย
มันอ่อนแอสำหรับศัตรูที่มีความสามารถระดับรัฐชาติ เพราะมันมีขนาดเพียง 701 บิต ขอแนะนำให้ใช้โมดูลัส 2048 บิตหรือสูงกว่าที่มีความยาวบิต p และ q เท่ากัน
นอกจากนี้ ดูเหมือนว่าจะไม่มีจุดอ่อนเมื่อใช้ Fermat's, p-1, อัตราส่วนนั้นไม่ใกล้ค่าเล็กน้อย เศษส่วน ECM ไม่มีประโยชน์
จำนวนเต็มนี้ดูเหมือนจะไม่ตรงกับรูปแบบพิเศษที่ง่ายต่อการแยกตัวประกอบ แม้ว่า เมื่อจำรูปแบบพิเศษได้แล้ว ก็สามารถแยกจำนวนออกได้โดยออกแรงน้อยลง การตรวจหารูปแบบพิเศษใดอาจใช้เวลานานเนื่องจากมีหลายรูปแบบ
คุณยินดีให้คำแนะนำอะไร ว่านี่คือเซมิไพรม์? ซึ่งปัจจัยต่างๆ ยาวไม่เท่ากัน? ว่าตัวประกอบเป็นพหุนามที่มีเงื่อนไข: a0 x 2^(k0) + a1 x 2^(k1) + a2 x 2^(k2)...
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
