Алгоритм Лемана не имеет смысла
Я пытался реализовать тест Лемана, но он не работает с первого раза. Я следовал тому, что все описали
- Вычислить r = [a ^ ((p -1) / 2)] mod p
- Если r не 1 или -1, то p определенно не простое число.
- Если r = 1 или -1, вероятность того, что p не простое, составляет не более 50 процентов.
Независимо от того, как я это сделал, это никогда не работает. Я даже пытался кодировать его
p = 7; //definitely a prime number
double e = (p - 1 )/2;
int f = (int)pow(3, e) % p;
cout << f <<endl;
и е закончилось как 6
любая помощь будет оценена
Решение
Вычисляя f, вы сделали шаг 1, но вы пропускаете шаги 2 и 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;
Оператор % это мод-оператор. Это уменьшает левый номер мод правый номер. подобно 10 % 8 является 2, Важно отметить, что когда левый номер положительный, результат всегда положительный. Так что если a = b - 1, a % b является aто есть, если a = -1 mod b, затем a % b == a,
Состояние f % p != 1 && f % p != p - 1 на английском есть (f % p not equal 1) AND (f % p not equal p - 1)
Одна проблема состоит в том, что это переполнится для больших p,
Если вы хотите избежать использования библиотеки bignum, вы можете определить свой собственный pow следующим образом:
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
}
Вы бы использовали это как int f = pow(3, e, p);, Я не уверен, как связать, когда это будет переполнено, но это будет намного больше, чем обычно pow,
Другие решения
f заканчивается как 6, потому что 6 равно -1 mod 7, надеюсь, это поможет.