In the first version of the AKS primality test paper, a conjecture about Sophie Germain primes is used to lower the worst case complexity from O(log12n) to O(log6n).
Trong phiên bản đầu tiên của nghiên cứu phép kiểm tra tính nguyên tố AKS, một dự đoán về số nguyên tố Sophie Germain được sử dụng để giảm độ phức tạp của trường hợp xấu nhất từ O(log12n) giảm thành O(log6n).