Lehmann algorithm doesn't make sense

Question

I tried implementing the Lehmann test but it doesn't work the first time round. I followed what everyone described

1. Calculate r = [ a^( (p -1) / 2) ] mod p
2. If r is not 1 or –1 then p is definitely not a prime.
3. If r = 1 or –1 the likelihood that p is not prime is at most than 50 percent.

No matter how I did it, it never works. I even tried hard coding it

p = 7; //definitely a prime number

double e = (p - 1 )/2;

int f = (int)pow(3, e) % p;

cout << f <<endl;

and f ended up as 6

any help will be appreciated

Answer 1

By calculating f, you've done step 1, but you're leaving out steps 2 and 3.

p = 7; //definitely a prime number

double e = (p - 1 )/2;

int f = (int)pow(3, e) % p;

// Step 2
if(f % p != 1 && f % p != p - 1)
    cout << p << " is definitely not prime." << endl;
else // If not step 2, then step 3
    cout << p << " has 50% probability of being prime." << endl;

The operator % is the mod operator. It reduces the left number mod the right number. Like 10 % 8 is 2. It's important to note that, when the left number is positive the result is always positive. So if a = b - 1, a % b is a, which is to say that, if a = -1 mod b, then a % b == a.

The condition f % p != 1 && f % p != p - 1 in English is (f % p not equal 1) AND (f % p not equal p - 1)

One problem is that this will overflow for big p.

If you want to avoid using a bignum library, you can define your own pow like so:

unsigned int my_pow(unsigned int base, unsigned int expon, unsigned int mod){
    unsigned int result = base;
    for(int i = 1;i < expon;i++)
        result = (result * base) % mod;
    return result
}

You would use this like int f = pow(3, e, p);. I'm not sure how to bound when this will overflow, but it will be a lot larger than the normal pow.