Реализации алгоритмов/P-1 метод Полларда: различия между версиями
Содержимое удалено Содержимое добавлено
Vlsergey (обсуждение | вклад) Новая страница: «=== С/С++ === Ниже приведен заготовка функции на С++, реализующая первую стадию алгоритма. Нек…» |
Urm ravil (обсуждение | вклад) Нет описания правки |
||
Строка 1:
=== С/С++ ===
Ниже приведен заготовка функции на С++, реализующая первую
*: Класс Т — класс, с которым производятся вычисления, это может быть как стандартный числовой класс, например ''long int'', так и пользовательский класс, для которого необходимо [[Перегрузка процедур и функций | перегрузить]] функции и операции '+', '-', '+=', '-=', взятия остатка по модулю n '%', '%='.
*: Массив q — массив простых чисел меньше либо равных b (B в предыдущих обозначениях).
*: Массив p — массив простых чисел между границами <math>~ B1 </math> и <math>~B2= B1^2</math>.
*: Необходимо определить так же функции mulmod(T a,T b,T n)— перемножение чисел a,b по модулю n   <math>~ mulmod(a, b, n) = ab \mod n </math> , gsd(T a,T b) — поиск НОД чисел a и b, powmod(T a,T b, T n) — возведение числа a в степень b по модулю n <math>~ powmod(a, b, n) = a^b \mod n </math>.
*: Первая стадия выполняется для нескольких а.
Строка 9 ⟶ 10 :
<source lang=c>
template <class T>
T
{
const T b1=13;
const T b2=169; //b2=b1^2
T p[]= [13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167];
size_t i;
T a = 5 % n;
{
▲ // несколько попыток алгоритма
▲ T a = 5 % n;
{
▲ for (int j=0; j<10; j++)
a += 3;
a %= n;
}
▲ // ищем такое a, которое взаимно просто с n
▲ while (gcd (a, n) != 1)
{
▲ mulmod (a, a, n);
continue;
T g = gcd (aa-1, n);
if (1 < g && g < n)
return g;
}
}
▲ // вычисляем a^M
T apowM=aa;//apowM=a^M посчитанное в первой стадии
▲ for (size_t i = 0; i < sizeof q / sizeof q[0]; i++)
for (i = 0; i< (sizeof q / sizeof p[0])-1; i++)
{
▲ T qq = q[i];
p[i]= p[i+1]-p[i]; //переопределяем массив p
▲ T e = (T) floor (log ((double)b) / log ((double)qq));
}
▲ T aa = powmod (a, powmod (qq, e, n), n);
for ( i = 0; i< (sizeof q / sizeof p[0])-1; i++)
▲ if (aa == 0)
{
aa = mulmod(aa, powmod(aa, p[i], n), n);
g = gsd (aa-1, n);
▲ // проверяем, не найден ли ответ
}
return g;▼
▲ // если ничего не нашли
}
| |||