Title: Point Counting on Elliptic Curves over Finite Fields
Abstract: Elliptic curves over finite fields play a central role in modern number theory and cryptography. A fundamental computational problem is to determine the number of rational points on a given elliptic curve defined over a finite field, a quantity closely related to the trace of the Frobenius endomorphism.
In this talk, I will present an overview of algorithms for point counting on elliptic curves, starting from naive enumeration and the Baby-Step Giant-Step method, and progressing to more efficient approaches. The main focus will be Schoof’s algorithm, a deterministic polynomial-time method that computes the number of points by determining the trace of Frobenius modulo small primes and reconstructing it via the Chinese Remainder Theorem, together with Hasse’s bound.
I will also discuss practical aspects of implementation, including SageMath computations over large finite fields, and compare the efficiency of different algorithms across varying field sizes. Finally, I will highlight the significance of point counting in elliptic curve cryptography, where the security of cryptographic protocols depends on the arithmetic structure of elliptic curves and the hardness of the elliptic curve discrete logarithm problem.
The talk will conclude with a brief discussion of current research directions, including improvements via the SEA algorithm and connections to L-functions and modern cryptographic constructions.