What if $\sigma_0(n)$ could be computed efficiently? (Part 2)

In the first post regarding this topic, i sketched why an algorithm that counts the number of prime factors of an integer could lead to an algorithm that actually could factorize that integer. The application of such an algorithm to different number fields would lead to non-trivial information about the prime factors due to the definition of prime numbers in $\mathbb{Q}(\sqrt{d})$. The hope is, that this information would eventually allow us to reconstruct the entire prime numbers.

In this post i will show some basic facts about different number field and what information they leak about prime factors of $n$ if $\sigma_0(n)$ is known.

The l-Hensel Lifting Assumption

In one of my previous posts, i talked about the possibilities to insert backdoors in prime numbers (beside the property that $p-1$ is smooth). One of the potential ideas for a backdoor was to generate primes that allow an easy lift from $\mathbb{Z}/p$ to $\mathbb{Z}/{p^2}\mathbb{Z}$. But under the consideration of the $l$-Hensel Discrete Logarithm Assumption, this should be actually hard in the general case.

Because if you could successfully lift the element $e\equiv g^x\pmod{p}$ to $E\equiv g^x\pmod{p^2}$, then you could, as long as $x < \mathsf{ord}_p(g) = r$, compute
\begin{align*}
\left(g^x\right)^{r} \equiv (g^{r})^x \equiv (1+p\lambda)^x \pmod{p^2}
\end{align*}
Next, the Binomial Theorem gives
\begin{align*}
(1+p\lambda)^x \equiv \sum^x_{i=0}\binom{x}{i}p^i\lambda^i \equiv 1 + xp\lambda\pmod{p^2}
\end{align*}
and hence
\begin{align*}
\frac{E^{r} - 1}{p\lambda} \equiv x \pmod{p}
\end{align*}

What if $\sigma_0(n)$ could be computed efficiently?

What would be the consequences if the sum of divisors function with $k=0$ could be computed efficiently, that is polynomial in $\log (n)$ if $n$ is the input to $\sigma_0(n)$? Note that if $n=p_1^{e_1}p_2^{e_2}...p_m^{e_m}$ then $$\sigma_0(n) = \sum_{d|n} d^0 =  \sum_{d|n} 1 = (e_1+1)(e_n+1)...(e_m+1)$$ For square-free numbers $n$, this is always a power of $2$, hence $\log_2(\sigma_0(n))$ gives the number of prime factors in this case. Furthermore, the famous AKS-algorithm gives a deterministic polynomial time algorithm, that decides if $\sigma_0(n) = 2$ or not, i.e. $n$ is prime or composite.

For the general case, Terence Tao gave an heuristic argument that generally this should be as hard as factoring a number:

"There is a folklore observation that if one was able to quickly count the number of prime factors of an integer n, then one would likely be able to quickly factor n completely. So the counting-prime-factors  problem is believed to have comparable difficulty to factoring itself."

Backdooring Discrete Logarithms in $\mathbb{Z}^*_p$

In one of my previous post, i talked about the (potential) backdoor in the pseudo random number generator described in SP800-90 Dual Ec PRNG. The backdoor could be exploited by the usage of some perhaps existing secret relation among two given constants.

The concept of elliptic curves cryptography and its whole theory is much more complicated than the cryptography based on the finite fields $\mathbb{F}_p$ for a large prime number $p$. Implementing a backdoor in that case seems to be harder. Some people indeed say, that we should switch back to the good old fields $\mathbb{Z}^*_p$ to increase the confident in our systems.

Learning a Sine-Wave

A few month ago, i locked up myself into a mental hole, by trying to solve or at least partially solve the following problem:

Problem-Definition. Assume you have a sufficient long integer interval $I=[0,n]$ and a set $Z$ that consists of tuples $(x,s(x))$, with $x \in_R I$ and $s(x) = \mathsf{sign}(\sin(2x\pi/p))$. Formulated in words, the set $Z$ contains the randomly distributed integers from $I$ enriched with the information if a certain (but fixed) sinus wave travels above or below that point (i.e., the sign value). Find the secret parameter $p$.

# Heuristic argument #

It can be heuristically proved, that even as few as $m =\log p$ points should be enough to find a unique value for $p$. Imagine a random sine wave that is plotted along the interval $I$. Since the points $x_i$ are randomly chosen from $I$, the chance that a point $x_i$ is traversed by the sine wave equal to its assigned sign value is $1/2$. Hence, the chances that a random curves traverses all $m$ points correct is $(1/2)^m$.

But it seems one can not do better than $\mathcal{O}(p)$, that is exponential in $m$.

Sum of Divisors Function - Euler's recursion

Number theory has many functions that are based on the arithmetical properties of a given input integer $n$. These functions are called number-theoretic functions. Well known examples are, e.g., the Euler's Totient Function and The Möbius Function. Since arithmetical properties often depend in one or the other way on the integer's prime factorization, these functions are usually hard to compute for large integers due to the factorization problem. One of these functions, that heavily depends on that factorization, is the Divisor Function.

Definition [Divisor Function] Given an integer $n$ then the divisor function $\sigma_k(n)$ is defined as $$ \sigma_k(n) := \sum_{d|n}d^k$$

Infinite Regular Primes Conjecture

Another unproven conjecture in number theory is the Infinite Regular Primes Conjecture (IRPC). A regular prime can be characterised in more than one way.

Definition [Regular Prime]. A prime \(p > 2\) is called regular if it does not divide the class number of the \(p\)-th cyclotomic field $\blacktriangleleft$.

An alternative characterisation is the following.

Definition [Regular Prime]. A prime \(p > 2\) is called regular if it does not divide the numerator of any Bernoulli number \(B_n\) for \(n = 2,4,6,...,p-3\) $\blacktriangleleft$.

Then the IRPC conjecture simply this:

[Infinite Regular Primes Conjecture] There are infinite many regular prime.

Kummer proved in 1850 that Fermat's Last Theorem is true if the involved exponent $p$ is regular.

If there are regular primes, it is not hard to guess that there are also irregular primes. Their infiniteness as already been proved several decades ago (1954)  by Carlitz [1]. His proof is based on the second characterisation. It is a proof by contradiction; he assumes that there are only finite many irregular primes, which leads him to a contradiction to some proved result about Bernoulli numbers.

The Agoh-Giuga Conjecture

Number theory accommodates a lot of conjectures and a lot of them resist proof attempts since many years or even decades. Most of them have to do with prime numbers and its behaviour. 

One of those conjectures is the Agoh-Giuga Conjecture (AGC). Actually, it was Guiseppe Giuga who formulated the conjecture in 1950 and Takasi Agoh reformulated it 40-years later.

The original statement from Giuga was the following:

[Agoh-Giuga-Conjecture] The integer \(p\) is a prime number if and only if $$\sum^{p-1}_{k=1}k^{p-1} \equiv -1\pmod{p}$$

and the reformulation due to Agoh is

[Agoh-Giuga-Conjecture] The integer \(p\) is a prime number if and only if $$pB_{p-1} \equiv -1\pmod{p}$$

It is not hard to show that these two formulations are actually equal.

Characterising integer tuples by co-prime nearby integers (Part 1)

The Chinese Remainder Theorem is a beautiful tool if someone wants to characterise a large integer \(N\) via a set \(\mathcal{B} = \{n_1,...,n_m\}\) of small integers. Based in the remainders \(\{N\pmod{n_1},...,N\pmod{n_2}\} = \{r_1,...,r_m\}\) one can reconstruct the unique integer \(N\pmod{\prod^m_{i=1}n_i}\), which is \(N\) itself if \(N \leq \prod^m_{i=1}n_i\).

What i want to discuss in this post is, if it is possible to characterise a tuple of integers \(N_1,N_2\) via their co-prime neighbors. For example:

Suppose we have \(N_1\) and \(N_2\), which are two unknown integers. All it is known, is that
$$\gcd(N_1+s_i,N_2+t_i) = 1$$
for integers \(s_i\) and \(t_i\), \(i \leq k\). These \(s_i\) and \(t_i\) could be small, i.e., 2, 3 or 5 but also any other integer. The question is:

Given the set \(\mathcal{S} = \{(s_1,t_1),...,(s_k,t_k)\}\), is it possible to say anything non trivial about the integers \(N_1\) or \(N_2\)?

If this would be possible, one could, e.g., use this information to help to factorize integers. The relationship is the following:

Lemma 1. Let \(n = pq\) and \(p,q \in \mathbb{P}\) and let \(p = gm_1+d_1\) and \(q = gm_2+d_2\) with \(\gcd(m_1,m_2) = 1\). Let \(n-d_1d_2 = t\). If \( t > \sqrt{n}\) and \(t \in \mathbb{P}\) than \(g = 1\), hence \(p-d_1\) and \(q-d_2\) are co-prime integers.