Opensource

Factorization is a challenging math problem and an interesting application for Machine Understanding.

In number theory, integer factorization is the decomposition of a composite number n into a product of smaller integers. The hardest instances of factorization problems (for currently known techniques) are semiprimes, the product of two prime numbers, when they are both large, randomly chosen, and about the same size (but not too close).

The no-factor-base (NFB) approach to factorization is easy-to-understand and can be tried in combination with different known and new strategies of sieving quadratic residues modulo n to find the fastest solution. For example, it amends asymptotic complexity to L(2/5, 2) for the Dixon's and the quadratic sieve and to L(4/15, 2) for the general number field sieve and its analogs.

This FORTH interpreter with API to C/C++ was made in research on how to train combinatorial AI to program. Some of the motives for chosing FORTH were:

• very simple syntax for definition of new words (what's easy for kids is easy for AI as well),
• bottom-to-top programming style, which is in agreement with the approach to training from simple to complex,
• FORTH like any other interpreter is interactive, which makes it an interesting object for any AI training environment.

FORTH is a simple yet extensible language originally designed by Charles Moore. It features structured programming, reflection (the ability to examine and modify program structure during execution), concatenative programming. The modularity and extensibility of FORTH permit writing significant programs.