What is the fastest deterministic primality test for numbers in the range 2^1024 to 2^4096?

Question

I am writing an implementation of a cryptography protocol. So far I've been having a difficult time finding the fastest deterministic primality test for 1024-bit to 4096-bit integers (308- to 1233-digit numbers). I am aware of several options but I have not been able to find real world speed comparisons.

Specifically, how does the AKS test perform compared to the deterministic version of Rabin-Miller and the Elliptic Curve Primality Proving test (and others) for general random numbers this size ?

Answer 1

This article is answering your question:

PRIMALITY TESTING by Richard P. Brent: http://cs.anu.edu.au/student/comp4600/lectures/comp4600_primality.pdf

It compares in complexity and in "real world speed" the 3 algorithms.