The encryption process of LUC Cryptosystem is Ve(P,1)(mod N), while the decryption process is Vd(C,1)(mod N). An N is a product of two relatively primes p and q, P is a message and C is the ciphertext. To compute Ve and Vd, this system used Lucas Function. The Lucas Functions is a special form of second order linear recurrence relation using a large public integer. Recently, methods for fast LUC Cryptosystem computation in sequential and parallel techniques have been developed. We are introducing an important property of Lucas Function, V2n+1=PV2n–QV2n-1. This property could increase the performance of LUC Cryptosystem computation and reduce the computation time. We are implementing the method in parallel on distributed memory multiprocessor machine using message passing interface. In order to show a new parallel solution is better than the previous parallel solution; we will compare the simulation time, speedup and efficiency of both solutions.