im.ralphholzmann

Finding P and Q in an RSA encryption

Our last assignment in File Structures dealt with decrypting messages ecrypted with RSA and a Viginere cypher. Our professor stressed that we should come up with the most efficient way of finding primes p and q given n, because that would require the most time and he would take points off for decrypters that take more than 10 seconds to run. Considering the assignment was due 5 minutes ago, I’m going to post my algorithm for finding P and Q which I’m pretty proud of because it runs really fast.

// Recursively tries to find prime numbers,
// p and q, given n, starting each factor
// at the square root of n. Values p and q are
// passed by reference so I wouldn’t have to
// return an array or anything
void findPQ(unsigned long n, int up, int down, unsigned long& p, unsigned long& q) {

bool foundUp, foundDown = false;

// Finds lower prime from root
while (!foundDown){
if (!isPrime(down)) {
down—;
} else {
foundDown = true;
}
}

// Finds upper prime from root
while (!foundUp){
if (!isPrime(up)) {
up++;
} else {
foundUp = true;
}
}

// Checks primes p and q against n
if( down > 0 && up < 65535) {
if ((up * down) == n) {
p = up;
q = down;
} else if ((up * down) < n) {
findPQ(n, (up + 2), down, p, q);
} else {
findPQ(n, up, (down - 2), p, q);
}
}
}

My decrypter can decrypt Hamlet in less than a second!

Have a good weekend.

~Ralph