Primality test function doesn't work on large numbers?

[Timon Gehr via Digitalmars-d-learn]

On 08.01.2017 08:52, 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

Fixed version:

import std.bigint;
import std.stdio;

private alias bigint = BigInt;
bigint pow(bigint base,bigint exponent){
     bigint tmp=1;
     for(auto x=base,y=exponent;y;x*=x,y/=2)
         if(y%2) tmp*=x;
     return tmp;
}
bigint powm(bigint base,bigint exponent,bigint modulus){
     bigint tmp=1;
     for(auto x=base,y=exponent;y;x=x*x%modulus,y/=2)
         if(y%2) tmp=tmp*x%modulus;
     return tmp;
}
private pragma(inline, true) bigint pow(int base, bigint exponent) {
     return pow(bigint(base), exponent);
}
private pragma(inline, true) bigint pow(bigint base, int exponent) {
     return pow(base, bigint(exponent));
}
private pragma(inline, true) bigint pow(int base, int exponent) {
     return pow(bigint(base), bigint(exponent));
}

// Credit to 
http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf appendix C.3
private bigint genprime(int bits, int numtests){
     import std.random: uniform;

     bool mrprime(bigint integer, int iterations) {
         if(integer%2==0)
             return false;

         bigint m, a = 0, tmp = integer, b, z;
         int length;

         for(m=integer-1;m%2==0;m/=2,++a){}
         assert((integer-1)%pow(bigint(2), a)==0);

         while(tmp != 0) {
             tmp >>=1;
             length += 1;
         }

         for (int i=0; i<iterations; i++) {
             // Create b such that b has the same number of bits as 
"integer"
             for (int j = 1; j<=length; j++) {
                 b <<= 1;
                 b += uniform(0, 2);
             }
             while ((b <= 1) || (b >= (integer-1))) {
                 b = 0;
                 for (int j = 1; j<=length; j++) {
                     b <<= 1;
                     b += uniform(0, 2);
                 }
             }

             z = powm(b, m, integer);
             if((z == 1) || (z == integer-1))
                 goto endofloop;

             for(int k=1; k<=a-1; k++) {
                 z = z*z%integer;
                 if(z == integer-1)
                     goto endofloop;
                 if(z == 1)
                     return false;
             }
             return false;
         endofloop:
         }
         return true;
     }

     bigint genbigint(int numbits) {
         bigint tmp;
         while (numbits --> 0) {
             tmp <<= 1;
             tmp += uniform(0, 2);
         }
         return tmp;
     }
     bigint currnum;
     while (true) {
         currnum = genbigint(bits);
         if (mrprime(currnum, numtests)) {
             return currnum;
         }
     }
     assert(0);
}

void main(){
     writeln(genprime(300,30));
}