Write a program to implement RSA algorithm in Java. The program prompts the user for the values of p, q, d and the encrypted message (based on these parameters). It decrypts and outputs the original string message. The Java program needs to accommodate 64-bit computation, but it must use primitive data types only, e.g., long.