The telecare medicine information system enables or supports health-care delivery services. In recent years, the increased availability of lower-cost telecommunications systems and custom made physiological monitoring devices for patients have made it possible to bring the advantages of telemedicine directly into the patient's home. These systems are moving towards an environment where automated patient medical records and electronically interconnected telecare facilities are prevalent. A secure authentication scheme will thus be needed to safeguard data integrity, confidentiality, and availability. Many schemes based on cryptography have been proposed for the goals. However, much of the schemes are vulnerable to various attacks, and are neither efficient, nor user friendly. Specially, in terms of efficiency, some schemes need the exponential computation resulting in high time cost. Therefore, we propose a novel authentication scheme that is added the pre-computing idea within the communication process to avoid the time-consuming exponential computations. Finally, it is shown to be more secure and practical for telecare medicine environments.