Каков алгоритм нахождения "Простое ли число или составное" без поиска делителя? По математике интерес

Значит, придется использовать компьютер. Но тогда можно проверить и делители, компьютеру это не задача, а пшик, с его скоростью порядка миллиарда операций в секунду, тем более что проверять надо только делители до квадратного корня из числа. Существует несколько более короткий по времени вычисления для больших чисел "Общий метод решета числового поля", но он очень сложен по алгоритму.