Public cloud storage auditing allows a file owner or a public verifier to conduct integrity checking without downloading the whole file from cloud server. Plenty of unaffordable modular exponentiations for resource-constraint devices are required on the client side in the process of signature generation for public cloud storage auditing. In this paper, we introduce a secure outsourcing algorithm to make cloud storage public auditing more feasible and practical for the computationally limited clients. Compared with the existing algorithms for secure outsourcing of modular exponentiations, the proposed algorithm designed for this scenario takes advantage of that the bases of modular exponentiations do not need to be protected. Therefore, our algorithm is efficient. Furthermore, the evaluation shows that it has high efficiency and checkability as well. Specifically, the client-side cost is reduced to 5.6% of the original computation cost, and the probability that the client detects the misbehavior of server is close to 1.