Since 2002 this has been known, and it's one of the least intuitive things in modern math. (versions with probability of 1-\epsilon have existed since Miller-Rabin in 1976)