## digitalmars.D.learn - Primality test function doesn't work on large numbers?

- Elronnd (7/7) Jan 07 2017 I'm working on writing an RSA implementation, but I've run into a
- Eugene Wissner (10/17) Jan 08 2017 I haven't read your code very exactly, but I have an assumption
- Timon Gehr (90/97) Jan 08 2017 Fixed version:
- Elronnd (15/15) Jan 09 2017 Thank you! Would you mind telling me what you changed aside from
- Eugene Wissner (5/20) Jan 10 2017 Yes. You would normally get some random string/value only once
- Timon Gehr (35/50) Jan 12 2017 1. This code:

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

Jan 07 2017

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/1034777940820230144I 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.

Jan 08 2017

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/1034777940820230144Fixed 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)); }

Jan 08 2017

Thank you! Would you mind telling me what you changed aside from pow() and powm()? diff isn't giving me readable results, since there was some other stuff I trimmed out of the original file. Also, while this is a *lot* better, I still get some lag generating 1024-bit primes and I can't generate larger primes in a reasonable amount of time. Maybe my genbigint() function is to blame? It isn't efficient: bigint genbigint(int numbits) { bigint tmp; while (numbits --> 0) { tmp <<= 1; tmp += uniform(0, 2); } return tmp; }

Jan 09 2017

On Tuesday, 10 January 2017 at 03:02:40 UTC, Elronnd wrote:Thank you! Would you mind telling me what you changed aside from pow() and powm()? diff isn't giving me readable results, since there was some other stuff I trimmed out of the original file. Also, while this is a *lot* better, I still get some lag generating 1024-bit primes and I can't generate larger primes in a reasonable amount of time. Maybe my genbigint() function is to blame? It isn't efficient: bigint genbigint(int numbits) { bigint tmp; while (numbits --> 0) { tmp <<= 1; tmp += uniform(0, 2); } return tmp; }Yes. You would normally get some random string/value only once and then apply md5 or better sha512 on it (several times if you want to have a more secur hash) to get the right length and then get the hex digest and load it into bigint.

Jan 10 2017

On 10.01.2017 04:02, Elronnd wrote:Thank you! Would you mind telling me what you changed aside from pow() and powm()?1. This code: // make 2^a = integer-1 while ((integer-1)%(pow(bigint(2), a))!=0) a--; m = (integer-1) / pow(bigint(2), a); a starts out as integer-1, so this computes many big powers of two if integer-1 has only a few factors of 2 (which is very likely if integer is a random number), so I changed this to: for(m=integer-1;m%2==0;m/=2,++a){} where a starts from 0. Now it just counts the factors of two and m is computed on the fly. 2. There was a bug in the Miller-Rabin implementation. (There are two cases where the function should return false. Only one was present.)diff isn't giving me readable results, since there was some other stuff I trimmed out of the original file. Also, while this is a *lot* better, I still get some lag generating 1024-bit primes and I can't generate larger primes in a reasonable amount of time. Maybe my genbigint() function is to blame? It isn't efficient: bigint genbigint(int numbits) { bigint tmp; while (numbits --> 0) { tmp <<= 1; tmp += uniform(0, 2); } return tmp; }This should be quite fine, as its running time is linear in numbits (when rejection sampling to get into the right range, the running time will still be linear in numbits in expectation). I would expect that the problem is pow and powm, as for the typical bases, exponents and moduli you use, they have running time Ω((log(modulus)+log(exponent))*log(exponent)). The actual asymptotic running time is significantly more than this bound, as multiplication is done using Karatsuba. Maybe you can get a relevant speedup by using a different bigint implementation. The std.bigint documentation says that it is optimized for numbers up to ~1000 decimal digits and that you should probably use GMP for larger numbers. https://dlang.org/phobos/std_bigint.html GMP also has implementations of pow and powm built-in. Other than that: 1. You can save a constant factor of time in genbigint by generating more than one bit at a time. (But I don't think this is the bottleneck.) 2. Generating only odd candidates should give you a factor of two. 3. In mrprime, you should check other small primes other than 2, as a random number is likely to have a small prime factor. If what you need is some fast black-box to generate large primes, you can probably use existing libraries.

Jan 12 2017