We had a assignment in math where we used Maple to learn a tiny bit about algorithm and encryption and one of the bonus goal was to decrypt another’s student message by cracking his n, n being the product of two ~50 digits prime number, p and q.

Maple being poorly optimize and working in serial was nowhere close to be able to factor the 100 digits number in over 18h of computing.

Since I know that parallel computing is a better approach and that I have a GTX570, I thought I could kill 2 bird with one stone and learn a bit of CUDA and finding the Teacher n. (If you find this one you can find the n of every other students)

I’ll like to know how to translate this algorithm in CUDA and parallelize it or if there would be a better one as that one was the best I could do with the program I had.

p= 50 digits prime (not know)

q= 50 digits prime (not know)

n= p*q (know)

p= squareroot(n) lower to last odd Interger

q= n/p

while q is not an integer

p= p-2

q= n/q

return/print p and q

I have a bit of experience with Java(Netbeans) not C/C++ unfortunately.

Also would anyone have an estimate on how long it would take for one GTX570/i5-2500k?