Methods to compute the class number

The class number is an important term from algebraic number theory. It specifies the order of the class group of an algebraic number field $K$ and can be interpreted as the number of different ways to factorize an element of $K$ into prime elements. If the class number is equal to $1$, the $K$ is called a unique factorization domain, e.g. the integers $\mathbb{Z}$. It is long known that for imaginary quadratic fields the class number is $1$ only for the values: $$K = \mathbf{Q}(\sqrt{d}), d \in \{-1,-2,-3,-7,-11,-19,-43,-67,-163\}$$ There are a surprisingly large number of ways to compute the class number of a quadratic field, which i want to show you next.

On Giuga Numbers

In number theory, certain numbers are sometimes given special names if their prime factorisations have a special property. For an integer $n$, a divisor $d$ is called a proper divisor as long as $d < n$. Also $1$ is a proper divisor in this case. This gives us the following examples:

1. Prime Numbers: An integer $n$ with only one proper divisor.
2. Perfect Numbers (also Deficient / Abundant Numbers): An integer $n$ such that the sum of all its proper divisors is equal to $n$. (Deficient $< n$; Abundant $> n$).
3. Carmichael Numbers : An integer $n$ such that $(p-1) | (n/p-1)$ for each prime factor $p$ of $n$
4. Giuga Numbers : An integer $n$ such that $p | (n/p-1)$ for each prime factor $p$ of $n$

To 1.) It is known since Euclid that there are infinite many prime numbers. 

To 2.) It is not known if there are infinite many perfect numbers nor is know if there exists a single odd perfect number since all currently known perfect numbers are even e.g., $6 = 1\cdot 2\cdot 3 = 1+2+3=6$ or $28 = 1\cdot 2^2\cdot 7 = 1 + 2 + 4 + 7 + 14 = 28$. The total number of known perfect numbers is 49.

To 3.) Carmichael numbers are often mentioned in relationship with primality testing. A Carmichael number is a composite number $n$ that passes every Fermat primality test as long as the chosen basis $b$ is co-prime to $n$. In particular, every Carmichael number must be odd. In 1994 Alford, Granville and Pomerance [1] proved that there exists infinitely many Carmichael numbers. There even exists an algorithm to construct new Carmichael numbers [2].

To 4.) The definition of a Giuga number is very similar to the one of a Carmichael number. However, the status quo is more similar to the perfect numbers. It is not known if there are infinitely many Giuga numbers and every known Giuga number is even (actually, in fact all known Giuga numbers are a multiple of $6$). E.g. $30 = 2\cdot 3\cdot 5$ because $$2 | \frac{30}{2}-1$$ $$3 | \frac{30}{3}-1$$ $$5 | \frac{30}{5}-1$$ Currently (2019) there are 13 known Giuga numbers.

Using the ABC-Conjecture in Cryptography

The ABC-Conjecture is a very famous conjecture in Number Theory which is perhaps not a conjecture anymore if it the proof of Shinichi Mochizuki will turn out to be correct. I can not say anything useful about proving this conjecture, but i thought about its application for a while. Let me state the stronger version of the conjecture due to Baker [1];

ABC-Conjecture (strong, explicit version)

Given co-prime integers $a,b,c$ with $a + b = c$ then $$ c < (\text{rad}(abc))^{1.75}$$

The operator $\text{rad}$ (=radical) means the product of the distinct prime numbers dividing $n$. The version was derived from the (following) explicit ABC-Conjecture, also due to Baker:

ABC-Conjecture (explicit version)

Given co-prime integers $a,b,c$ with $a + b = c$ and let $\omega(n)$ be the number of distinct prime factors of $n$ then $$c < \frac{6}{5}\text{rad}(abc)\frac{(\log(\text{rad}(abc)))^{\omega(abc)}}{\omega(abc)!}$$

Assume you have co-prime integers $a,b,c$, wlog $a < b < c$, with $\text{rad}(a) < a^{1/6}$,  $\text{rad}(b) < b^{1/6}$ and $\text{rad}(c) < c^{1/6}$, then it is
\begin{align*}
 c &\leq \text{rad}(abc)^{1.75} = (\text{rad}(a)\text{rad}(b)\text{rad}(c))^{1.75}\\
 &< (a^{1/6}b^{1/6}c^{1/6})^{1.75} < (c^{1/2})^{1.75} = c^{15/16}\\
& < c
\end{align*} which is a contradiction and hence such integers can not exists. That's also the reason, why the even more famous Fermat Last Theorem follows from the ABC-Conjecture, which shows how deep the ABC-Conjecture is.

Observe the following simple Heuristic:

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

The $\sigma_i(n)$ function is an important arithmetic function and as typical for such functions, it can not be computed efficiently for large input parameters $n$ due to the factorization problem. But in contrast to $\sigma_1(n)$, which does reveal the factorization of $n$ immediately (at least if $n=pq$), $\sigma_0(n)$ does not, or at least not that easy (see Part 2 and Part 1). Additionally, $\sigma_1(n)$ has also the strange property that it can be computed recursively, as i showed in that [post].

However, we know how to compute, or better, how to decide, if $\sigma_0(n)$ is $2$ or not. This is because $\sigma_0(n) = 2$ if and only if $n$ is a prime number. And primality can be checked by the AKS-Algorithm in deterministic polynomial time. If AKS is too slow for you, there much more faster probabilistic polynomial time algorithms. They utilize that a prime number has special properties, e.g., they use Fermat-Little-Theorem. But so called base-$b$ pseudo prime numbers can survive this process and still pretend to be a prime number. Repeating the whole process with different values for $b$ often helps. Only a few pseudo prime numbers still remain for nearly all choices of $b$. These numbers are called carmichael numbers, and in [1] it was proved that there are infinite many such numbers. However, the probability to announce a false-positive for such algorithm is negligible after a few rounds.

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.

An explicit formula for the discrete logarithm

I guess, but i am not sure, many people don't know that there is an explicit formula for the discrete logarithm in finite fields $\mathbb{F}^*_p$. I remember that i was quite surprised when i learned the formula many years ago.

Theorem [Explicit DL Formula] Let $p$ be a prime number $>2$ and $g$ be a primitive root in $\mathbb{F}^*_p$. Then the discrete logarithm of the element $a \in \mathbb{F}^*_p$ is equal to \begin{equation} \mathsf{dlog}_{p,g}(a) = \sum^{p-2}_{k=1} \frac{a^k}{1-g^k}\pmod{p}\end{equation}

The proof is actually not that complicated and can be found in Niederreiter [1]. I will give here a new proof for you:

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."

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

The Collatz Conjecture

The Collatz Conjecture is another famous conjecture that concerns the natural numbers. There has been written a lot about the collatz conjecture, just see the beautiful blog post from Terence Tao or the overview from Lagrias [1]. The conjecture is also known as the $3n+1$ conjecture, the Ulam conjecture or the Syracuse conjecture. The handsomeness of this conjecture is based on the fact that it is one of these conjectures that are easy to state and even understandable by non-mathematicians.

The collatz conjecture in its original form is this:

Definition [Collatz-Function]. The Collatz function for an integer $n \in \mathbb{N}$ is defined as $$ C(n) := \begin{cases} 3n+1 & \text{if}\;n\;\text{is odd} \\ n/2 & \text{if}\;n\;\text{is even}\end{cases} $$ $\blacktriangleleft$

Then the conjecture is:

Collatz-Conjecture. For each \(n \in \mathbb{N}\) there exists an \(k \in \mathbb{N}\) such that \(C^k(n) = 1\).

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.