Direct and inverse factorization algorithms of numbers - Melničenko, Grigorijus (Lietuvos matematikos rinkinys, 2019)
The factoring natural numbers into factors is a complex computational task. The complexity of solving this problem lies at the heart of RSA security, one of the most famous cryptographic methods. The classical trial division algorithm divides a given number N into all divisors, starting from 2 and to integer part of √N. Therefore, this algorithm can be called the direct trial division algorithm. We present the inverse trial division algorithm, which divides a given number N into all divisors,starting from the integer part of √N to 2.
Keywords: prime numbers; trial division; Fermats factorization algorithm