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 - Calculate r = [ a^( (p -1) / 2) ] mod p - If r is not 1 or –1 then p is definitely not a prime. - 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

Accepted Answer

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`.

Lehmann algorithm doesn't make sense

Solution

Problem