Hỏi cách kiểm tra bignum có phải số nguyên tố hay không

[VDuy_Le]

Cho em hỏi cách kiểm tra bignum có phải số nguyên tố hay ko làm theo hướng nào ạ

[rogp10]

Dễ nhất là bạn dùng pseudoprimality test với độ tin cậy rất cao (test Fermat có 1 dạng số toàn xịt, không thể sử dụng)

Một bộ test pseudo đáng tin cậy kết hợp nhiều dạng kiểm tra khác nhau cho mỗi đặc điểm của số nguyên tố, cực kì hiếm có một hợp số nào thỏa tất cả những điều kiện như vậy.

note

Nếu muốn chắc ăn và bạn tin giả thuyết Riemann thì có thể chạy RM đến 2(ln(n))^2 là đủ.