6
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ Welcome to Cryptography.se. What do you mean by efficient to compute and reverse? $\endgroup$
    – kelalaka
    Dec 15 '21 at 22:20
  • $\begingroup$ @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. $\endgroup$
    – stimulate
    Dec 16 '21 at 22:06
4
$\begingroup$

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}}}$$

$\endgroup$
11
$\begingroup$

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})$.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.