k = 150;

(*  Generate random primes p≠q of bitlength k s . t .  3 does not divide (p - 1)(q - 1) . 
Assign to m the product of p and \(q . \ 	
Assign\) to φ the Euler totient function φ(m) value. 
Assign to d the inverse of 3 modulo φ(m). 
Assign to \(d\&^\) the approximation of d (without using m' 
                  s factorization) .  
Print the values of d and \(d\&^\) to show that the first half of the digits are equal.  *)

	While[p = Random[Integer, {(2^(k - 1)), (2^k) - 1}]; 
        Mod[p - 1, 3] == 
            0 || ! PrimeQ[p]]
	While[q = Random[Integer, {(2^(k - 1)), (2^k) - 1}]; 
        p == q  || 
          Mod[q - 1, 3] == 
            0 || ! PrimeQ[q]]
	m  =  p q;
	φ  = (p - 1) (q - 
                1);
	d  =  
          Mod[First[
              Last[ExtendedGCD[
                  3, φ]]] , φ];
	\(d\&^ = \ 
          Floor[\((1 + 2 \((m - 2 \@ m + 1)\))\)\ /\ 
              3];\)
	Print["d = ",  d]
	\(Print[\*""\!\(d\&^\) = "", \ d\&^]\)