A. K. Lenstra and E. R. Verheul introduced a new public key system called XTR. They proposed two algorithms for finding primes
≡2 (mod 3), which are the key parameters for the XTR. One is unable to estimate in a simple way a running time the above algorithms, nor to give a mathematical proof of their correctness or prove that these algorithms works in polynomial time as suggested authors above mentioned cryptosytem. In this paper we propose theoretical algorithms which find primes as above. We give a mathematical proof of its correctness, under the assumption of some conjecture.