การกรองตัวเลขในขอบเขตแบบธรรมดา

จากวิกิพีเดีย สารานุกรมเสรี
ไปยังการนำทาง ไปยังการค้นหา

ในทฤษฎีจำนวนนั้น การกรองตัวเลขในขอบเขตแบบธรรมดา (อังกฤษ: General number field sieve: GNFS) เป็น วิธีการในการแยกตัวประกอบจำนวนเต็มที่มีขนาดใหญ่ (มีตัวประกอบ 100 ตัวขึ้นไป) ได้เร็วที่สุด[1] มักจะใช้กับเลขที่มีจำนวนมากกว่า 110 บิท โดยนำไปใช้ในการเข้ารหัสลับแบบกุญแจอสมมาตร (Public-key cryptography) ซึ่งเป็นขั้นตอนวิธีที่เหมาะสำหรับลายเซ็นดิจิตอลรวมทั้งการเข้ารหัสที่มีความปลอดภัย

การกรองตัวเลขในขอบเขตแบบธรรมดา นั้นมีเป้าหมายเพื่ออธิบายความสัมพันธ์ของที่มา, ข้อมูล และทฤษฎี ให้ผู้อ่านที่มีความเข้าใจในด้านต่างๆ เข้าใจและได้ข้อสรุปตรงกันและร่วมกันยกระดับพื้นฐานของวิธีการนี้ให้มีประสิทธิภาพมากขึ้นอีกด้วย

จะเห็นได้ว่า การกรองตัวเลขในขอบเขตแบบธรรมดานั้นมีความสำคัญอย่างมากในการรับส่งข้อความที่เป็นความลับ จึงเป็นสิ่งที่นักวิชาการให้ความสนใจ ไม่ว่าจะเป็นตัวขั้นตอนการทำงาน ผลลัพธ์จากหลากหลายขอบเขตของคณิตศาสตร์และวิทยาการคอมพิวเตอร์, ทฤษฎีเลขพีชคณิต, สมการเชิงเส้น, ค่าจำนวนจริง และการวิเคราะห์เชิงซ้อน

การกรองตัวเลขในขอบเขต[แก้]

ตั้งแต่ได้มีการเปิดตัว elliptic curve factorization method (ECM) ในปี ค.ศ. 1985 แล้วก็ไม่มีทฤษฎีใดที่จะกล่าวถึงขั้นตอนวิธีการแยกตัวประกอบอีกเลย นอกจากขั้นตอนวิธีที่มีอยู่เดิม ซึ่งได้แก่ Multiple Polynomial Quadratic Sieve (MPQS) และวิธีนี้นับเป็นวิธีที่เร็วที่สุด ณ ขณะนั้น แต่ก็ไม่ได้เป็นที่ยอมรับแต่อย่างใด ต่อมาได้มีการพูดถึง การกรองตัวเลขในขอบเขต (Number Field Sieve) (NFS) [2] กันมากขึ้น ว่าเป็นวิธีการแยกตัวประกอบที่ดีและเร็วกว่าขั้นตอนวิธีใดๆที่เคยมีมา ขั้นตอนวิธีประเภทนี้ สามารถแยกตัวประกอบเลขจำนวนหนึ่งโดยใช้เวลาเพียงแค่ไม่กี่สัปดาห์ เมื่อเทียบกับ Multiple Polynomial Quadratic Sieve (MPQS) ซึ่งใช้เวลานับปี แต่จากการบอกเล่าของ Joe Buhler และ Carl Pomerance ที่กล่าวไว้ว่า ทฤษฎีการกรองตัวเลขในขอบเขตนั้นสามารถนำไปใช้ได้ดีกับเลขจำนวนเต็มทั่วๆ ไป

จากผลการวิจัยพบว่า รูปแบบของสมการที่เหมาะสม อยู่ในรูป โดยกำหนดให้ และ เป็นจำนวนที่น้อยมากๆ และ เป็นจำนวนที่มีขนาดใหญ่มาก

โดยที่ ประมาณ 1.526 (เป็นเลขคงที่ ไม่ว่า จะเป็นเลขจำนวนเต็มใดๆ)

วิธีนี้เป็นวิธีที่ดีกว่า Multiple polynomial quadratic sieve (MPQS) เป็นอย่างมาก

วิธีนี้จะขึ้นอยู่กับจำนวนเต็ม ด้วย โดยทั่วไปวิธีนี้จะได้ผลที่ใกล้เคียงกับ Multiple polynomial quadratic sieve (MPQS) หรืออาจจะดีกว่าเพียงเล็กน้อยเท่านั้น

ขั้นตอนการกรองตัวเลขในขอบเขตแบบธรรมดา[แก้]

กำหนดให้ คือ ตัวประกอบ ที่ถูกเลือก คือ เซต ของจำนวนเต็ม

ดังนั้น จะพบว่า ทุกๆ ที่เป็นสมาชิกของ จะอยู่เหนือ และ สำหรับ บางตัวที่เป็นสมาชิกของ เนื่องจากรูปแบบสมการพหุนามพิเศษ คือ

ขั้นตอนการกรองตัวเลขในขอบเขตแบบธรรมดาพัฒนามาจากพหุนามกำลังสองซึ่งมีความสามารถในการหาคำตอบสำหรับตัวเลขที่มี เลขชี้กำลัง จำนวนมากๆ

ตัวอย่างการกรองตัวเลขในขอบเขตแบบธรรมดา[แก้]

วิธีการกรองตัวเลขในขอบเขตแบบธรรมดา เคยถูกใช้ในการหาตัวประกอบที่มีจำนวน 193 หลัก RSA₆₄₀ ขนาดใหญ่ ในเดือนพฤศจิกายน ปี ค.ศ. 2005[3] โดย F. Bahr, M. BOEHM, J. FRANKE,T. KLEINJUNG ซึ่งจะได้ว่า

RSA640=310741824049004372135075003588856793003734602284272754572016194882320644051808150455634682967172328678243791627283803341547107310
8501919548529007337724822783525742386454014691736602477652346609

=1634733645809253848443133883865090859841783670033092312181110852389333100104508151212118167511579·19008712816648221131268515739354139754
71896789968515493666638539088027103802104498957191261465571

โครงสร้างพื้นฐานของการกรองตัวเลขในขอบเขตแบบธรรมดา[แก้]

เราสามารถทำการกรองตัวเลขในขอบเขตแบบธรรมดา ได้ในขั้นตอนต่อไปนี้[4]

  1. ทำการเลือกพหุนาม เวลาของขั้นตอนวิธีการนี้ต้องขึ้นอยู่กับคุณภาพของพหุนามที่เลือก ดังนั้นเราต้องเลือกอย่างระมัดระวังและเรากำหนดให้ค่าพหุนามที่เลือกเป็น โดย
  2. ขั้นตอนการกรอง ( sieving ) : สร้างสัมพันธ์ (Lattice or Line Sieves) เส้นตะแกรง ( Line Sieves ) สำหรับการกรองตัวเลขในขอบเขตแบบธรรมดา เส้นจะมีความยาวมาก เราสามารถจัดการได้โดยการตั้งเวลา แต่การตั้งเวลานั้น จะใช้เวลาค่อนข้างนานสำหรับตัวเลขที่มีขนาดใหญ่มากๆ
  3. การลบสำเนาและการตัดแต่ง ( Remove copies and Pruning) เมื่อเราได้ค่าของ มากพอแล้ว ก็จะนำค่าที่ได้ทั้งหมดมาใส่เป็นเมทริกซ์เพื่อที่จะทำการแก้ระบบสมการเชิงเส้นที่มีขนาดใหญ่กว่า แต่ก่อนที่เราจะเริ่มทำในแบบที่ได้กล่าวมาข้างต้นได้เราจะต้องทำ
    1. ลบสำเนา เนื่องจากขั้นตอนการสร้างสัมพันธ์เป็นการรวมกันของเส้นและเส้นตะแกรงเข้าด้วยกันหรือจากการผิดพลาดของผู้คำนวณทำให้มีค่า มากเกินไปการลบสำเนาสามารถทำได้โดยใช้ตารางแฮชเข้ามาช่วยและเรายังสามารถช่วยลดขนาดของตารางแฮชได้โดยใช้ฟังก์ชันแฮช
    2. การตัดแต่ง (Pruning) เราสามารถทำได้โดยการลดขนาดของเมทริกซ์ ได้โดย กำหนดค่าตจำนวนเฉพาะที่แตกต่างกันในแถวของ เมทริกซ์ ซึ่งเรียกว่า ดังนั้น

เราสามารถบอกได้ว่า ซึ่งอ้างอิงจาก พีชคณิตเชิงเส้น ตามขั้นตอนดังนี้

  1. ย้าย 0
  2. ถ้าในแถว ใน เราสามารถย้าย ในแถวนั้นๆ โดย ให้
  3. การกรอง เพื่อเป็นการลดขนาดของเมทริกซ์ และลดจำนวนของหลักลง เราสามารถใช้ทฤษฎีของกราฟในการหาค่าการดำเนินงานของเมทริกซ์ที่ใช้เวลาน้อยที่สุด
  4. การแก้สมการเชิงเส้น

หลังจากการลดสมการแล้ว ก็มาถึงการแก้สมการเชิงเส้น ที่มีจำนวนมากๆ โดยทั่วไปแล้ว ขั้นตอนวิธีที่ดีที่สุดในการ random matrix ที่มีค่า 0 ที่แตกต่างกัน คือ การกำจัดเกาท์ร่วมกับการคูณ เมทริกซ์ อย่างรวดเร็ว แต่สำหรับกรณีที่เรามี ระบบสมการเชิงเส้นเบาบาง ดังนั้น เราจะมีขั้นตอนวิธีที่ดีกว่าคือ

  1. ขั้นตอนวิธีของ Lonczos (อังกฤษ: Lonczos Algorithm)
  2. ขั้นตอนวิธีของ Lonczos แบบปิดกั้น (อังกฤษ: Block-Lonzos Algorithm)
  3. ขั้นตอนวิธีของ Wiedemann (อังกฤษ: Wiedemann Algorithm)
  4. ขั้นตอนวิธีของ Wiedemann แบบปิดกั้น (อังกฤษ: Block-Wiedemann Algorithm)
  5. การคำนวณหารากที่สอง

ขั้นตอนวิธีดังที่กล่าวมาในข้างต้นนั้นถูกกล่าวถึงโดย Daniel Loebenberger ซึ่งการคำนวณค่ากำลังสองของ นั้น ไม่พบปัญหาใดๆ มีวิธีการคำนวณ ค่ากำลังสองมามากหลายวิธีในแต่ละขั้นตอนวิธีและวิธีใหม่ล่าสุดคือวิธี Montgomery นั่นเอง

อ้างอิง[แก้]

  1. Kostas Bimpikis and Ragesh Jaiswal ,Modern Factoring Algorithms ,University of California, San Diego
  2. Matthew E. Briggs. wAn Introduction to the General Number Field Sieve x the degree of Master of Science in Mathematics , the Faculty of the Virginia Polytechnic Institute and State University
  3. http://www.freerepublic.com/focus/f-news/1518642/posts
  4. http://wob.iai.uni-bonn.de/Wob/images/77333588.pdf