- บทนำ
- จำนวนเฉพาะเป็นแนวคิดที่อธิบายได้ง่าย แต่ซ่อนความซับซ้อนอันมหาศาล
- นำไปใช้งานได้หลากหลายด้าน เช่น แนวคิดทางคณิตศาสตร์ การแสดงภาพที่น่าสนใจ และการเข้ารหัสลับ
- ตัดสินใจลองท้าทายการสร้างจำนวนเฉพาะผ่านการเขียนโค้ด
- ความท้าทาย
- การสร้างจำนวนเฉพาะที่สามารถใช้กับอัลกอริทึม RSA ได้
- ความยาวที่เหมาะสมสำหรับคีย์ RSA ในปัจจุบันคือ 2048 บิต จึงต้องการจำนวนเฉพาะขนาด 1024 บิตจำนวน 2 ตัว
- ข้อจำกัด:
- เขียนโค้ดด้วยตนเองตั้งแต่ต้น (โดยไม่ใช้ส่วนประกอบภายนอก)
- ใช้เฉพาะ CPU AMD Ryzen 7 และ RAM 16GB ของโน้ตบุ๊กเท่านั้น
- สร้างจำนวนเฉพาะให้ได้ใน "เวลาที่สมเหตุสมผล"
- เลือกภาษา Rust
- การสร้างจำนวนเฉพาะ 16 บิต
- ใช้ตัวสร้างตัวเลขสุ่มแบบกึ่งสุ่ม
/dev/urandom เพื่อสร้างเลขสุ่ม
- ใช้วิธีการทดสอบการหารแบบตรงไปตรงมา (Trial Division)
- สร้างจำนวนเฉพาะ 16 บิตได้โดยเฉลี่ยใน 40ms
- การสร้างจำนวนเฉพาะ 64 บิต
- ใช้อัลกอริทึมการทดสอบการหารแบบตรงไปตรงมาที่ปรับประสิทธิภาพแล้ว
- ตรวจเฉพาะตัวเลขในรูปแบบ 6k±1
- สร้างรายชื่อจำนวนเฉพาะเล็ก ๆ ล่วงหน้า แล้วกรองตัวเลขที่หารลงตัวได้ง่ายก่อน
- หลังจากปรับปรุงใช้เวลาประมาณ 6 วินาที
- ในตัวเลขขนาดใหญ่ขึ้น จะมีข้อจำกัดเมื่อใช้วิธีการแบบชี้ขาด (deterministic)
- การทดสอบจำนวนเฉพาะแบบความน่าจะเป็น
- ใช้กฎเล็กของเฟอร์มาต์ (Fermat's Little Theorem)
- มีปัญหาที่จำนวนประกอบซ้อนบางตัวอาจผ่านเงื่อนไขได้เช่นกัน (Pseudoprimes)
- การทดสอบความเป็นจำนวนเฉพาะแบบ Miller-Rabin (Miller-Rabin Primality Test)
- วิธีการตรวจสอบแบบความน่าจะเป็นที่พัฒนาแนวคิดจากกฎของเฟอร์มาต์
- ไม่มีจำนวนประกอบซ้อนที่เป็น Pseudoprime ต่อฐานใดฐานหนึ่งเสมอไป
- ความน่าจะเป็นผิดพลาดต่ำมาก จึงสามารถใช้งานได้ในทางปฏิบัติ
- การสร้างจำนวนเฉพาะ 128 บิต
- สร้างจำนวนเฉพาะได้อย่างรวดเร็วด้วยการทดสอบ Miller-Rabin (เฉลี่ย 0.03 วินาที)
- การขยายไปถึง 1024 บิตทำได้ยากเนื่องจากข้อจำกัดของชนิดข้อมูล
u128
- การพัฒนา BigInt สำหรับ 1024 บิต
- ค่อยๆ ปรับปรุงผ่านการลองหลายครั้ง
- ความพยายามที่ 1: เก็บแต่ละหลักของตัวเลขในอาร์เรย์
- ความพยายามที่ 2: เก็บตัวเลขในรูปแบบไบนารี
- ความพยายามที่ 3: เก็บตัวเลขเป็นก้อนข้อมูลแบบไบต์
- ความพยายามที่ 4: เก็บตัวเลขเป็นก้อนข้อมูลขนาดหน่วย
u64
- ความพยายามที่ 5: ปรับแต่งอัลกอริทึมคณิตศาสตร์พื้นฐาน
- ปรับแต่งการทดสอบ Miller-Rabin และตรรกะการทำงานทั้งหมด
- การประมวลผลแบบขนานด้วยมัลติเธรด
- ผลลัพธ์สุดท้าย
- สร้างจำนวนเฉพาะ 1024 บิตได้ภายในราว 40ms (8ms ~ 800ms)
- เมื่อใช้การประมวลผลแบบขนาน ใช้เวลาเฉลี่ยเพียง 0.04 วินาที
ความคิดเห็นของ GN⁺
- กระบวนการค่อยๆ พัฒนาอย่างต่อเนื่องผ่านการลองผิดลองถูกนั้นน่าประทับใจ
- เริ่มจากการใช้อัลกอริทึมแบบเรียบง่าย แล้วเพิ่มแนวคิดใหม่ ๆ และทำการปรับปรุงในแต่ละขั้น
- แม้จะเกิดความล้มเหลวก็ไม่ยอมแพ้ และพยายามทำความเข้าใจสาเหตุของปัญหาเพื่อหาทางแก้ไข
- แม้ผู้เขียนจะมีพื้นฐานคณิตศาสตร์ไม่มาก แต่การค้นคว้าและทำความเข้าใจเนื้อหาที่เกี่ยวข้องอย่างมุ่งมั่นเป็นสิ่งที่เด่นชัด
- เรียนรู้แนวคิดทางคณิตศาสตร์ที่จำเป็น เช่น กฎเล็กของเฟอร์มาต์ การทดสอบ Miller-Rabin และอื่น ๆ
- เข้าใจเนื้อหาที่ยากให้ลึกพอที่จะนำไปปฏิบัติได้จริง
- การสร้าง BigInt ขึ้นมาเองเพื่อเอาชนะข้อจำกัดของชนิดจำนวนเต็มความยาวคงที่เป็นจุดที่น่าสนใจ
- ไม่เพียงแต่ใช้ไลบรารีสำเร็จรูป แต่ยังเข้าใจหลักการทำงานภายในและปรับแต่งประสิทธิภาพด้วย
- การลองแนวคิดหลากหลายและค่อยๆ พัฒนานั้นชัดเจนมาก
- การใช้มัลติเธรดเพิ่มประสิทธิภาพอย่างมีนัยสำคัญเป็นสิ่งที่น่าสนใจมาก
- เล็งเห็นลักษณะของปัญหาที่สามารถคำนวณแบบแยกส่วนได้ และนำมาใช้ประโยชน์ได้อย่างเหมาะสม
- ไม่ใช่เพียงการไล่หา "ความเร็ว" เท่านั้น แต่เป็นการเลือกแนวทางที่เหมาะกับคุณสมบัติของปัญหา
- แม้จะยังไม่ถึงระดับความปลอดภัยทางด้านการเข้ารหัส แต่โครงการนี้มีความหมายอย่างมากในเชิงการเรียนรู้และการสำรวจ
- มากกว่าความเหมาะสมเชิงใช้งานจริง เป็นโจทย์ที่สะท้อนความอยากรู้อยากเห็นและความท้าทายของผู้เขียนได้ชัดเจน
- คาดหวังว่าความเข้าใจเชิงลึกและประสบการณ์ที่ได้จากกระบวนการนี้จะช่วยให้ผู้เขียนเติบโตได้มากในอนาคต
1 ความคิดเห็น
ความคิดเห็นจาก Hacker News
โดยทั่วไปแล้ว เหรียญดิจิทัลบางสกุลใช้การค้นหาจำนวนเฉพาะขนาดใหญ่เป็นส่วนหนึ่งของฟังก์ชัน proof-of-work เมื่อประมาณ 8 ปีก่อน เคยมีรายได้เยอะมากจากการทำให้การทดสอบจำนวนเฉพาะเร็วขึ้นได้มาก ผู้เขียนเคยเป็นทั้งผู้พัฒนาและผู้ดูแลซอฟต์แวร์ขุดสำหรับ Riecoin ในระยะหนึ่ง
บทความนี้ละเว้นการเพิ่มประสิทธิภาพสูงสุดสำหรับการทดสอบจำนวนเฉพาะที่เร็วที่สุด คือ Montgomery multiplication ซึ่งเป็นพื้นฐานสำหรับการทำโมดูลาร์เอกซ์โพเนนเชียชันแบบปฏิบัติเชิงเร็ว
CGBN ที่ Niall Emmart เผยแพร่เป็นไลบรารี bigint บน GPU ที่เร็วมากจริงๆ และยังเป็นการนำไปใช้ batch modexp ที่เร็วที่สุดเท่าที่ฉันรู้จัก
Python มี modexp ในตัวที่คำนวณ pow(x, y, m) → x^y % m ได้ค่อนข้างดี ช่วยให้การเขียน Fermat หรือ Miller-Rabin เพื่อทดสอบจำนวนเฉพาะทำได้ง่าย
ตอนแรกฉันคิดว่าความคิดเรื่องการทดสอบจำนวนเฉพาะแบบ probabilistic นั้นแปลก และพยายามหาฟังก์ชัน deterministic ที่จัดการกับตัวเลขขนาดใหญ่อย่างแท้จริง แต่ APR-CL กับ ECPP มีความซับซ้อนทางคณิตศาสตร์มากเกินไป จนยากต่อความเข้าใจ สุดท้ายจึงรู้ว่าเกือบทุกที่ รวมทั้ง RSA ใช้อัลกอริทึมแบบ probabilistic อยู่
การทำให้ Miller-Rabin เป็น deterministic ในช่วงค่าสูงสุดที่กำหนดนั้นไม่ยากเลย แค่เลือกฐานที่พิสูจน์ได้ว่าสามารถตัด pseudo-prime ทั้งหมดในช่วงนั้นออกได้
การคูณจำนวนขนาดใหญ่ทำได้ง่ายมากด้วย inline assembly เพียงบรรทัดเดียว อยากเห็นถ้าเพิ่มแนวคิดการคูณแบบขยายเข้าในภาษา C บ้าง ซัพพอร์ตด้านฮาร์ดแวร์มีให้แทบทุกที่
Fermat test ก็เพียงพอแล้ว เพราะถ้าตัวเลขไม่ใช่จำนวนเฉพาะจริงๆ อัลกอริทึมจะไม่ทำงานได้ อย่างไรก็ตาม ฉันไม่รู้ว่าจะพิสูจน์ได้ไหมว่าค่า P/Q ที่ไม่ใช่จำนวนเฉพาะใดๆ ไม่มีอยู่ที่ยังสามารถเข้ารหัส/ถอดรหัสข้อความได้สำเร็จ
อยากรู้ว่าใช้เวลาเท่าไรในโปรเจกต์นี้ ผู้เขียนได้ implement Karatsuba, Toom-Cook, complex FFT, NTT และ Schönhage–Strassen มาแล้ว แนะนำ "A Friendly Introduction to Number Theory" ของ Silverman
เมื่อมีการเขียนโค้ดคูณจำนวนใหญ่ด้วยตัวเอง ก็รู้สึกได้เลยว่าการแปลงคำอธิบายระดับสูงจากงานเขียนทางคณิตศาสตร์ให้กลายเป็นการคำนวณจริงนั้นยากมาก ด้วยเหตุผลเกี่ยวกับ radix ก็มีรายละเอียดค่อนข้างผิดพลาดเล็กน้อย
การปรับปรุงขั้นสุดท้ายที่เพิ่ม 2 แทนการสร้างเลขใหม่จะทำให้ความปลอดภัยลดลงบ้าง เพราะจำนวนเฉพาะไม่ได้กระจายแบบสม่ำเสมอ จึงมีแนวโน้มเอนเอียงไปหาจำนวนเฉพาะที่อยู่ถัดจากช่วงห่างจำนวนเฉพาะขนาดใหญ่
คำอธิบายของทฤษฎีบทเล็กของ Fermat มีข้อผิดพลาดนิดหน่อย คือกล่าวว่าค่า a^(p-1) หารด้วย p ลงตัว แต่ที่ถูกต้องคือ a^(p-1) - 1 ต้องหารด้วย p ลงตัว และในเชิงศัพท์ทาง modular arithmetic ถือว่าถูกต้องแล้ว