In this post I want to talk about a thing from the Kryptos universe that are not directly related to the statue. But i think it may be an indirect hint to some Kryptos related methods. The Mayan Symbols in Ed Scheidts driveway I think everyone who knows Kryptos knows Ed Scheidt. The former Chairman of the Cryptographic Center at the CIA and founder of the cryptosystems used around the Kryptos statue. As already shown in Part 4 of my Kryptos series, in the driveway of Ed Scheidts house, there are two symbols: Figure 1 - Garage driveway of Ed Scheidt We denote the left symbol set with $S_1$ and the right one with $S_2$. It took me a while to find his house on Google Maps - Street View. To save you some time, here is the link with a view on the driveway. I you go back in time in Streetview, you can see that the symbols were already there in 2012. But it is impossible to say when they were built. $S_1$ is clearly visible from the street, $S_2$ is hidden in the view. But you can u...
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 counting is foundational for:
-
Generating secure elliptic curves
-
Verifying their group structure
-
Ensuring resistance to small-subgroup attacks
-
Validating cryptographic security parameters
Without efficient methods for counting points on elliptic curves, modern elliptic curve cryptography (ECC) would not exist.
Why Counting Points on Elliptic Curves Matters in Cryptography
Cryptography is fundamentally about working inside groups — and especially about knowing the size of those groups.
Multiplicative groups over finite fields
If you work over a finite field $\mathbb{F}_p$ that size of all multiplicative subgroups is completely determined by the prime factorization of $p-1$. Small subgroups are dangerous. They enable attacks if: $$ p - 1 = 2\cdot 3\cdot 5 ... $$ i.e., contains small prime factors. For a safe choice for $p$ we pick primes such that $p-1$ is safe. That means, it contains at least one large prime factor. Sofie-Germain primes are likely the best choice.
Example
If we set $p=31$, then $p-1=30=2\cdot 3\cdot 5$ hence the list of all divisors is $$\text{div}(p-1) = \{1,2,3,5,6,10,15,30\}$$ All multiplicative subgroups sizes of $\mathbb{Z}^*_{31}$ are one of those integers. In contrast, we set $p=47$, then $p-1=46=2\cdot 23$ hence the list of all divisors is $$\text{div}(p-1) = \{1,2,23,46\}$$ The possible subgroups sizes of $\mathbb{Z}^*_{47}$ are only one of this four integers. Even if $p$ is a Safe Prime of size around $2^{1024}$, the number of possible groups sizes are only $4$.
If we set $p=31$, then $p-1=30=2\cdot 3\cdot 5$ hence the list of all divisors is $$\text{div}(p-1) = \{1,2,3,5,6,10,15,30\}$$ All multiplicative subgroups sizes of $\mathbb{Z}^*_{31}$ are one of those integers. In contrast, we set $p=47$, then $p-1=46=2\cdot 23$ hence the list of all divisors is $$\text{div}(p-1) = \{1,2,23,46\}$$ The possible subgroups sizes of $\mathbb{Z}^*_{47}$ are only one of this four integers. Even if $p$ is a Safe Prime of size around $2^{1024}$, the number of possible groups sizes are only $4$.
The Difference with Elliptic Curves
For elliptic curves, things are fundamentally different. If $E(\mathbb{F}_p): y^2=x^3+Ax+B$ then the group size $\#E(\mathbb{F}_p)$ is not known in advance.
There is no simple formula like "p−1”. The group order depends delicately on the arithmetic of the curve.
However, we know a certain range. According to the Theorem
of Hasse for Elliptic Curves we know that
$$\left| \#E(\mathbb{F}_p) - (p+1)\right| \leq 2\sqrt{p} $$
That’s why counting points on elliptic curves is essential:
We must ensure the group has a large prime factor
We must avoid small subgroups
We must verify cryptographic strength
Schoof’s algorithm made this possible in full generality.
Counting Points on Elliptic Curves: The Basic Formula
Let $p$ be a prime number and $A,B \in \mathbb{F}_p$, then
$$ E(\mathbb{F}_p): y^2 = x^3 + Ax + B$$We assume the $E$ is non-singluar. Then the number of points on the curve can be expressed as the following sum of legendre symbols
$$ \#E(\mathbb{F}_p) = 1 + \sum^{p}_{x=1} \left(1 + \binom{x^3 + Ax + B}{p}\right)
= p + 1 + \sum^{p}_{x=1} \binom{x^3 + Ax + B}{p} $$
= p + 1 + \sum^{p}_{x=1} \binom{x^3 + Ax + B}{p} $$
It looks pretty simple - just evaluate the sum on the right side and you are done. However, if we write $n=\log(p)$ (as usual), directly evaluating this
sum is exponential in $n$. For cryptographic primes (hundreds/thousands of bits), this is infeasible.
But some special cases allow elegant solutions even without the need to apply Schoof's algorithm.
We’ll work out a nontrivial family where point counting can still be done by hand. The key tool is the Jacobsthal Sum, which reduces the point count to a classical number-theoretic identity. This also illustrates why general point counting is hard — and why Schoof’s algorithm matters.
Theorem
Let $E(\mathbb{F}_p)$ be an elliptic curve of the form $y^2 = x^3+Ax$, then
- If $p \equiv 3\pmod{4}$, then $\#E(\mathbb{F}_p) = p+1$
- If $p \equiv 1\pmod{4}$, then $\#E(\mathbb{F}_p) \in \{p+1\pm 2a,p+1\pm 2b\}$, where $p=a^2+b^2$ is the unique representation of $p$ as the sum of two squares
We need one helping Lemma for the proof [1].
Lemma
Given $x^2+bx+c$ and set $D = b^2 - 4c$
$$ \sum^p_{x=1} \binom{x^2+bx+c}{p} = \sum^p_{x=1} \binom{x^2-D}{p} = p-1-p\binom{D}{p}^2 $$
*The function $\binom{\cdot}{\cdot}$ is as usual the Legendre symbol.
Proof [Theorem]
The proof is all about the evaluation the sum $\sum^{p}_{x=1} \binom{x^3 + Ax + B}{p}$ in the two cases.
Case 1: The first case is the easy case. For a prime of the form $p \equiv 3\pmod{4}$ it is $\binom{x}{p} = -\binom{p-x}{p}$ due to the fact that $\binom{-1}{p} = -1$. So we have $$ \binom{x^3 + Ax}{p} = \binom{x}{p}\binom{x^2 + A}{p} = -\binom{p-x}{p}\binom{(p-x)^2 + A}{p}$$ So the first $(p-1)/2$ terms cancel with the later ones. \begin{align*} \sum^p_{x=1} \binom{x}{p}\binom{x^2 + A}{p} & = \sum^{(p-1)/2}_{x=1} \binom{x}{p}\binom{x^2 + A}{p} + \sum^{(p-1)/2}_{x=0} \binom{p-x}{p}\binom{(p-x)^2 + A}{p} \\
& = \sum^{(p-1)/2}_{x=1} \binom{x}{p}\binom{x^2 + A}{p} - \sum^{(p-1)/2}_{x=0} \binom{x}{p}\binom{x^2 + A}{p} \\
& = 0 \end{align*} Note that $\binom{0}{p} = 0$.
Case 2: The second case is the tricky one. For a prime of the form $p \equiv 1\pmod{4}$ we can not argue in the same way. But we can write $$ \sum^{p}_{x=1} \binom{x^3 + Ax}{p} = \sum^{p}_{x=1} \binom{x}{p}\binom{x^2 + A}{p} =: f(A) $$ Here we have $\binom{x}{p} = \binom{p-x}{p}$ due to the fact that $\binom{-1}{p} = 1$ which ensures as the first observation that $f(A)$ must be an even number, i.e.: $$ \sum^{p}_{x=1} \binom{x}{p}\binom{x^2 + A}{p} = 2\sum^{(p-1)/2}_{x=1} \binom{x}{p}\binom{x^2 + A}{p} $$
Step 1:
The sum $f(A)$ (see above) is known as Jacobsthal Sum. We follow here the proof from [1]. Let $y$ be an integer co-prime to $p$, then \begin{align*} f(A) & = \binom{y^4}{p}f(A) = \binom{y}{p}\sum^{p-1}_{x=0} \binom{y}{p}\binom{x}{p}\binom{y^2}{p}\binom{x^2 + A}{p} \\
& = \binom{y}{p}\sum^{p-1}_{x=0} \binom{xy}{p}\binom{(xy)^2 + y^2A}{p}\\
& = \binom{y}{p}\sum^{p-1}_{m=0} \binom{m}{p}\binom{m^2 + y^2A}{p}\\
& = \binom{y}{p}f(y^2A) \end{align*} The second to last equaltiy is due to the fact that $xy$ and $(xy)^2$ cover the same residues as $x$ and $x^2$, just a permutation. This can be realized as a switch of index.
After squaring we get: $$ f(A)^2 = \binom{y^2}{p}f(y^2A)^2 = f(y^2A)^2 $$ The integer $y^2A$ is a quadratic residue whenever $A$ is (we just multiply with a QR). And with the same reason $y^2A$ is a quadratic non-residue whenever $A$ is. So $f(A)^2$ adapts only two possible values $f(r)$ for $\binom{r}{p}=1$ and $f(n)$ for $\binom{n}{p}=-1$. If we now sum over all possible $A$'s and keep in mind that there are $(p-1)/2$ quadratic residues and non-residues, we get: $$ [1]\;\;\;\;\;\;\;\;\;\;\;\;\sum^{p}_{A=1} f(A)^2 = \frac{p-1}{2}f(r)^2 + \frac{p-1}{2}f(n)^2 $$ Step 2:
Next, we do a direct evaluation of the sum $\sum^{p-1}_{A=1} f(A)^2$. First look at $f(A)^2$ only (no sum): \begin{align*} f(A)^2 & = f(A)\cdot f(A) \\
& = \left[\sum^{p}_{x_1=1} \binom{x_1}{p}\binom{x_1^2 + A}{p}\right]\left[\sum^{p}_{x_2=1} \binom{x_2}{p}\binom{x_2^2 + A}{p}\right] \\
& = \sum^{p}_{x_1=1}\sum^{p}_{x_2=1} \binom{x_1}{p}\binom{x_1^2 + A}{p}\binom{x_2}{p}\binom{x_2^2 + A}{p} \\
& = \sum^{p}_{x_1=1}\sum^{p}_{x_2=1} \binom{x_1x_2}{p}\binom{(x_1x_2)^2 + A(x_1^2+x_2^2)+A^2}{p}\\
\end{align*} If we know add the sum again over all $A$: \begin{align*} \sum^p_{A=1} f(A)^2 & = \sum^p_{A=1}\sum^{p}_{x_1=1}\sum^{p}_{x_2=1} \binom{x_1x_2}{p}\binom{(x_1x_2)^2 + A(x_1^2+x_2^2)+A^2}{p}\\
& = \sum^{p}_{x_1=1}\sum^{p}_{x_2=1} \binom{x_1x_2}{p}\sum^p_{A=1}\binom{(x_1x_2)^2 + A(x_1^2+x_2^2)+A^2}{p}\\
\end{align*} For the most inner sum we can apply the Lemma from above, since $x_1$ and $x_2$ are fixed in this case. \begin{align*} \sum^p_{A=1} f(A)^2 & = \sum^{p}_{x_1=1}\sum^{p}_{x_2=1} \binom{x_1x_2}{p}\left(p-1-p\binom{(x_1^2+x_2^2)^2-4x_1^2x_2^2}{p}^2\right)\\
\end{align*} Note that $(x_1^2+x_2^2)^2-4x_1^2x_2^2 = x_1^4 - 2x_1^2x_2^2 + x_2^4 = (x_1^2-x_2^2)^2$ \begin{align*} \sum^p_{A=1} f(A)^2 & = \sum^{p}_{x_1=1}\sum^{p}_{x_2=1} \binom{x_1x_2}{p}\left(p-1-p\binom{(x_1^2-x_2^2)^2}{p}^2\right)\\
\end{align*} Whenever $x_1^2 \neq x_2^2$ the term $p-1-p\binom{(x_1^2-x_2^2)^2}{p}^2$ is equal to $-1$. And whenever $x_1^2 = x_2^2$ it is $p-1$. So we can split the sum \begin{align*} \sum^p_{A=1} f(A)^2 & = \sum^{p}_{x_1=1}\sum^{p}_{x_2=1;x_1^2\neq x_2^2} \binom{x_1x_2}{p}(-1) + \sum^{p}_{x_1=1}\sum^{p}_{x_2=1;x_1^2=x_2^2} \binom{x_1x_2}{p}(p-1)\\
& = -\sum^{p}_{x_1=1}\binom{x_1}{p}\sum^{p}_{x_2=1;x_1^2\neq x_2^2} \binom{x_2}{p} + \sum^{p}_{x_1=1}\sum^{p}_{x_2=1;x_1^2=x_2^2} \binom{x_1x_2}{p}(p-1)\\
& = -\sum^{p}_{x_1=1}\binom{x_1}{p}\left(-\binom{x_1}{p}-\binom{-x_1}{p}\right) + \sum^{p}_{x_1=1}\sum^{p}_{x_2=1;x_1^2=x_2^2} \binom{x_1x_2}{p}(p-1)\\
& = 2\sum^{p}_{x_1=1}\binom{x_1^2}{p} + \sum^{p}_{x_1=1}\sum^{p}_{x_2=1;x_1^2=x_2^2} \binom{x_1x_2}{p}(p-1)\\
& = 2(p-1) + \sum^{p}_{x_1=1}\sum^{p}_{x_2=1;x_1^2=x_2^2} \binom{x_1x_2}{p}(p-1)\\
& = 2(p-1) + \sum^{p}_{x_1=1}\left(\left(\binom{x_1^2}{p}+\binom{-x_1^2}{p}\right)(p-1)\right)\\
\end{align*} So for a prime $p=1\pmod{4}$, we get $$ [2]\;\;\;\;\;\;\;\;\;\;\;\;\sum^{p}_{A=1} f(A)^2 = 2(p-1) + 2(p-1)(p-1) = 2p(p-1) $$ Equating [1] and [2], we get $$ \frac{p-1}{2}f(r)^2 + \frac{p-1}{2}f(n)^2 = 2p(p-1) $$ hence $$ \left(\frac{f(r)}{2}\right)^2 + \left(\frac{f(n)}{2}\right)^2 = p = a^2 + b^2$$ Note: We observed that $f()$ is always an even number so division by $2$ does not cause any problems here.
We can conclude that $f(r)/2 = \pm a$ and $f(n)/2 = \pm b$ $\Leftrightarrow$ $f(r) = \pm 2a$ and $f(n) = \pm 2b$. The representation of $p$ (if $p\equiv 1\pmod{4}$) as the sum of two square is unique. So we figured out the value for $f(A)$ is either $\pm 2a$ or $\pm 2b$, depending on its legendre symbol, which proofs the Theorem.
□
Case 1: The first case is the easy case. For a prime of the form $p \equiv 3\pmod{4}$ it is $\binom{x}{p} = -\binom{p-x}{p}$ due to the fact that $\binom{-1}{p} = -1$. So we have $$ \binom{x^3 + Ax}{p} = \binom{x}{p}\binom{x^2 + A}{p} = -\binom{p-x}{p}\binom{(p-x)^2 + A}{p}$$ So the first $(p-1)/2$ terms cancel with the later ones. \begin{align*} \sum^p_{x=1} \binom{x}{p}\binom{x^2 + A}{p} & = \sum^{(p-1)/2}_{x=1} \binom{x}{p}\binom{x^2 + A}{p} + \sum^{(p-1)/2}_{x=0} \binom{p-x}{p}\binom{(p-x)^2 + A}{p} \\
& = \sum^{(p-1)/2}_{x=1} \binom{x}{p}\binom{x^2 + A}{p} - \sum^{(p-1)/2}_{x=0} \binom{x}{p}\binom{x^2 + A}{p} \\
& = 0 \end{align*} Note that $\binom{0}{p} = 0$.
Case 2: The second case is the tricky one. For a prime of the form $p \equiv 1\pmod{4}$ we can not argue in the same way. But we can write $$ \sum^{p}_{x=1} \binom{x^3 + Ax}{p} = \sum^{p}_{x=1} \binom{x}{p}\binom{x^2 + A}{p} =: f(A) $$ Here we have $\binom{x}{p} = \binom{p-x}{p}$ due to the fact that $\binom{-1}{p} = 1$ which ensures as the first observation that $f(A)$ must be an even number, i.e.: $$ \sum^{p}_{x=1} \binom{x}{p}\binom{x^2 + A}{p} = 2\sum^{(p-1)/2}_{x=1} \binom{x}{p}\binom{x^2 + A}{p} $$
Step 1:
The sum $f(A)$ (see above) is known as Jacobsthal Sum. We follow here the proof from [1]. Let $y$ be an integer co-prime to $p$, then \begin{align*} f(A) & = \binom{y^4}{p}f(A) = \binom{y}{p}\sum^{p-1}_{x=0} \binom{y}{p}\binom{x}{p}\binom{y^2}{p}\binom{x^2 + A}{p} \\
& = \binom{y}{p}\sum^{p-1}_{x=0} \binom{xy}{p}\binom{(xy)^2 + y^2A}{p}\\
& = \binom{y}{p}\sum^{p-1}_{m=0} \binom{m}{p}\binom{m^2 + y^2A}{p}\\
& = \binom{y}{p}f(y^2A) \end{align*} The second to last equaltiy is due to the fact that $xy$ and $(xy)^2$ cover the same residues as $x$ and $x^2$, just a permutation. This can be realized as a switch of index.
After squaring we get: $$ f(A)^2 = \binom{y^2}{p}f(y^2A)^2 = f(y^2A)^2 $$ The integer $y^2A$ is a quadratic residue whenever $A$ is (we just multiply with a QR). And with the same reason $y^2A$ is a quadratic non-residue whenever $A$ is. So $f(A)^2$ adapts only two possible values $f(r)$ for $\binom{r}{p}=1$ and $f(n)$ for $\binom{n}{p}=-1$. If we now sum over all possible $A$'s and keep in mind that there are $(p-1)/2$ quadratic residues and non-residues, we get: $$ [1]\;\;\;\;\;\;\;\;\;\;\;\;\sum^{p}_{A=1} f(A)^2 = \frac{p-1}{2}f(r)^2 + \frac{p-1}{2}f(n)^2 $$ Step 2:
Next, we do a direct evaluation of the sum $\sum^{p-1}_{A=1} f(A)^2$. First look at $f(A)^2$ only (no sum): \begin{align*} f(A)^2 & = f(A)\cdot f(A) \\
& = \left[\sum^{p}_{x_1=1} \binom{x_1}{p}\binom{x_1^2 + A}{p}\right]\left[\sum^{p}_{x_2=1} \binom{x_2}{p}\binom{x_2^2 + A}{p}\right] \\
& = \sum^{p}_{x_1=1}\sum^{p}_{x_2=1} \binom{x_1}{p}\binom{x_1^2 + A}{p}\binom{x_2}{p}\binom{x_2^2 + A}{p} \\
& = \sum^{p}_{x_1=1}\sum^{p}_{x_2=1} \binom{x_1x_2}{p}\binom{(x_1x_2)^2 + A(x_1^2+x_2^2)+A^2}{p}\\
\end{align*} If we know add the sum again over all $A$: \begin{align*} \sum^p_{A=1} f(A)^2 & = \sum^p_{A=1}\sum^{p}_{x_1=1}\sum^{p}_{x_2=1} \binom{x_1x_2}{p}\binom{(x_1x_2)^2 + A(x_1^2+x_2^2)+A^2}{p}\\
& = \sum^{p}_{x_1=1}\sum^{p}_{x_2=1} \binom{x_1x_2}{p}\sum^p_{A=1}\binom{(x_1x_2)^2 + A(x_1^2+x_2^2)+A^2}{p}\\
\end{align*} For the most inner sum we can apply the Lemma from above, since $x_1$ and $x_2$ are fixed in this case. \begin{align*} \sum^p_{A=1} f(A)^2 & = \sum^{p}_{x_1=1}\sum^{p}_{x_2=1} \binom{x_1x_2}{p}\left(p-1-p\binom{(x_1^2+x_2^2)^2-4x_1^2x_2^2}{p}^2\right)\\
\end{align*} Note that $(x_1^2+x_2^2)^2-4x_1^2x_2^2 = x_1^4 - 2x_1^2x_2^2 + x_2^4 = (x_1^2-x_2^2)^2$ \begin{align*} \sum^p_{A=1} f(A)^2 & = \sum^{p}_{x_1=1}\sum^{p}_{x_2=1} \binom{x_1x_2}{p}\left(p-1-p\binom{(x_1^2-x_2^2)^2}{p}^2\right)\\
\end{align*} Whenever $x_1^2 \neq x_2^2$ the term $p-1-p\binom{(x_1^2-x_2^2)^2}{p}^2$ is equal to $-1$. And whenever $x_1^2 = x_2^2$ it is $p-1$. So we can split the sum \begin{align*} \sum^p_{A=1} f(A)^2 & = \sum^{p}_{x_1=1}\sum^{p}_{x_2=1;x_1^2\neq x_2^2} \binom{x_1x_2}{p}(-1) + \sum^{p}_{x_1=1}\sum^{p}_{x_2=1;x_1^2=x_2^2} \binom{x_1x_2}{p}(p-1)\\
& = -\sum^{p}_{x_1=1}\binom{x_1}{p}\sum^{p}_{x_2=1;x_1^2\neq x_2^2} \binom{x_2}{p} + \sum^{p}_{x_1=1}\sum^{p}_{x_2=1;x_1^2=x_2^2} \binom{x_1x_2}{p}(p-1)\\
& = -\sum^{p}_{x_1=1}\binom{x_1}{p}\left(-\binom{x_1}{p}-\binom{-x_1}{p}\right) + \sum^{p}_{x_1=1}\sum^{p}_{x_2=1;x_1^2=x_2^2} \binom{x_1x_2}{p}(p-1)\\
& = 2\sum^{p}_{x_1=1}\binom{x_1^2}{p} + \sum^{p}_{x_1=1}\sum^{p}_{x_2=1;x_1^2=x_2^2} \binom{x_1x_2}{p}(p-1)\\
& = 2(p-1) + \sum^{p}_{x_1=1}\sum^{p}_{x_2=1;x_1^2=x_2^2} \binom{x_1x_2}{p}(p-1)\\
& = 2(p-1) + \sum^{p}_{x_1=1}\left(\left(\binom{x_1^2}{p}+\binom{-x_1^2}{p}\right)(p-1)\right)\\
\end{align*} So for a prime $p=1\pmod{4}$, we get $$ [2]\;\;\;\;\;\;\;\;\;\;\;\;\sum^{p}_{A=1} f(A)^2 = 2(p-1) + 2(p-1)(p-1) = 2p(p-1) $$ Equating [1] and [2], we get $$ \frac{p-1}{2}f(r)^2 + \frac{p-1}{2}f(n)^2 = 2p(p-1) $$ hence $$ \left(\frac{f(r)}{2}\right)^2 + \left(\frac{f(n)}{2}\right)^2 = p = a^2 + b^2$$ Note: We observed that $f()$ is always an even number so division by $2$ does not cause any problems here.
We can conclude that $f(r)/2 = \pm a$ and $f(n)/2 = \pm b$ $\Leftrightarrow$ $f(r) = \pm 2a$ and $f(n) = \pm 2b$. The representation of $p$ (if $p\equiv 1\pmod{4}$) as the sum of two square is unique. So we figured out the value for $f(A)$ is either $\pm 2a$ or $\pm 2b$, depending on its legendre symbol, which proofs the Theorem.
One may wonder if we can also find $a$ and $b$ efficiently. Yes, this is possible very efficiently using e.g. Cornacchia's Algorithm.
[1] Jacobsthal, E. (1907), "Über die Darstellung der Primzahlen der Form 4n + 1 als Summe zweier Quadrate", Journal für die reine und angewandte Mathematik: 238–245, ISSN 0075-4102, JFM 38.0238.03
Comments
Post a Comment