Total video Encryption has been established as the most suitable technique to guarantee the security of digital video data during transmission but suffers wide adoption due to its large disk space and long processing time. This paper, therefore aimed at reducing the computational space complexity using Residue Number System (RNS). MPEG IV algorithm and encryption of pixel values using RNS traditional moduli set was employed for the encryption while a modified reverse converter was used for decryption. JAVA was used for the implementation while an evaluation was performed to compare the disk size of the cipher and deciphered videos. The scheme outperformed the existing evaluated cryptosystems in terms of cipher size, decrypted videos increased by 49% when compared with the original video. The space computational complexity problem in total video encryption was adequately reduced using RNS. It is recommended that RNS should be used for securing video transmission and storage.