Let $A$ be an abelian variety over $mathbb{Q}$ of dimension $g$ such that the image of its associated absolute Galois representation $rho_A$ is open in $operatorname{GSp}_{2g}(hat{mathbb{Z}})$. We investigate the arithmetic of the traces $a_{1, p}$ o
f the Frobenius at $p$ in $operatorname{Gal}(overline{mathbb{Q}}/mathbb{Q})$ under $rho_A$, modulo varying primes $p$. In particular, we obtain upper bounds for the counting function $#{p leq x: a_{1, p} = t}$ and we prove an Erdos-Kac type theorem for the number of prime factors of $a_{1, p}$. We also formulate a conjecture about the asymptotic behaviour of $#{p leq x: a_{1, p} = t}$, which generalizes a well-known conjecture of S. Lang and H. Trotter from 1976 about elliptic curves.
We provide a framework for using elliptic curves with complex multiplication to determine the primality or compositeness of integers that lie in special sequences, in deterministic quasi-quadratic time. We use this to find large primes, including the
largest prime currently known whose primality cannot feasibly be proved using classical methods.
We give a deterministic algorithm that very quickly proves the primality or compositeness of the integers N in a certain sequence, using an elliptic curve E/Q with complex multiplication by the ring of integers of Q(sqrt(-7)). The algorithm uses O(lo
g N) arithmetic operations in the ring Z/NZ, implying a bit complexity that is quasi-quadratic in log N. Notably, neither of the classical N-1 or N+1 primality tests apply to the integers in our sequence. We discuss how this algorithm may be applied, in combination with sieving techniques, to efficiently search for very large primes. This has allowed us to prove the primality of several integers with more than 100,000 decimal digits, the largest of which has more than a million bits in its binary representation. At the time it was found, it was the largest proven prime N for which no significant partial factorization of N-1 or N+1 is known.
