Phân tích số nguyên

Trong lý thuyết số, phân tích số nguyên là việc phân tách một hợp số thành một tích của các số nguyên nhỏ hơn. Nếu các số nguyên đó giới hạn lại chỉ là số nguyên tố, quá trình được gọi là phân tích số nguyên thành thừa số nguyên tố.

Khi con số ban đầu rất lớn, không có thuật toán phân tích nhân tử dùng máy tính lượng tử có hiệu quả nào được biết đến. Một nỗ lực của một số nhà nghiên cứu, kết luận vào năm 2009, để phân tích thành thừa số một số có 232 chữ số (RSA-768) sử dụng hàng trăm máy tính đã mất hai năm và các nhà nghiên cứu ước tính rằng một phép đồng dư RSA 1024 bit sẽ mất thời gian gấp một nghìn lần như vậy. Tuy vậy, cũng chưa chứng minh được việc không tồn tại một thuật toán nhanh hơn, hiệu quả hơn. Sự khó khăn phức tạp của bài toán này là trung tâm của hàng loạt thuật toán được sử dụng rộng rãi trong mật mã học như RSA. Nhiều lĩnh vực của toán học và khoa học máy tính đã được đưa ra để giải quyết vấn đề này, bao gồm đường cong elliptic, lý thuyết số đại số, và máy tính lượng tử

Không phải tất cả các con số với một chiều dài nhất định đều khó phân tích ra thừa số. Các trường hợp khó nhất của phân tích ra thừa số (đối với các kỹ thuật hiện đang được biết đến) là các số nửa nguyên tố, tích của hai số nguyên tố. Khi cả hai số nguyên tố này đều lớn, ví dụ hơn 2.000 bit, được lựa chọn ngẫu nhiên và có cùng kích thước (nhưng không quá gần, nhằm tránh phân bổ hiệu quả theo phương pháp phân tích thừa số của Fermat), ngay cả các thuật toán phân tích nhân tố nhanh nhất trên các máy tính nhanh nhất có thể mất nhiều thời gian đến mức khiến cho việc phân tích trở thành không thực tế; nghĩa là, khi số chữ số của số nguyên tố tăng lên, số phép toán cần thiết để thực hiện phân tích nhân tố trên bất kỳ máy tính nào cũng đều tăng mạnh.

Nhiều giao thức mã hoá dựa trên sự khó khăn của việc phân tích các số nguyên lớn này hoặc một vấn đề liên quan - ví dụ như bài toán RSA. Một thuật toán hiệu quả phân tích các thừa số nguyên tố một số nguyên tùy ý sẽ khiến cho việc mã hóa sử dụng khóa công khai của RSA trở nên không an toàn.

Xem thêm

• Phân tích nhân tử
• Phân hoạch (lý thuyết số)

Sách tham khảo

• Richard Crandall và Carl Pomerance (2001). Prime Numbers: A Computational Perspective. Springer. ISBN 0-387-94777-9. Chapter 5: Exponential Factoring Algorithms, pp. 191–226. Chapter 6: Subexponential Factoring Algorithms, pp. 227–284. Section 7.4: Elliptic curve method, pp. 301–313.
• Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Section 4.5.4: Factoring into Primes, pp. 379–417.
• Samuel S. Wagstaff, Jr. (2013). The Joy of Factoring. Providence, RI: American Mathematical Society. ISBN 978-1-4704-1048-3..
• Warren Jr., Henry S. (2013). Hacker's Delight (ấn bản thứ 2). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8.

Liên kết ngoài

• msieve - SIQS and NFS - đã giúp hoàn thành một số các lần phân tích thừa số được công bố rộng rãi nhất
• Richard P. Brent, "Recent Progress and Prospects for Integer Factorisation Algorithms", Computing and Combinatorics", 2000, pp. 3–22. download
• Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P." Annals of Mathematics 160(2): 781-793 (2004). August 2005 version PDF
• Eric W. Weisstein, "RSA-640 Factored" MathWorld Headline News, ngày 8 tháng 11 năm 2005