Реализацию на Java можно взять в исходниках JDK:
$JDK_HOME/src.zip/java/math/BigInteger.java,
функция BigInteger.probablePrime(). Исходники достаточно подробно откомментированы.
А также ту часть алгоритма RSA, где эта функция используется:
sun/security/rsa/RSAKeyPairGenerator.java 
