Khác biệt giữa bản sửa đổi của “Số nguyên tố”

Cho một hợp số <math>n</math>, công việc xuất ra một (hoặc tất cả) thừa số nguyên tố được gọi là ''phân tích'' của <math>n</math>. Công việc này khó hơn đáng kể so với kiểm tra tính nguyên tố,<ref>{{Harvnb|Kraft|Washington|2014|p=275}}</ref> và mặc dù tồn tại nhiều thuật toán phân tích nhưng chúng đều chậm hơn so với các phương pháp nhanh nhất để kiểm tra tính nguyên tố. Giải thuật chia thử và [[thuật toán RHO]] có thể được dùng để tìm các nhân tử rất nhỏ của <math>n</math>,<ref name=":7" /> và thuật toán [[Phân tích số nguyên bằng đường elip|phân tích bằng đường cong elliptic]] có thể hiệu quả khi <math>n</math> có các nhân tử lớn vừa phải.<ref>{{chú thích sách|url=https://books.google.com/books?id=cbl_BAAAQBAJ&pg=PA329|title=An Introduction to Mathematical Cryptography|last1=Hoffstein|first1=Jeffrey|last2=Pipher|first2=Jill|last3=Silverman|first3=Joseph H.|publisher=Springer|year=2014|isbn=978-1-4939-1711-2|edition=2nd|series=Undergraduate Texts in Mathematics|location=|page=329|pages=|ref=harv}}</ref> Một số phương pháp phù hợp đối với số lớn bất kỳ không phụ thuộc vào độ lớn của nhân tử bao gồm [[sàng cấp hai]] và [[sàng trường số thông thường]]. Giống như kiểm tra tính nguyên tố, có một số thuật toán phân tích yêu cầu đầu vào có dạng đặc biệt, trong đó có [[sàng trường số đặc biệt]].<ref>{{chú thích tạp chí|last=Pomerance|first=Carl|date=|year=1996|title=A tale of two sieves|url=|journal=Notices of the American Mathematical Society|volume=43|issue=12|pages=1473–1485|mr=1416721|via=}}</ref> Tính đến tháng 2 năm 2020 [[Kỷ lục phân tích số nguyên|số lớn nhất được phân tích]] bằng một thuật toán thông thường là [[Số RSA|RSA-250]], một số có 250 chữ số (829 bit) và là tích của hai số nguyên tố lớn.<ref>{{Chú thích danh sách thư|url=https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2020-February/001166.html|title=Factorization of RSA-250|access-date = ngày 3 tháng 8 năm 2020 |first=Paul|last=Zimmermann|date = ngày 28 tháng 2 năm 2020 |mailinglistmailing-list=cado-nfs-discuss}}</ref>