Open AccessDirect and inverse factorization algorithms of numbers
Author(s) -
Grigorijus Melničenko
Publication year - 2019
Publication title -
lietuvos matematikos rinkinys
Language(s) - English
Resource type - Journals
eISSN - 2335-898X
pISSN - 0132-2818
DOI - 10.15388/lmr.b.2019.15234
Subject(s) - integer factorization , division (mathematics) , integer (computer science) , mathematics , algorithm , inverse , cryptography , factorization , natural number , arithmetic , discrete mathematics , computer science , public key cryptography , encryption , geometry , programming language , operating system
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.