Algorithms of the Möbius function by random forests and neural networks

Abstract

Abstract The Möbius function $$\mu (n)$$ μ ( n ) is known for containing limited information on the prime factorization of n. Its known algorithms, however, are all based on factorization and hence are exponentially slow on $$\log n$$ log n . Consequently, a faster algorithm of $$\mu (n)$$ μ ( n ) could potentially lead to a fast algorithm of prime factorization which in turn would throw doubt upon the security of most public-key cryptosystems. This research introduces novel approaches to compute $$\mu (n)$$ μ ( n ) using random forests and neural networks, harnessing the additive properties of $$\mu (n)$$ μ ( n ) . The machine learning models are trained on a substantial dataset with 317,284 observations (80%), comprising five feature variables, including values of n within the range of $$4\times 10^9$$ 4 × 10 9 . We implement the Random Forest with Random Inputs (RFRI) and Feedforward Neural Network (FNN) architectures. The RFRI model achieves a predictive accuracy of 0.9493, a recall of 0.5865, and a precision of 0.6626. On the other hand, the FNN model attains a predictive accuracy of 0.7871, a recall of 0.9477, and a precision of 0.2784. These results strongly support the effectiveness and validity of the proposed algorithms.

Keywords

• The Möbius function
• The algorithm of the Möbius function
• Machine learning
• Random forests
• Neural networks