In my random readings of nice math, I came across a very nice counting argument.
Now, consider the following curve \[ Y^2 = X^3 + AX + B \]
which is called an elliptic curve. The curve is called non-singular if its discriminant \(4A^3+27B^2\) is non-zero. There are some sophisticated algorithms that count the number of points \((X,Y)\) on a non-singular elliptic curve in the space \(\mathbb{F}^2\) over a finite field \(\mathbb{F}\). But, I am going to use a simple formula I saw in a paper titled “Counting points on elliptic curves over finite fields” by René Schoof. The number of points over the finite field \(\mathbb{F}\) is
\[ 1 + p + \sum_{x\in \mathbb{Z}/p} \left(\frac{x^3 + Ax + B}{p}\right) \]
where \(\left(\frac{q}{p}\right)\) is what is called the Legendre symbol which can be calculated as the simple exponent
\[ \left(\frac{q}{p}\right) = q^{(p-1)/2} \]
when \(p\) is an odd prime.
Let us start by implementing a smarter modular exponentiation:
(defun mod-exp (b e p &optional (acc 1))
(cond
((zerop e) acc)
((evenp e) (mod-exp (mod (* b b) p) (/ e 2) p acc))
(t (mod-exp (mod (* b b) p) (/ (1- e) 2) p (mod (* acc b) p)))))
(mod-exp 3 255 32933)MOD-EXP
14907This implementation is a variation of Egyptian multiplication modified for exponentiation.
Next, we implement the Legendre symbol as below:
(defun legendre (a p)
(cond
((zerop (mod a p)) 0)
((mod-exp a (/ (1- p) 2) p) 1)
(t -1)))
(legendre 255 32933)LEGENDRE
1Now, we are ready
(defun count-points (a b p)
(if (not (zerop (mod (+ (* 4 a a a) (* 27 b b)) p)))
(+ 1 p (loop for i from 0 below p
for x = (+ (* i i i) (* a i) b)
sum (legendre x p)))))
(count-points 7 13 32933)COUNT-POINTS
65867