Over the last 25 years, various fast algorithms for computing the determinant of a pentadiagonal Toeplitz matrices were developed. In this paper, we give a new kind of elementary algorithm requiring 56 . [n-4/k] + 30k O(log n) operations, where k >= 4 is an integer that needs to be chosen freely at the beginning of the algorithm. For example, we can compute det(T-n) in n + O(log n) and 82 root n + O(log n) operations if we choose k as 56 and [root 28/15(n - 4)], respectively. For various applications, it will be enough to test if the determinant of a pentadiagonal Toeplitz matrix is zero or not. As in another result of this paper, we used modular arithmetic to give a fast algorithm determining when determinants of such matrices are non-zero. This second algorithm works only for Toeplitz matrices with rational entries. (C) 2011 Elsevier B.V. All rights reserved.