“The article talks about a recent paper[1] by one of the interviewees that uses McMahon partition functions for primality testing. I wonder how its running time of compares to that of the AKS primality test, and something more practical like BPSW.[2] Could it find an application in practical cryptography? 1. https://arxiv.org/abs/2405.06451v2 2. https://…”
Integer partitions detect the primes
We show that integer partitions, the fundamental building blocks in additive number theory, detect prime numbers in an unexpected way. Answering a question of Schneider, we show that the primes are the solutions to special equations in partition functions. For example, an integer $n\geq 2$ is prime if and only if $$ (3n^3 - 13n^2 + 18n - 8)M_1(n) + (12n^2 - 120n + 212)M_2(n) -960M_3(n) = 0, $$ where the $M_a(n)$ are MacMahon's well-studied partition functions. More generally, for "MacMahonesque" partition functions $M_{\vec{a}}(n),$ we prove that there are infinitely many such prime detecting equations with constant coefficients, such as $$ 80M_{(1,1,1)}(n)-12M_{(2,0,1)}(n)+12M_{(2,1,0)}(n)+\dots-12M_{(1,3)}(n)-39M_{(3,1)}(n)=0. $$
候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。
HN 书评
推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及“Hello! I came across this new paper, INTEGER PARTITIONS DETECT THE PRIMES [1] from July, 2024, but I don't have enough knowledge to even read it. I wonder if an implementation of this method would provide any speed benefits compared to PRP. Great work! [1] https://arxiv.org/pdf/2405.06451”
“The M functions are the MacMahon’s partition functions (see the paper [1]). They were not known to relate to the sum of divisors. The M_a function counts partitions in a parts but weighing multiplicities in the partion. [1]: https://arxiv.org/abs/2405.06451”