NumberWorld

Detecting primes in deterministic polynomial time was a goal for hundreds of years. In 2002, a major breakthrough occurred in number theory: for the first time, a proof was published showing how to determine, in deterministic polynomial time, whether a given integer $n$ is prime. The resulting method is now known as the AKS algorithm , named after its authors Agrawal, Kayal, and Saxena. For their work, they received two major international awards: the Gödel Prize and the Fulkerson Prize. Of course, even before 2002, finding large prime numbers was far from hopeless. In fact, the algorithms used in practice today are essentially the same as those used before AKS, because they are extremely efficient. However, before AKS, all known efficient primality tests had one of the following drawbacks:

For decades, elliptic curves were regarded as beautiful but highly theoretical objects. While elliptic curves over finite fields naturally form groups, one fundamental problem remained computationally difficult: counting points on elliptic curves . In particular, determining the exact size of the group \( E(\mathbb{F}_p) \) was infeasible for general curves. Before the mid-1980s, counting points on elliptic curves was practical only for very special families, such as curves with complex multiplication. This severely limited their cryptographic applications. Early public-key cryptography therefore relied instead on multiplicative groups of finite fields, where the group order is easy to compute. Everything changed with Schoof’s algorithm. For the first time, it showed that counting points on elliptic curves over finite fields can be done in polynomial time. This breakthrough removed a major barrier to using elliptic curves in cryptography. Today, efficient point coun...

Fermat quotients have been mentioned several times in this blog and they are fascinating peace of math. The definition is \begin{equation}q_p(2) = \frac{2^{p-1}-1}{p},\;\;p \in \mathbb{P} \end{equation} One can extend this definition to composite integers $n$, which are called Euler quotients . \begin{equation} q^*_n(2) = \frac{2^{\varphi(n)}-1}{n},\;\;n \in \mathbb{N} \end{equation} In this short post, i would like to demonstrate the power of these Euler Quotients. Suppose you have an Oracle $\mathcal{O}$ that, given an integer $n$, returns $q^*_n(2)$. Only one such query is allowed . We treat $q^*_n(2)$ simply as a binary string and show that this string contains enough information to compute things that are otherwise hard to compute.

We start with a very brief primer to Binary Quadratic Forms (BQF). For more information ⦗1⦘ is a very good source to start with. 　A Binary Quadratic Form is a polynom of the form $Q(x,y) = ax^2+bxy+cy^2$ with integer coefficients. We focus on integer BQF, i.e., $x,y \in \mathbb{Z}$. Often one is only interested in the behaviour of the coefficients $a,b,c$ and in those cases one refers to a BQF simply by the triple $(a,b,c)$. Further, the integer $D$ defined as: $$D = b^2 - 4ac$$ is called the discriminant of $(a,b,c)$. 　A positive definite BQF $(a,b,c)$, i.e. $D < 0, a > 0$, is reduced if $-a < b < a < c$. Gauss observed, that all reduced BQF with the same discriminant form an abelian group and he gave a composition algorithm for those group elements. This group is called the class group and is usually denoted as $\mathcal{Cl}(D)$. The size of the group has a special name and is called the class number $h(D)$. Informally spoken, the class group $\mathcal{Cl}(D)$ ...

This blog post is about De Bruijn sequences and its relationship to cryptography. We focus here on De Bruijn sequences over the alphabet $A=\{0,1\}$. Definition [De Bruijn sequence (binary)] .   A binary string of length $2^n$ is called a De Bruijn sequence of order $n$ if each possible $n$-bit string occurs exactly once (incl. wrap-around) as a substring.  Picture 1 - DeBruijn graph for n=3 De Bruijn sequences are the shortest possible bitstring that contains all possible $n$-bit substrings. For each $n$ there are $$\frac{2^{2^{n-1}}}{2^n}$$ possible De Bruijn sequences. For example, a De Bruijn sequence of order $n=3$ is $$00011101$$ and of order $n=4$ is $$0000101100111101$$ There are several ways to create De Bruijn sequences. One way is walk along an  Hamiltonian Cycle in the corresponding De Bruijn graph (see Picture 1) . A De Bruijn graph is a directed graph of degree $2$ which has $2^n$ vertices. There is an edge from vertex $i$ to the two vertices $$(2i\;...

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.

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: Prime Numbers : An integer $n$ with only one proper divisor. 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$). Carmichael Numbers  : An integer $n$ such that $(p-1) | (n/p-1)$ for each prime factor $p$ of $n$ 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 ...

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

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

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.

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$ [i.e. the exponent $x$ from $g^x \equiv a\pmod{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} Note: This is a finite-sum identity that still costs $\approx \mathcal{O}(p)$ field ops, so it’s not a practical attack on discrete log for large primes but it’s conceptually neat (character sums / interpolation flavor). Although the discrete logarithm is naturally defined modulo $p-1$, the above identity evaluates in $\mathbb{F}_p$ and yields the unique integer representative in ${0,\dots,p-2}$. Th...

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

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 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\).

Another unproven conjecture in number theory is the Infinite Regular Primes Conjecture (IRPC). It addresses a special properties of primes. A prime can be regular or a prime can be irregular. For the later we know a proof [given below] since many years. For regular primes it is still unknown if they are infinite despite the fact that we can give good arguments that around $$60.653\%$$ of all primes should be regular. So we know that major part of all primes should be regular, but we cant prove it. 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\) $\blackt...

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.

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