Простые числа в P - как насчет работы до sqrt?

Question

Я учусь о P а также NP,
Я читал, что проблема решения, является ли данное число простым, является проблемой в P, что означает, что у него есть алгоритм полиномиального времени, который решает его.
Я также читал, что этот факт был доказан в 2002 году по алгоритму АКС.

Как мы все знаем, мы можем решить, является ли конкретное число простым, работая до его квадратного корня.

псевдокод:

isPrime(N):

sqrt(N) <- squareRoot(N)

for i from 2 to Sqrt(N)
    if (n mod i == 0)
        return false
return true

Мой вопрос прост:
Почему приведенный выше алгоритм не доказывает, что эта проблема в P?
Спасибо:)

Answer 1

Является ли алгоритм полиномиальным временем, зависит от представления входных данных. Например, большое число 9223372036854775807 подходит для 64-разрядного типа без знака. Значение результата AKS заключается в том, что он является полиномиальным по количеству битов (например, 64), а не по самому числу (например, 9223372036854775807).