Độ phức tạp của phép thử tính nguyên tố Rabin-Miller

Tôi đang nghĩ về sự phức tạp của bài kiểm tra tính nguyên tố Rabin-Miller. Trên wikipedia tôi tìm thấy O(k log3n), nhưng không có lời giải thích. Ý tưởng của tôi quá đơn giản. Để xem n có phải là số nguyên tố hay không, chúng ta có k lần thử và với mỗi lần thử, chúng ta kiểm tra xem phần tử đầu tiên b có phải là 1 hay không, nếu không, chúng ta sẽ tìm -1 trong dãy b. Ở đây b = a^u mod n và n-1 = 2^l * u, u lẻ, với (b,b^2^1,b^2^2,b^2^3,...,b^ 2^(l-1)). Vì vậy, tôi giả sử trường hợp xấu hơn, chúng tôi tính toán đến tận số mũ cuối cùng, ngay trước khi chúng tôi đạt đến số nguyên tố cực đại thực tế. Vì vậy, nếu chúng ta có thể biểu diễn n-1 = 2^lu với u lẻ, thì chúng ta cần tổng cộng k*(n-1)/(2u) bước.