Одно из требований дляАутентификация Telegram разлагает данное число на 2 простых кофактора. ОсобенноP*Q = N, where N < 2^63

Как мы можем найти меньший простой кофактор, такой, чтоP < square_root(N)

Мои предложения:

1) предварительно вычислить простые числа от 3 до2^31.5, а затем проверить, еслиN mod P = 0

2) Найти алгоритм для тестирования простых чисел (но мы все еще должны проверитьN mod P =0)

Есть ли алгоритм для простых чисел, который хорошо подходит для этого случая?