{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,10]],"date-time":"2025-12-10T16:01:24Z","timestamp":1765382484158,"version":"3.28.0"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,2,21]],"date-time":"2024-02-21T00:00:00Z","timestamp":1708473600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,2,21]],"date-time":"2024-02-21T00:00:00Z","timestamp":1708473600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Big Data"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The M\u00f6bius function<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mu (n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>\u03bc<\/mml:mi><mml:mo>(<\/mml:mo><mml:mi>n<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>is known for containing limited information on the prime factorization of<jats:italic>n<\/jats:italic>. Its known algorithms, however, are all based on factorization and hence are exponentially slow on<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\log n$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mo>log<\/mml:mo><mml:mi>n<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Consequently, a faster algorithm of<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mu (n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>\u03bc<\/mml:mi><mml:mo>(<\/mml:mo><mml:mi>n<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>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<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mu (n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>\u03bc<\/mml:mi><mml:mo>(<\/mml:mo><mml:mi>n<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>using random forests and neural networks, harnessing the additive properties of<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mu (n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>\u03bc<\/mml:mi><mml:mo>(<\/mml:mo><mml:mi>n<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. The machine learning models are trained on a substantial dataset with 317,284 observations (80%), comprising five feature variables, including values of<jats:italic>n<\/jats:italic>within the range of<jats:inline-formula><jats:alternatives><jats:tex-math>$$4\\times 10^9$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mn>4<\/mml:mn><mml:mo>\u00d7<\/mml:mo><mml:msup><mml:mn>10<\/mml:mn><mml:mn>9<\/mml:mn><\/mml:msup><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. 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.<\/jats:p>","DOI":"10.1186\/s40537-024-00889-7","type":"journal-article","created":{"date-parts":[[2024,2,21]],"date-time":"2024-02-21T16:02:21Z","timestamp":1708531341000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Algorithms of the M\u00f6bius function by random forests and neural networks"],"prefix":"10.1186","volume":"11","author":[{"given":"Huan","family":"Qin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yangbo","family":"Ye","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,2,21]]},"reference":[{"issue":"2","key":"889_CR1","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1145\/359340.359342","volume":"21","author":"RL Rivest","year":"1978","unstructured":"Rivest RL, Shamir A, Adlemany L. A method for obtaining digital signatures and public-key cryptography. Comm ACM. 1978;21(2):120\u20136.","journal-title":"Comm ACM"},{"key":"889_CR2","unstructured":"Sarnak P. Three lectures on the M\u00f6bius function randomness and dynamics. Institute for Advanced Study. 2011. https:\/\/www.math.ias.edu\/files\/wam\/2011\/PSMobius.pdf. Last retrieved on February 4, 2024."},{"issue":"2","key":"889_CR3","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1215\/00127094-2856619","volume":"164","author":"AR Booker","year":"2015","unstructured":"Booker AR, Hiary GA, Keating JP. Detecting squarefree numbers. Duke Math J. 2015;164(2):235\u201375.","journal-title":"Duke Math J"},{"issue":"7887","key":"889_CR4","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1038\/s41586-021-04086-x","volume":"600","author":"A Davies","year":"2021","unstructured":"Davies A, Veli\u010dkovi\u0107 P, Buesing L, Blackwell S, Zheng D, Toma\u0161ev N, et al. Advancing mathematics by guiding human intuition with AI. Nature. 2021;600(7887):70\u20134.","journal-title":"Nature"},{"issue":"7","key":"889_CR5","doi-asserted-by":"publisher","DOI":"10.1088\/1751-8121\/abbc4f","volume":"54","author":"YH He","year":"2021","unstructured":"He YH, Hirst E, Peterken T. Machine-learning dessins d\u2019enfants: explorations via modular and Seiberg-Witten curves. J Phys A Math Theor. 2021;54(7): 075401.","journal-title":"J Phys A Math Theor"},{"key":"889_CR6","doi-asserted-by":"publisher","DOI":"10.1016\/j.physletb.2022.136966","volume":"827","author":"J Bao","year":"2022","unstructured":"Bao J, He YH, Hirst E, Hofscheier J, Kasprzyk A, Majumder S. Hilbert series, machine learning, and applications to physics. Phys Lett B. 2022;827: 136966.","journal-title":"Phys Lett B"},{"key":"889_CR7","unstructured":"Bao J, He YH, Hirst E, Hofscheier J, Kasprzyk A, Majumder S. Polytopes and machine learning. arXiv preprint. 2021. arXiv:2109.09602."},{"key":"889_CR8","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.jsc.2021.11.002","volume":"111","author":"YH He","year":"2022","unstructured":"He YH, Lee KH, Oliver T. Machine-learning the Sato-Tate conjecture. J Sym Comput. 2022;111:61\u201372.","journal-title":"J Sym Comput"},{"key":"889_CR9","unstructured":"Lample G, Charton F. Deep learning for symbolic mathematics. arXiv preprint. 2019. arXiv:1912.01412."},{"key":"889_CR10","unstructured":"Vaswani A, Shazeer N, Parmar N, Uszkoreit J, Jones L, Gomez AN, et\u00a0al. Attention is all you need. Adv Neural Inform Process Syst. 2017;30."},{"key":"889_CR11","unstructured":"Charton F. Can transformers learn the greatest common divisor? arXiv preprint. 2023. arXiv:2308.15594."},{"key":"889_CR12","first-page":"34981","volume":"35","author":"E Wenger","year":"2022","unstructured":"Wenger E, Chen M, Charton F, Lauter KE. Salsa: attacking lattice cryptography with transformers. Adv Neural Inform Process Syst. 2022;35:34981\u201394.","journal-title":"Adv Neural Inform Process Syst"},{"issue":"12","key":"889_CR13","first-page":"1473","volume":"43","author":"C Pomerance","year":"1996","unstructured":"Pomerance C. A tale of two sieves. Not Amer Math Soc. 1996;43(12):1473\u201385.","journal-title":"Not Amer Math Soc"},{"key":"889_CR14","unstructured":"Luo Q, Ye Y. Distribution of neighboring values of the Liouville and M\u00f6bius functions. arXiv preprint. 2024; arXiv:2401.18082."},{"key":"889_CR15","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1093\/qmath\/os-3.1.273","volume":"3","author":"L Carlitz","year":"1932","unstructured":"Carlitz L. On a problem in additive arithmetic II. Quart J Math. 1932;3:273\u201390.","journal-title":"Quart J Math"},{"issue":"1","key":"889_CR16","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1112\/S0025579300012110","volume":"29","author":"RR Hall","year":"1982","unstructured":"Hall RR. Square-free numbers on short intervals. Mathmatika. 1982;29(1):7\u201317.","journal-title":"Mathmatika"},{"key":"889_CR17","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/BF01475576","volume":"266","author":"DR Hearth-Brown","year":"1984","unstructured":"Hearth-Brown DR. Square sieve and consecutive square-free numbers. Math Ann. 1984;266:251\u20139.","journal-title":"Math Ann"},{"key":"889_CR18","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1112\/S0025579300011049","volume":"32","author":"KM Tsang","year":"1985","unstructured":"Tsang KM. The distribution of $$r$$-tuples of square-free numbers. Mathematika. 1985;32:265\u201375.","journal-title":"Mathematika"},{"key":"889_CR19","volume-title":"The Riemann Hypothesis and Hilbert\u2019s Tenth Problem","author":"S Chowla","year":"1965","unstructured":"Chowla S. The Riemann Hypothesis and Hilbert\u2019s Tenth Problem. New York: Gordon and Breach; 1965."},{"issue":"9","key":"889_CR20","doi-asserted-by":"publisher","first-page":"2167","DOI":"10.2140\/ant.2015.9.2167","volume":"9","author":"K Matom\u00e4ki","year":"2015","unstructured":"Matom\u00e4ki K, Radziwi M, Tao T. An averaged form of Chowla\u2019s conjecture. Alg Number Theor. 2015;9(9):2167\u201396.","journal-title":"Alg Number Theor"},{"issue":"1","key":"889_CR21","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1023\/A:1010933404324","volume":"45","author":"L Breiman","year":"2001","unstructured":"Breiman L. Random forests. Mach Learn. 2001;45(1):5\u201332.","journal-title":"Mach Learn"},{"key":"889_CR22","volume-title":"An introduction to statistical learning with application in R (springer texts in statistics)","author":"G James","year":"2017","unstructured":"James G, Witten D, Hastie T, Tibshirani R. An introduction to statistical learning with application in R (springer texts in statistics). New York: Springer; 2017."},{"key":"889_CR23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-56485-8","volume-title":"Random Forests with R (Use R!)","author":"R Genuer","year":"2020","unstructured":"Genuer R, Poggi JM. Random Forests with R (Use R!). Cham: Springer Nature; 2020."},{"issue":"4","key":"889_CR24","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1080\/00031305.1996.10473554","volume":"50","author":"B Warner","year":"1996","unstructured":"Warner B, Misra M. Understanding neural networks as statistical tools. Amer Stat. 1996;50(4):284\u201393.","journal-title":"Amer Stat"},{"issue":"1","key":"889_CR25","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1613\/jair.953","volume":"16","author":"NV Chawla","year":"2002","unstructured":"Chawla NV, Bowyer KW, Hall LO, Kegelmeyer WP. SMOTE: synthetic minority over-sampling technique. J Artif Intell Res. 2002;16(1):321\u201357.","journal-title":"J Artif Intell Res"},{"issue":"5","key":"889_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.18637\/jss.v028.i05","volume":"28","author":"M Kuhnm","year":"2008","unstructured":"Kuhnm M. Building predictive model in R using the caret package. J Stat Softw. 2008;28(5):1\u201326. https:\/\/doi.org\/10.18637\/jss.v028.i05.","journal-title":"J Stat Softw"},{"issue":"3","key":"889_CR27","first-page":"18","volume":"2","author":"A Liaw","year":"2002","unstructured":"Liaw A, Wiener M. Classification and Regression by randomForest. R News. 2002;2(3):18\u201322.","journal-title":"R News"},{"key":"889_CR28","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-21706-2","volume-title":"Modern applied statistics with S","author":"WN Venables","year":"2002","unstructured":"Venables WN, Ripley BD. Modern applied statistics with S. New York: Springer; 2002."},{"key":"889_CR29","unstructured":"Kumar P. Computational complexity of ML models. December 4, 2019 https:\/\/medium.com\/analytics-vidhya\/time-complexity-of-ml-models-4ec39fad2770. Last retrieved on February 4, 2024."},{"issue":"1","key":"889_CR30","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1145\/174644.174647","volume":"41","author":"M Kearns","year":"1994","unstructured":"Kearns M, Valiant L. Cryptographic limitations on learning Booleann formulae and finite automata. J ACM. 1994;41(1):67\u201395.","journal-title":"J ACM"},{"key":"889_CR31","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational complexity a modern approach","author":"S Arora","year":"2009","unstructured":"Arora S, Barak B. Computational complexity a modern approach. New York: Cambridge University Press; 2009."},{"issue":"8","key":"889_CR32","doi-asserted-by":"publisher","first-page":"861","DOI":"10.1016\/j.patrec.2005.10.010","volume":"27","author":"T Fawcett","year":"2006","unstructured":"Fawcett T. An introduction to ROC analysis. Pattern Recognit Lett. 2006;27(8):861\u201374.","journal-title":"Pattern Recognit Lett"}],"container-title":["Journal of Big Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s40537-024-00889-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s40537-024-00889-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s40537-024-00889-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,12]],"date-time":"2024-11-12T03:50:09Z","timestamp":1731383409000},"score":1,"resource":{"primary":{"URL":"https:\/\/journalofbigdata.springeropen.com\/articles\/10.1186\/s40537-024-00889-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,21]]},"references-count":32,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2024,12]]}},"alternative-id":["889"],"URL":"https:\/\/doi.org\/10.1186\/s40537-024-00889-7","relation":{},"ISSN":["2196-1115"],"issn-type":[{"type":"electronic","value":"2196-1115"}],"subject":[],"published":{"date-parts":[[2024,2,21]]},"assertion":[{"value":"27 July 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 January 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 February 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests in this study.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"31"}}