Re: 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));
}