A new algebraic Cayley graph is constructed using finite fields. It provides a more flexible source of expander graphs. Its connectedness, the number of connected components, and diameter bound are studied via Weil's estimate for character sums. Furthermore, we study the algorithmic problem of computing the number of connected components and establish a link to the integer factorization problem. © 2014 Elsevier Inc.