Primality test function doesn't work on large numbers?

[Eugene Wissner via Digitalmars-d-learn]

On Sunday, 8 January 2017 at 07:52:33 UTC, Elronnd wrote:
> I'm working on writing an RSA implementation, but I've run into 
> a roadblock generating primes.  With a more than 9 bits, my 
> program either hangs for a long time (utilizing %100 CPU!) or 
> returns a composite number.  With 9 or fewer bits, I get 
> primes, but I have to run with a huge number of iterations to 
> actually _get_ a random number.  It runs fast, though.  Why 
> might this be?  Code: http://lpaste.net/1034777940820230144

I haven't read your code very exactly, but I have an assumption 
and you can check if it is helpful:)

I think your actual problem is this line:

z = pow(b, m) % integer;

If it does what I think, it can be horribly slow and memory 
consuming. You have to implement your own pow function that does 
a ^ b mod c. Look into python source code or in "tanya" (D): 
https://github.com/caraus-ecms/tanya/blob/master/source/tanya/math/package.d. It is the same algorithm that phobos uses but with modulo operation built-in and a bit differently written (my code is based neither on python nor on phobos and uses a different bigint implementation). You can also rewrite pow(z, 2) % integer then. It will be faster.
Try to reduce bigint copying and arithmetic anyway if possible.