ขั้นตอนวิธีของชอร์และจำนวนเฉพาะ

ทางลัด: ความแตกต่างความคล้ายคลึงกันค่าสัมประสิทธิ์การเปรียบเทียบ Jaccardการอ้างอิง

ความแตกต่างระหว่าง ขั้นตอนวิธีของชอร์และจำนวนเฉพาะ

ขั้นตอนวิธีของชอร์ vs. จำนวนเฉพาะ

ั้นตอนวิธีของชอร์ ตั้งชื่อตามนักคณิตศาสตร์ชื่อปีเตอร์ ชอร์ที่คิดขึ้นในปี..1994 โดยขั้นตอนวิธีนี้เป็นขั้นตอนวิธีควอนตัม (ขั้นตอนวิธีที่ทำงานบนควอนตัมคอมพิวเตอร์) ที่ใช้ในการแยกตัวประกอบของจำนวนเต็ม ซึ่งโดยทั่วไปแล้วใช้ในการแก้ปัญหา:ให้จำนวนเต็ม N แล้วให้หาตัวประกอบเฉพาะของ N ในควอนตัมคอมพิวเตอร์นั้น การแยกตัวประกอบด้วยขั้นตอนวิธีของชอร์จะใช้เวลาในการทำงานไม่เกินฟังก์ชันพหุนาม (Polynomial) ของขนาดข้อมูล โดยจะใช้เวลาเป็น O ((log N) 3) ซึ่งแสดงให้เห็นว่าเป็นการแก้ปัญหาการแยกตัวประกอบของจำนวนเต็มที่มีประสิทธิภาพในควอนตัมคอมพิวเตอร์ วิธีนี้จัดเป็นวิธีที่เร็วกว่าหลาย ๆ วิธีที่มีประสิทธิภาพที่รู้จักกันทั่ว ๆ ไปทีมักจะใช้เวลาเป็นฟังก์ชันเลขชี้กำลัง (Exponential) ขนาดของข้อมูล ให้ควอนตัมคอมพิวเตอร์มีจำนวนคิวบิตที่เพียงพอ ขั้นตอนวิธีของชอร์จะสามารถถอดรหัสประเภทระบบเข้ารหัสแบบกุญแจอสมมาตรได้ ยกตัวอย่างเช่น รหัสลับRSA โดยRSAนั้นตั้งอยู่บนสมมติฐานที่ว่าการคำนวณหาตัวประกอบของเลขที่มีจำนวนมาก ๆ นั้นเป็นไปไม่ได้ เท่าที่รู้กันสมมติฐานนี้ใช้ได้สำหรับคอมพิวเตอร์ทั่วไป และไม่มีขั้นตอนวิธีใดที่จะทำงานในเวลาไม่เกินฟังก์ชันพหุนาม อย่างไรก็ตามขั้นตอนวิธีของชอร์แสดงให้เห็นถึงวิธีการแยกตัวประกอบที่มีประสิทธิภาพในควอนตัมคอมพิวเตอร์ เพื่อให้ควอนตัมคอมพิวเตอร์มีขนาดที่ใหญ่พอที่จะถอดรหัสRSAได้ จึงสร้างแรงจูงใจอย่างมากในการออกแบบและการสร้างควอนตัมคอมพิวเตอร์ และสำหรับศึกษาแบบวิธีการบนควอนตัมคอมพิวเตอร์ใหม่ ๆ ในขณะที่ก็มีการให้การสนับสนุนการวิจัยระบบการเข้ารหัสแบบใหม่เพื่อสร้างความปลอดภัยจากควอนตัมคอมพิวเตอร์ เรียกว่าวิทยาการเข้ารหัสลับหลังควอนตัม (post-quantum cryptography). ในคณิตศาสตร์ จำนวนเฉพาะ (อังกฤษ: prime number) คือ จำนวนเต็มบวกที่มีตัวหารที่เป็นบวกอยู่ 2 ตัว คือ 1 กับตัวมันเอง ตรงข้ามกับจำนวนประกอบ ลำดับของจำนวนเฉพาะเริ่มต้นด้วย ดูบทความ รายชื่อจำนวนเฉพาะ สำหรับจำนวนเฉพาะ 500 จำนวนแรก สำหรับเลข 1 ไม่ถือว่าเป็นจำนวนเฉพาะตามนิยาม เซตของจำนวนเฉพาะทั้งหมดมักเขียนแทนด้วย \mathbb P เนื่องจาก 2 เป็นจำนวนเฉพาะตัวเดียวที่เป็นเลขคู่ ดังนั้นคำว่า จำนวนเฉพาะคี่ จะถูกใช้เพื่อหมายถึงจำนวนเฉพาะทั้งหมดที่ไม่ใช่ 2.

จำนวนประกอบ

ำนวนประกอบ (composite number) คือจำนวนเต็มบวกที่สามารถแยกตัวประกอบได้เป็นผลคูณของจำนวนเฉพาะ 2 จำนวนขึ้นไป จำนวนเต็มทุกๆจำนวนยกเว้น 1 กับ 0 จะเป็นจำนวนเฉพาะหรือจำนวนประกอบ อย่างใดอย่างหนึ่งเท่านั้น จำนวนเต็ม 14 เป็นจำนวนประกอบ เพราะว่ามันแยกตัวประกอบได้เป็น 2 × 7 จำนวนประกอบ 89 ตัวแรกมีดังนี้ จำนวนประกอบทุกจำนวนสามารถเขียนเป็นผลคูณของจำนวนเฉพาะอย่างน้อยสองจำนวน (ไม่จำเป็นต้องต่างกัน) นอกจากนี้ การเขียนแสดงจำนวนประกอบในรูปนี้ต่างกันได้เพียงลำดับการเรียงจำนวนเฉพาะ ตามทฤษฎีบทมูลฐานของเลขคณิต.

ขั้นตอนวิธีของชอร์และจำนวนประกอบ · จำนวนประกอบและจำนวนเฉพาะ · ดูเพิ่มเติม »