Числа Ферма

[___ALBA___]

Помогите, желательно подробно, расписать ход действий для проверки простоты числа Ферма $F_3= 257$, с помощью алгоритма Пепина http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D1%81%D1%82_%D0%9F%D0%B5%D0%BF%D0%B8%D0%BD%D0%B0 (а то что-то непонятно).

[Kolyan1994]

Вам непонятно именно решение сравнения?

[___ALBA___]

не понятен весь алгоритм

[Kolyan1994]

Эх лет 10 назад я бы Вам помог, а сейчас увы., не вспомню

[___ALBA___]

Вот ещё ссылку нашел http://razvlekaykaa.ru/ko-rio45ri34/%D0%A2%D0%B5%D1%81%D1%82_%D0%9F%D0%B5%D0%BF%D0%B8%D0%BD%D0%B0

[Xaositect]

Собственно, что там непонятного? Берем тройку и возводим в квадрат $2^n - 1$ раз по модулю $F_n$. Получилось в итоге $F_n - 1$ - хорошо, не получилось - плохо.

[___ALBA___]

как я понял, нужно $3^{(2^3-1)}$mod257. В итоге получилось 131, но это не верно! Известно, что 257 это простое число. В чем ошибка?

[Xaositect]

Не $3^{2^3 - 1}$, а $3^{2^{2^3 - 1}}$

[Someone]

___ALBA___ в сообщении #738727 писал(а):

как я понял, нужно $3^{(2^3-1)}$mod257. В итоге получилось 131, но это не верно! Известно, что 257 это простое число. В чем ошибка?

1) Нужно $3^{2^{2^3-1}}\mod 257$, а не то, что Вы написали. 2) Вторая ошибка - неправильный код формулы. Должно быть $3^{(2^3-1)}\mod 257$.

[Xaositect]

Someone в сообщении #738741 писал(а):

Должно быть $3^{(2^3-1)}\mod 257$

Лучше $3^{(2^3-1)}\bmod 257$

[___ALBA___]

спасибо.напомните, если не сложно, как решать $3^{63}\bmod 257$

[Xaositect]

Откуда у Вас появилось 63? $2^{2^3 - 1} = 2^7 = 128$.
$3^{128}\bmod 257$ вычисляется последовательным возведением в квадрат: сначала $3^2$, потом $3^4 = (3^2)^2$, потом $3^8 = (3^4)^2$ и т.д. (на каждом шаге берем результат по модулю 257)