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.
