RSA selecting encryption key c++ integer

Question

In my RSA cryptosystem, I am trying to select an encryption key e that is relatively prime to phi(n).

phi(n) is the product of two numbers, p-1 & q-1, where p and q are both prime. Those primes are generated using the naive primality test (yes, I know it's inefficient).

When I execute my program, I get the following output:

***** p *****
878222789

***** q *****
851559637

***** n = p x q *****
3523942633

***** phi(n) = (p-1)x(q-1) *****
1794160208

***** e *****
99

***** d *****
47835

Problem is, every time I run this program, e always ends up equaling 99 or 97. It is the only constant in this output. I am almost positive my GCD algorithm is correct. But it's the only subroutine in select_e().

Relevant functions:

void select_e(uint &e, const uint phi_n)
{ // e = encryption key
    for(int i=3;i<100;i++) {
        if(gcd(phi_n,i) == 1) {
            e = i;
            break;
            }
    }
    printf("\n***** e *****\n%u\n",e);
}

uint gcd(uint a, uint b) {
    uint temp;
    while (b!=0) {
        temp = b;
        b = a%b;
        a = temp;
    }
    return a;
}

EDIT***********************

Okay, so I've added a break statement in select_e() which has caused the program to output a value of usually 3 or 5 for e. Now, as I understand it, the botched decryption is the result of integer overflow from multiplying two 32-bit integers and storing the value in another 32-bit integer. Therefore, I have modified my program to generate smaller p and q with a modulo. Here is that function:

void generate_pq(uint &p, uint &q)
{
    srand(time(NULL));
    bool repeat = false;
    printf("\nGenerating keys...\n");

    while(!repeat) {
        p = rand()%100;
        repeat = isPrime(p);
    }
    repeat = false;
    while(!repeat) {
        q = rand()%100;
        repeat = isPrime(q);
    }
    printf("\n***** p *****\n%u\n\n***** q *****\n%u\n",p,q);
}

The problem now is that sometimes, I luck out and the message is decrypted successfully. Other times it does not work. Here is an example of a botched decryption:

Generating keys...

***** p *****
79

***** q *****
49

***** n = p x q *****
3871

***** phi(n) = (p-1)x(q-1) *****
3744

***** e *****
5

***** d *****
749

Message: fdsa 

Cipher: �/�J

Decrypted Message: �a

I know the decryption and encryption functions work. I have tested them separately and examined the algorithms. They are not the source of the problem. I will provide them for posterity if requested.

Answer 1

Well, you select the first possible number greater than two. Since the number of primes factors of any large number is extremely small compared to the number itself, you cannot expect the test if(gcd(phi_n,i) == 1) to fail many times. Maybe it fails once, maybe it fails twice, but I wouldn't even want to wait until it fails ten times...

So the answer would be to randomly pick an i in each iteration of the loop instead of simply counting up.

---

Btw: Your output is funny in another way: 3523942633 is definitely not the product of 878222788 and 851559636. Not sure why precisely, but it looks like an inadvertent truncation due to the use of 32 bit integers...