Score:6

Why can't we use the Zeta function to search for prime factors in RSA?

cn flag

Maybe I got this wrong, but if the Zeta function is efficient to compute and reverse, and if Riemann's assumption is true (which it seems like), can't we use the Zeta function to efficiently find prime factors of large numbers and find private keys of public RSA keys?

kelalaka avatar
in flag
Welcome to Cryptography.se. What do you mean by _efficient to compute and reverse_?
stimulate avatar
cn flag
@kelalaka efficient to compute: basically computable in less than exponential time respective to the prime we are searching; reverse: efficient to find the input to zeta for a given prime number.
Score:11
ru flag

Firstly, I don't think that $\zeta(s)$ is that efficient to compute. Our interest in calculating $\zeta(s)$ for prime number theoretic purposes typically focuses on the critical line $\mathrm{Re}s=1/2$ and the Riemann-Siegel formula requires $O(t^{1/2})$ terms to compute $\zeta(1/2+it)$. There are speed-ups for calculating multiples values, but not dramatically so.

Likewise, I'm not sure what you mean by reverse. The function is not bijective (we know many places where it is zero for example).

That said, there have been some ideas around using analytic number theory for factoring methods. Shanks's class group factorisation method can be sped up if one can approximate $L(1,\chi_N)$ (here the $L$-function is for the number field $\mathbb Q(\sqrt N)$ and is closely related to $\zeta(s)$. Assuming the generalised Riemann hypothesis, Shanks managed to reduce the run time of his algorithm to factor $N$ from $O(N^{1/4+\epsilon})$ to $O(N^{1/5+\epsilon})$. Such complexity is unlikely to factor numbers bigger than a few hundred bits and cannot compete with the general number field sieve.

There have been ideas to use $\zeta(s)$ itself (see the recent paper "Factoring with hints" by Sica for example), but these struggle to get close to the complexity of Shanks's methods of the 1970s (the Sica paper has complexity $O(N^{1/3+\epsilon})$.)

Score:4
us flag

Can't we use the Zeta function to efficiently find prime factors of large numbers and find private keys of public RSA keys

In short: The $\zeta$ function doesn't give access to individual prime numbers (I don't know of any formula which does), so even if we have a super-fast computation method, it can't be used to find prime numbers.


  • What the $\zeta$ function gives access to, is for example the number of prime numbers between $1$ and $x$, i.e. the prime-counting function $\pi(x)$.

    There is indeed a relation between the prime-counting function $\pi(x)$, and all the zeros $\rho$ of the Riemann $\zeta$ function:

    $$\psi _{0}(x)=x-\sum _{\rho }{\frac {x^{\rho }}{\rho }}-\ln 2\pi -{\frac 12}\ln(1-x^{{-2}}).$$

    Here think of $\psi_0(x)$ as something very close to $\pi(x)$ in the idea, but it just counts the prime numbers with another weight than $1$ for each prime, instead the weight is $\log p$. This is omitting details, but it gives the idea. See here for more precisions.

  • The Euler product for the $\zeta$ function involves all prime numbers, but doesn't give an effective way to generate / find prime numbers:

    $$\zeta(s) = \sum _{n=1}^{\infty }{\frac {1}{n^{s}}}=\prod _{p{\text{ prime}}}{\frac {1}{1-p^{-s}}}$$

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.