Lý thuyết số tính toán

Trong toán học và khoa học máy tính, lý thuyết số tính toán, còn được gọi là lý thuyết số thuật toán, là nghiên cứu về các thuật toán để thực hiện tính toán lý thuyết số. Mục đích của lý thuyết số tính toán là nghiên cứu thuật toán phù hợp nhất từ lý thuyết số.

Thuật toán

Có nhiều thuật toán trong lý thuyết số tính toán. Sau đây là một số thuật toán và độ phức tạp của chúng:

Phép nhân

Giới hạn dưới cho độ phức tạp tính toán của phép nhân đã là một trọng tâm kể từ khi máy tính đầu tiên xuất hiện. Thuật toán nhân chuẩn có độ phức tạp O(n²), nhưng độ phức tạp thời gian từ lâu đã được phỏng đoán là O(nlog (n)), điều này đã được chứng minh vào năm 2019.^[1]

Phép lũy thừa

Giống như phép nhân, phép lũy thừa đã là một mục tiêu cho lý thuyết số. Nếu chúng ta cố gắng tính toán một phép toán theo cấp số nhân với phép nhân liên tiếp, chúng ta sẽ có một độ phức tạp giống như phép nhân với thuật toán tiêu chuẩn (O(n²)). Để cải thiện điều này, chúng ta có thể sử dụng thuật toán nhân và giảm lặp lại. Với điều này, chúng ta giảm độ phức tạp xuống O (M(n)2^k). Các thuật toán khác là lũy thừa bằng cách bình phương hoặc hạ bậc Montgomery làm giảm độ phức tạp thành O (M (n)k).

Kiểm tra số nguyên tố

Một phần rất quan trọng của lý thuyết số tính toán là phép kiểm tra xem một số có là số nguyên tố hay không. Điều này có thể khó khăn vì nó đòi hỏi một lượng lớn năng lượng máy tính để chứng minh tính nguyên tố của một số nguyên dương lớn.

Một thuật toán dễ dàng hơn để giúp xác định nếu một số là số nguyên tố là một phép chia liên tiếp cho tất cả các số thấp hơn của nó. Nếu chúng ta khởi hành từ đó, phép chia chuẩn sẽ có độ phức tạp là O (n²). Nếu chúng ta muốn biết nếu một số n là số nguyên tố thì độ phức tạp toàn cầu là O (n×n²). Để cải thiện điều này, chúng ta có thể áp dụng phép kiểm tra tính nguyên tố AKS và nếu chúng ta áp dụng giả thuyết Agrawal, thì độ phức tạp là O ((log n)³); nếu không dựa vào giả thuyết này, việc kiểm tra sẽ có độ phức tạp là O ((log n)⁶).

Giai thừa số nguyên

Giai thừa n là tích của tất cả các số nguyên dương từ 1 đến n. Với phép nhân liên tiếp, giai thừa có thể tính bằng cách sử dụng độ phức tạp của O (n × n²⁾). Với thuật toán nhân từ dưới lên, độ phức tạp này có thể giảm xuống O (M(m²) log m).

Tham khảo

1. https://hal.archives-ouvertes.fr/hal-02070778/document