สารบัญ
12 ความสัมพันธ์: การกรองตัวเลขในขอบเขตแบบธรรมดาการหารเชิงทดลองวิทยาการเข้ารหัสลับอาร์เอสเอทฤษฎีบทมูลฐานของเลขคณิตทฤษฎีจำนวนขั้นตอนวิธีพีลบหนึ่งของพอลลาร์ดขั้นตอนวิธีของชอร์ขั้นตอนวิธีแบบสุ่มขั้นตอนวิธีโรห์ของพอลลาร์ดตะแกรงกำลังสองโดนัลด์ คนูธ
- ขั้นตอนวิธีการแยกตัวประกอบจำนวนเต็ม
การกรองตัวเลขในขอบเขตแบบธรรมดา
ในทฤษฎีจำนวนนั้น การกรองตัวเลขในขอบเขตแบบธรรมดา (General number field sieve: GNFS) เป็น วิธีการในการแยกตัวประกอบจำนวนเต็มที่มีขนาดใหญ่ (มีตัวประกอบ 100 ตัวขึ้นไป) ได้เร็วที่สุด มักจะใช้กับเลขที่มีจำนวนมากกว่า 110 บิท โดยนำไปใช้ในการเข้ารหัสลับแบบกุญแจอสมมาตร (Public-key cryptography) ซึ่งเป็นขั้นตอนวิธีที่เหมาะสำหรับลายเซ็นดิจิตอลรวมทั้งการเข้ารหัสที่มีความปลอดภัย การกรองตัวเลขในขอบเขตแบบธรรมดา นั้นมีเป้าหมายเพื่ออธิบายความสัมพันธ์ของที่มา, ข้อมูล และทฤษฎี ให้ผู้อ่านที่มีความเข้าใจในด้านต่างๆ เข้าใจและได้ข้อสรุปตรงกันและร่วมกันยกระดับพื้นฐานของวิธีการนี้ให้มีประสิทธิภาพมากขึ้นอีกด้วย จะเห็นได้ว่า การกรองตัวเลขในขอบเขตแบบธรรมดานั้นมีความสำคัญอย่างมากในการรับส่งข้อความที่เป็นความลับ จึงเป็นสิ่งที่นักวิชาการให้ความสนใจ ไม่ว่าจะเป็นตัวขั้นตอนการทำงาน ผลลัพธ์จากหลากหลายขอบเขตของคณิตศาสตร์และวิทยาการคอมพิวเตอร์, ทฤษฎีเลขพีชคณิต, สมการเชิงเส้น, ค่าจำนวนจริง และการวิเคราะห์เชิงซ้อน.
ดู การแยกตัวประกอบจำนวนเต็มและการกรองตัวเลขในขอบเขตแบบธรรมดา
การหารเชิงทดลอง
การหารเชิงทดลอง (trial division) เป็นขั้นตอนวิธีที่ทำความเข้าใจได้ง่าย เนื่องจากเป็นขั้นตอนวิธีที่ใช้วิธีการแบบบรู๊ทฟอร์ซ (brute-force) เพื่อช่วยในการแยกตัวประกอบของจำนวนเต็ม n โดยตรวจสอบว่ามีจำนวนเฉพาะใดๆที่มากกว่า 1 แต่น้อยกว่า n ที่สามารถหาร n ได้ลงตัว โดยวิธีนี้มักใช้กับการแยกตัวประกอบของจำนวนเต็มค่าน้อยๆ เนื่องจากประสิทธิภาพเชิงเวลาค่อนข้างช้.
ดู การแยกตัวประกอบจำนวนเต็มและการหารเชิงทดลอง
วิทยาการเข้ารหัสลับ
วิทยาการเข้ารหัสลับ วิชาเกี่ยวกับการเข้ารหัสลับคือการแปลงข้อความปกติให้กลายเป็นข้อความลับ โดยข้อความลับคือข้อความที่ผู้อื่น นอกเหนือจากคู่สนทนาที่ต้องการ ไม่สามารถเข้าใจได้ มนุษย์ได้คิดค้นวิธีการรักษาความลับของเรามาตั้งนาน นับตั้งแต่สมัยจูเลียส ซีซาร์ จนกระทั่งถึงปัจจุบันที่ใช้คอมพิวเตอร์มาช่วยเข้ารหัสลับและถอดรหัสลับ การเข้ารหัสแบบซีซ่าร์ทำได้โดยการนำตัวอักษรที่อยู่ถัดไปอีกสองตำแหน่งมาแทนที่ ยกตัวอย่างเช่น ถ้าต้องการเข้ารหัสคำว่า HELLO เราก็นำตัวอักษรที่ถัดจากตัว H ไปอีกสองตัวนั่นคือตัว J มาแทน ตัว E แทนด้วย G ตัว L แทนด้วย N ตัว O แทนด้วย Q ดังนั้นข้อความ HELLO จึงถูกแปลงให้เป็นคำว่า JGNNQ การเข้ารหัสลับแตกต่างกับวิทยาการอำพรางข้อมูล ข้อมูลที่ถูกอำพรางนั้นจะไม่ถูกเปลี่ยนแปลง ในขณะที่การเข้ารหัสลับจะเปลี่ยนแปลงข้อมูล วิทยาการเข้ารหัสลับสมัยใหม่ (Modern Cryptography) เป็นวิชาการที่ใช้แนวทางคณิตศาสตร์เพื่อแปลงข้อความปกติให้กลายเป็นข้อความลับ โดยให้เฉพาะคู่สนทนาที่ต้องการสามารถอ่านเข้าใจได้เท่านั้น ขั้นตอนวิธีของการเข้ารหัสลับสมัยใหม่ ได้แก่ Data Encryption Standard, Advanced Encryption Standard หรือ One-Time Padding ฯลฯ หลักการเบื้องต้นของการเข้ารหัสลับ ประการแรกคือ ขั้นตอนวิธีต้องเป็นที่รู้โดยทั่วไป และประการต่อมา รหัสจะต้องใหม่เสมอ.
ดู การแยกตัวประกอบจำนวนเต็มและวิทยาการเข้ารหัสลับ
อาร์เอสเอ
อาร์เอสเอ (RSA) คือขั้นตอนวิธีสำหรับการเข้ารหัสลับแบบกุญแจอสมมาตร (public-key encryption) เป็นขั้นตอนวิธีแรกที่ทราบว่าเหมาะสำหรับลายเซ็นดิจิทัลรวมถึงการเข้ารหัส เป็นหนึ่งในความก้าวหน้าครั้งใหญ่ครั้งแรกในการเข้ารหัสแบบกุญแจสาธารณะ อาร์เอสเอยังคงใช้ในโพรโทคอลสำหรับการพาณิชย์อิเล็กทรอนิกส์ และเชื่อว่ามีความปลอดภัยถ้ามีคีย์ที่ยาวพอ.
ดู การแยกตัวประกอบจำนวนเต็มและอาร์เอสเอ
ทฤษฎีบทมูลฐานของเลขคณิต
ทฤษฎีบทมูลฐานของเลขคณิต หรือ ทฤษฎีบทการแยกตัวประกอบได้อย่างเดียว (fundamental theorem of arithmetic หรือ unique factorization theorem) ในคณิตศาสตร์และทฤษฎีจำนวน คือประโยคซึ่งกล่าวว่า จำนวนเต็มบวกทุกจำนวนที่มากกว่า 1 สามารถเขียนอยู่ในรูปผลคูณของจำนวนเฉพาะได้วิธีเดียวเท่านั้น ตัวอย่างเช่น เราสามารถเขียน และไม่มีทางที่จะแยกตัวประกอบของ 6936 หรือ 1200 ได้เป็นอย่างอื่น ถ้าเราไม่สนใจลำดับของตัวประกอบ เพื่อที่จะให้ทฤษฏีบทนี้ใช้ได้กับจำนวน 1 เราจะถือว่า 1 เป็นผลคูณของของจำนวนเฉพาะศูนย์จำนวน (ดูใน ผลคูณว่าง).
ดู การแยกตัวประกอบจำนวนเต็มและทฤษฎีบทมูลฐานของเลขคณิต
ทฤษฎีจำนวน
ทฤษฎีจำนวน (number theory) โดยธรรมเนียมเดิมเป็นสาขาหนึ่งของคณิตศาสตร์บริสุทธิ์ ซึ่งศึกษาเกี่ยวกับคุณสมบัติของจำนวนเต็ม สาขานี้มีผลงานและปัญหาเปิดมากมายที่สามารถเข้าใจได้ง่าย แม้กระทั่งผู้ที่ไม่ใช่นักคณิตศาสตร์ แต่ในปัจจุบัน สาขานี้ยังได้สนใจกลุ่มของปัญหาที่กว้างขึ้น ซึ่งมักเป็นปัญหาที่ต่อยอดมาจากการศึกษาจำนวนเต็ม นักคณิตศาสตร์ที่ศึกษาสาขานี้เรียกว่า นักทฤษฎีจำนวน คำว่า "เลขคณิต" (arithmetic) มักถูกใช้เพื่ออ้างถึงทฤษฎีจำนวน นี่เป็นการเรียกในอดีต ซึ่งในปัจจุบันไม่ได้รับความนิยมเช่นเคย ทฤษฎีจำนวนเคยถูกเรียกว่า เลขคณิตชั้นสูง ซึ่งเลิกใช้ไปแล้ว อย่างไรก็ตามคำว่า "เลขคณิต" ยังปรากฏในสาขาทางคณิตศาสตร์อยู่ (เช่น ฟังก์ชันเลขคณิต เลขคณิตของเส้นโค้งวงรี หรือ ทฤษฎีบทมูลฐานของเลขคณิต) ไม่ควรจะสับสนระหว่างคำว่า เลขคณิต นี้ กับเลขคณิตมูลฐาน (elementary arithmetic) หรือสาขาของตรรกศาสตร์ที่ศึกษาเลขคณิตเปียโนในรูปของระบบรูปนั.
ดู การแยกตัวประกอบจำนวนเต็มและทฤษฎีจำนวน
ขั้นตอนวิธีพีลบหนึ่งของพอลลาร์ด
ั้นตอนวิธีพีลบหนึ่งของพอลลาร์ด (Pollard's p - 1 algorithm) เป็นขั้นตอนวิธีในการหาตัวประกอบของจำนวนเต็มโดยใช้แนวคิดทางทฤษฎีจำนวนเป็นพื้นฐาน ขั้นตอนวิธีดังกล่าว จอห์น พอลลาร์ด (John Pollard) นำเสนอขึ้นในปี 1974.
ดู การแยกตัวประกอบจำนวนเต็มและขั้นตอนวิธีพีลบหนึ่งของพอลลาร์ด
ขั้นตอนวิธีของชอร์
ั้นตอนวิธีของชอร์ ตั้งชื่อตามนักคณิตศาสตร์ชื่อปีเตอร์ ชอร์ที่คิดขึ้นในปี..1994 โดยขั้นตอนวิธีนี้เป็นขั้นตอนวิธีควอนตัม (ขั้นตอนวิธีที่ทำงานบนควอนตัมคอมพิวเตอร์) ที่ใช้ในการแยกตัวประกอบของจำนวนเต็ม ซึ่งโดยทั่วไปแล้วใช้ในการแก้ปัญหา:ให้จำนวนเต็ม N แล้วให้หาตัวประกอบเฉพาะของ N ในควอนตัมคอมพิวเตอร์นั้น การแยกตัวประกอบด้วยขั้นตอนวิธีของชอร์จะใช้เวลาในการทำงานไม่เกินฟังก์ชันพหุนาม (Polynomial) ของขนาดข้อมูล โดยจะใช้เวลาเป็น O ((log N) 3) ซึ่งแสดงให้เห็นว่าเป็นการแก้ปัญหาการแยกตัวประกอบของจำนวนเต็มที่มีประสิทธิภาพในควอนตัมคอมพิวเตอร์ วิธีนี้จัดเป็นวิธีที่เร็วกว่าหลาย ๆ วิธีที่มีประสิทธิภาพที่รู้จักกันทั่ว ๆ ไปทีมักจะใช้เวลาเป็นฟังก์ชันเลขชี้กำลัง (Exponential) ขนาดของข้อมูล ให้ควอนตัมคอมพิวเตอร์มีจำนวนคิวบิตที่เพียงพอ ขั้นตอนวิธีของชอร์จะสามารถถอดรหัสประเภทระบบเข้ารหัสแบบกุญแจอสมมาตรได้ ยกตัวอย่างเช่น รหัสลับRSA โดยRSAนั้นตั้งอยู่บนสมมติฐานที่ว่าการคำนวณหาตัวประกอบของเลขที่มีจำนวนมาก ๆ นั้นเป็นไปไม่ได้ เท่าที่รู้กันสมมติฐานนี้ใช้ได้สำหรับคอมพิวเตอร์ทั่วไป และไม่มีขั้นตอนวิธีใดที่จะทำงานในเวลาไม่เกินฟังก์ชันพหุนาม อย่างไรก็ตามขั้นตอนวิธีของชอร์แสดงให้เห็นถึงวิธีการแยกตัวประกอบที่มีประสิทธิภาพในควอนตัมคอมพิวเตอร์ เพื่อให้ควอนตัมคอมพิวเตอร์มีขนาดที่ใหญ่พอที่จะถอดรหัสRSAได้ จึงสร้างแรงจูงใจอย่างมากในการออกแบบและการสร้างควอนตัมคอมพิวเตอร์ และสำหรับศึกษาแบบวิธีการบนควอนตัมคอมพิวเตอร์ใหม่ ๆ ในขณะที่ก็มีการให้การสนับสนุนการวิจัยระบบการเข้ารหัสแบบใหม่เพื่อสร้างความปลอดภัยจากควอนตัมคอมพิวเตอร์ เรียกว่าวิทยาการเข้ารหัสลับหลังควอนตัม (post-quantum cryptography).
ดู การแยกตัวประกอบจำนวนเต็มและขั้นตอนวิธีของชอร์
ขั้นตอนวิธีแบบสุ่ม
ั้นตอนวิธีแบบสุ่ม (randomized algorithm) เป็นขั้นตอนวิธีที่ยอมให้มีการโยนเหรียญได้ ในทางปฏิบัติ เครื่องที่ใช้ทำงานขั้นตอนวิธีนี้ จะต้องใช้ตัวสร้างเลขสุ่มเทียม (pseudo-random number generator) ในการสร้างตัวเลขสุ่มขึ้นมา อัลกอรึทึมโดยทั่วๆไปมักใช้บิทสุ่ม (random bit) สำหรับเป็นอินพุตเสริม เพื่อชี้นำการกระทำของมันต่อไป โดยมีความหวังว่าจะช่วยให้มีประสิทธิภาพที่ดีใน "กรณีส่วนมาก (average case)" หรือหากพูดในทางคณิตศาสตร์ก็คือ ประสิทธิภาพของขั้นตอนวิธีมีค่าเท่ากับตัวแปรสุ่ม (random variable) ซึ่งคำนวณจากบิทสุ่ม โดยหวังว่าจะมีค่าคาดหมาย (expected value) ที่ดี กรณีที่แย่มากที่สุดมักจะมีโอกาสเกิดขึ้นน้อยมากจนแทบจะไม่ต้องสนใ.
ดู การแยกตัวประกอบจำนวนเต็มและขั้นตอนวิธีแบบสุ่ม
ขั้นตอนวิธีโรห์ของพอลลาร์ด
ั้นตอนวิธีโรห์ของพอลลาร์ด (Pollard's rho algorithm) เป็นขั้นตอนวิธีแบบสุ่มที่ใช้หาตัวประกอบของจำนวนประกอบที่มีค่ามาก โดยอาศัยคุณสมบัติของการหาร เพื่อให้หาตัวประกอบของเลขจำนวนนั้น ๆ ได้เร็ว ขั้นตอนวิธีนี้ จอห์น พอลลาร์ด (John Pollard) นำเสนอขึ้นในปี 1975 และต่อมา ริชาร์ด เบรนท์ (Richard Brent) ปรับปรุงในปี 1980.
ดู การแยกตัวประกอบจำนวนเต็มและขั้นตอนวิธีโรห์ของพอลลาร์ด
ตะแกรงกำลังสอง
ั้นตอนวิธีตะแกรงกำลังสอง (quadratic sieve algorithm: QS) เป็นหนึ่งในขั้นตอนวิธีในการแยกตัวประกอบของจำนวนเต็มให้อยู่ในรูปของผลคูณของเลขยกกำลังของจำนวนเฉพาะซึ่งยังเป็นสิ่งที่น่าสนใจเนื่องจากมีการนำไปใช้ในการเข้ารหัส (โดยถ้าใช้บางขั้นตอนวิธีอาจจะต้องใช้เวลามากกว่าอายุของจักรวาลเสียอีก) Carl Pomerance เป็นผู้ค้นพบขั้นตอนวิธีนี้ในปี..
ดู การแยกตัวประกอบจำนวนเต็มและตะแกรงกำลังสอง
โดนัลด์ คนูธ
นัลด์ เออร์วิน คนูธ (Donald Ervin Knuth, 10 มกราคม ค.ศ. 1938 - ปัจจุบัน) เป็นนักวิทยาการคอมพิวเตอร์และศาสตราจารย์ที่มหาวิทยาลัยสแตนฟอร์ดและผู้ชนะรางวัลทัวริง (พ.ศ.
ดู การแยกตัวประกอบจำนวนเต็มและโดนัลด์ คนูธ