Algorithms of the Möbius function by random forests and neural networks
Huan Chang Qin, Yangbo Ye · Journal Of Big Data · 2024
Abstract The Möbius function $$\mu (n)$$ μ(n) is known for containing limited information on the prime factorization ofn. Its known algorithms, however, are all based on factorization and hence are exponentially slow on $$\log n$$ logn . 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 ofnwithin the range of $$4\times 10^9$$ 4×109 . 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.