The Paillier encryption scheme is a homomorphic encryption scheme that includes modular exponentiation in its encryption algorithm. Due to the high computational cost of modular exponentiation, outsourcing these operations to cloud servers can effectively reduce the computational burden on the local server. However, there is a risk of plaintext leakage during the outsourcing process. Therefore, we propose a secure outsourcing scheme for the Residue Number System (RNS) based on the Paillier cryptosystem. The scheme leverages the decomposition and parallel computation features of the RNS for large integers, splitting the plaintext for representation. This prevents information leakage during transmission and encryption. The local server allocates the public key and appropriate plaintext components to the cloud servers based on their computational capabilities, ensuring load balancing. The cloud servers then use the Paillier encryption algorithm to encrypt their respective plaintext components and return the results to the local server. The local server combines the ciphertext components using the Chinese Remainder Theorem to obtain the plaintext, achieving secure and efficient Paillier encryption outsourcing. Additionally, we conducted correctness and security analyses of the proposed scheme and evaluated its performance through experiments. The experimental results demonstrate that our scheme improves encryption time by approximately 67% compared to the non-outsourced Paillier scheme and reduces execution time on the local server by approximately 38%.