ผลต่างระหว่างรุ่นของ "ตอนที่ 1: Levin's Search กับการแยกตัวประกอบของจำนวน"
Parinya (คุย | มีส่วนร่วม) (→เกริ่น) |
Parinya (คุย | มีส่วนร่วม) |
||
| แถว 11: | แถว 11: | ||
วิธีนี้อาจจะใช้ได้ผลดีหากตัวเลขมีค่าไม่มากนัก แต่ในแง่ของนักวิทยาการคอมพิวเตอร์แล้ว วิธีนี้ถือว่าสิ้นเปลืองเวลาและพลังงานชิวิตของคอมพิวเตอร์เป็นอย่างมาก ในการคิดความเร็วในการคำนวณของคอมพิวเตอร์นั้น เราจะคิดความเร็วเทียบกับขนาดของข้อมูลที่ป้อนเข้า หาก n มีค่าเป็น 3,000,013 ขนาดของข้อมูลที่ป้อนเข้าก็คือ 7 หลักเท่านั้น แต่วิธีการแยกตัวประกอบดังกล่าวอาจใช้เวลาการทำงานนับหมื่นรอบ เพื่อหาจำนวนดังกล่าว ดังนั้นแล้ววิธีนี้จึงถือว่าไม่มีประสิทธิภาพ | วิธีนี้อาจจะใช้ได้ผลดีหากตัวเลขมีค่าไม่มากนัก แต่ในแง่ของนักวิทยาการคอมพิวเตอร์แล้ว วิธีนี้ถือว่าสิ้นเปลืองเวลาและพลังงานชิวิตของคอมพิวเตอร์เป็นอย่างมาก ในการคิดความเร็วในการคำนวณของคอมพิวเตอร์นั้น เราจะคิดความเร็วเทียบกับขนาดของข้อมูลที่ป้อนเข้า หาก n มีค่าเป็น 3,000,013 ขนาดของข้อมูลที่ป้อนเข้าก็คือ 7 หลักเท่านั้น แต่วิธีการแยกตัวประกอบดังกล่าวอาจใช้เวลาการทำงานนับหมื่นรอบ เพื่อหาจำนวนดังกล่าว ดังนั้นแล้ววิธีนี้จึงถือว่าไม่มีประสิทธิภาพ | ||
| − | ในด้านวิทยาการคอมพิวเตอร์นั้น ปัญหาการแยกตัวประกอบถือว่าเป็นปัญหาที่ยากมาก การเข้ารหัสเกือบทั้งหมดในปัจจุบันถูกสร้างขึ้นมาโดยสมมติฐานที่ว่า ผู้ที่ต้องการขโมยข้อมูลไม่สามารถถอดรหัสได้ เพราะฉะนั้น หากมีผู้ใดค้นพบวิธีการแยกตัวประกอบอย่างมีประสิทธิภาพ ระบบความปลอดภัยในคอมพิวเตอร์เกือบทั้งหมดก็จะกลายเป็นไม่ปลอดภัยทันที | + | ในด้านวิทยาการคอมพิวเตอร์นั้น ปัญหาการแยกตัวประกอบถือว่าเป็นปัญหาที่ยากมาก การเข้ารหัสเกือบทั้งหมดในปัจจุบันถูกสร้างขึ้นมาโดยสมมติฐานที่ว่า ผู้ที่ต้องการขโมยข้อมูลไม่สามารถถอดรหัสได้ เพราะฉะนั้น หากมีผู้ใดค้นพบวิธีการแยกตัวประกอบอย่างมีประสิทธิภาพ ระบบความปลอดภัยในคอมพิวเตอร์เกือบทั้งหมดก็จะกลายเป็นไม่ปลอดภัยทันที |
| + | |||
| + | กลุ่มวิจัย RSA ได้ตั้งรางวัลไว้สำหรับผู้ที่สามารถใช้คอมพิวเตอร์แยกตัวประกอบจำนวนขนาดใหญ่ได้ในเวลาสั้นๆ [http://www.rsasecurity.com/rsalabs/node.asp?id=2092] (โดยปกติแล้วปัญหาการแยกตัวประกอบจำนวนใหญ่ๆเชื่อว่า ต่อให้รันโปรแกรมไปจนโปรแกรมเมอร์แก่ตาย คอมพิวเตอร์ก็ยังแยกตัวประกอบไม่เสร็จ) | ||
| + | |||
| + | |||
== Levin's search == | == Levin's search == | ||
| + | |||
== บทสรุป == | == บทสรุป == | ||
รุ่นแก้ไขเมื่อ 06:57, 21 พฤศจิกายน 2549
เกริ่น
"Only math nerds would call finite" Leonid Levin
ปัญหาการแยกตัวประกอบจำนวนก็คือปัญหาที่เรามีจำนวนจำนวนหนึ่งที่เป็นจำนวนประกอบ n เราจะสามารถหาวิธีการที่มีประสิทธิภาพที่สุดในการแยกตัวประกอบของจำนวนนั้นได้อย่างไร หากลองมองกลับไปวิธีที่ใช้สอนเด็กประถม เราอาจจะทำได้ดังนี้ ลองหารจำนวนตั้งแต่ 1, 2, 3 จนกระทั่งพบจำนวนแรกที่หารจำนวนนั้นลงตัว เท่านี้ก็แยกตัวประกอบสำเร็จ
วิธีนี้อาจจะใช้ได้ผลดีหากตัวเลขมีค่าไม่มากนัก แต่ในแง่ของนักวิทยาการคอมพิวเตอร์แล้ว วิธีนี้ถือว่าสิ้นเปลืองเวลาและพลังงานชิวิตของคอมพิวเตอร์เป็นอย่างมาก ในการคิดความเร็วในการคำนวณของคอมพิวเตอร์นั้น เราจะคิดความเร็วเทียบกับขนาดของข้อมูลที่ป้อนเข้า หาก n มีค่าเป็น 3,000,013 ขนาดของข้อมูลที่ป้อนเข้าก็คือ 7 หลักเท่านั้น แต่วิธีการแยกตัวประกอบดังกล่าวอาจใช้เวลาการทำงานนับหมื่นรอบ เพื่อหาจำนวนดังกล่าว ดังนั้นแล้ววิธีนี้จึงถือว่าไม่มีประสิทธิภาพ
ในด้านวิทยาการคอมพิวเตอร์นั้น ปัญหาการแยกตัวประกอบถือว่าเป็นปัญหาที่ยากมาก การเข้ารหัสเกือบทั้งหมดในปัจจุบันถูกสร้างขึ้นมาโดยสมมติฐานที่ว่า ผู้ที่ต้องการขโมยข้อมูลไม่สามารถถอดรหัสได้ เพราะฉะนั้น หากมีผู้ใดค้นพบวิธีการแยกตัวประกอบอย่างมีประสิทธิภาพ ระบบความปลอดภัยในคอมพิวเตอร์เกือบทั้งหมดก็จะกลายเป็นไม่ปลอดภัยทันที
กลุ่มวิจัย RSA ได้ตั้งรางวัลไว้สำหรับผู้ที่สามารถใช้คอมพิวเตอร์แยกตัวประกอบจำนวนขนาดใหญ่ได้ในเวลาสั้นๆ [1] (โดยปกติแล้วปัญหาการแยกตัวประกอบจำนวนใหญ่ๆเชื่อว่า ต่อให้รันโปรแกรมไปจนโปรแกรมเมอร์แก่ตาย คอมพิวเตอร์ก็ยังแยกตัวประกอบไม่เสร็จ)
