SICP Ex.1.28

[ivvan]

Sonic86 в сообщении #1149346 писал(а):

Обычное натуральное число

Оно одинаково для всех $a$?

[Sonic86]

ivvan в сообщении #1149347 писал(а):

Sonic86 в сообщении #1149346 писал(а):

Обычное натуральное число

Оно одинаково для всех $a$?

Нет же, у нас уже рассматриваются только те $a$, которые проходят тест Ферма. И вообще, это посылка, т.е. туда попадают только те $a$, которые туда попадают

[ivvan]

Sonic86 в сообщении #1149352 писал(а):

И вообще, это посылка, т.е. туда попадают только те $a$, которые туда попадают

А зачем нужна эта посылка?

[ivvan]

Sonic86 в сообщении #1149049 писал(а):

Т.е. квадратные корни мы ищем не для всех $a$, а только для таких, для которых $a^{n-1}\equiv 1\pmod n$.

В общем, я не понял, почему это так, но похоже, это верно (проверил до 2000).

[Sonic86]

ivvan в сообщении #1149495 писал(а):

Sonic86 в сообщении #1149049 писал(а):

Т.е. квадратные корни мы ищем не для всех $a$, а только для таких, для которых $a^{n-1}\equiv 1\pmod n$.

В общем, я не понял, почему это так, но похоже, это верно (проверил до 2000).

Похоже, мои рассуждения выше про мощность группы скорее всего неверны. Там на самом деле работает теорема Рабина. Она легко гуглится, но я ее ниасилил + я все еще путаю это с тестом Миллера.
А почему брать только $a^{n-1}\equiv 1\pmod n$ - это я писал:

Sonic86 в сообщении #1149049 писал(а):

Для прозвольного нечетного $n$ условие $a^{n-1}\equiv 1\pmod n$ необходимо, но не достаточно для того, чтобы $n$ было простым. Т.е. если оно неверно, то $n$ явно составное.

[ivvan]

Рассмотрим нечётное число $n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$. Мультипликативная группа его вычетов имеет вид $\mathbb{Z}_{p_1^{\alpha_1-1}(p_1-1)}\oplus\mathbb{Z}_{p_2^{\alpha_2-1}(p_2-1)}\oplus\dots\oplus\mathbb{Z}_{p_k^{\alpha_k-1}(p_k-1)}$. $1$ соответствует $(0,0,\dots,0)$, а $-1$ - $(p_1^{\alpha_1-1}\frac{p_1-1}{2},p_2^{\alpha_2-1}\frac{p_2-1}{2},\dots,p_k^{\alpha_k-1}\frac{p_k-1}{2})$. Видно, что подгруппа элементов с свойством $a^{n-1}\equiv1\pmod{n}$ имеет вид $G\cong\mathbb{Z}_{(n-1,p_1-1)}\oplus\mathbb{Z}_{(n-1,p_2-1)}\oplus\dots\oplus\mathbb{Z}_{(n-1,p_k-1)}$. Представим $(n-i,p_i-1)=2^{s_i}m_i$, где $m_i$ - нечётное число,$s_i\geqslant1$. Тогда $G\cong\mathbb{Z}_{2^{s_1}}\oplus\mathbb{Z}_{2^{s_2}}\oplus\dots\oplus\mathbb{Z}_{2^{s_k}}\oplus\mathbb{Z}_{m_1}\oplus\mathbb{Z}_{m_2}\oplus\dots\oplus\mathbb{Z}_{m_k}$, и $-1$ соответствует $(2^{s_1-1},2^{s_2-1},\dots,2^{s_k-1},0,0,\dots,0)$.
При возведении элемента в квадрат его компоненты из $\mathbb{Z}_{2^{s_i}}$, если не нулевые, увеличивают кратность множителя 2, каким образом могут стать нулевыми; другие компоненты стать нулевыми не смогут, если ими не были. Умножение на основание вычисляемой по приведённому на 1 странице алгоритму степени производится лишь после возведения в квадрат, поэтому придаёт промежуточному результату ту же кратность 2 у компонентов при $\mathbb{Z}_{2^{s_i}}$, каковая у самого основания. Одинаковое изменение этой кратности не позволяет встретиться нетривиальным корням при нахождении степени по основанию, компоненты которой при $\mathbb{Z}_{2^{s_i}}$ имеют кратность $s_i-t$, где $0\leqslant t\leqslant\min(s_1,s_2,\dots,s_k)=s$. У других оснований нетривиальный корень обязательно встретится при возведении в степень $n-1$ на последних возведениях в квадрат (после последнего умножения на основание).
Таким образом, число элементов, у которых при возведении в степень $n-1$ не появляется нетривиальных корней, равно $1^km_1m_2\dots m_k+1^km_1m_2\dots m_k+2^km_1m_2\dots m_k+\dots+2^{(s-1)k}m_1m_2\dots m_k$, что больше $2^{s_1+s_2+\dots+s_k-1}m_1m_2\dots m_k$ (число всех рассматриваемых элементов) при $k=1$.

[Sonic86]

Это Вы что считаете? Вероятность извлечение квадратного корня по модулю $n$?
И можно уточнить, что получилось, т.к. меня смущают 2 одинаковых первых слагаемых:

ivvan в сообщении #1149918 писал(а):

Таким образом, число элементов, у которых при возведении в степень $n-1$ не появляется нетривиальных корней, равно $1^km_1m_2\dots m_k+1^km_1m_2\dots m_k+2^km_1m_2\dots m_k+\dots+2^{(s-1)k}m_1m_2\dots m_k$, что больше $2^{s_1+s_2+\dots+s_k-1}m_1m_2\dots m_k$ (число всех рассматриваемых элементов) при $k=1$.

Кроме того, $m_1...m_k$ можно за скобку вынести, а в вероятности вообще сократить.
А вычисления не проверяли?

Я еще ссылку дам на теорему Рабина, просто для того, чтобы было видно, как считал автор: http://www.uic.unn.ru/~zny/compalg/Lectures/rabin.pdf (мне кажется, что как-то не так, но я не вникал)

[ivvan]

Sonic86 в сообщении #1150143 писал(а):

Это Вы что считаете? Вероятность извлечение квадратного корня по модулю $n$?

Количество чисел $0<a<n$, на которых алгоритм не выявляет составности $n$.

Sonic86 в сообщении #1150143 писал(а):

И можно уточнить, что получилось, т.к. меня смущают 2 одинаковых первых слагаемых:

Первое слагаемое соответствует взятию компонент максимальной краткости двойки, т.е. нейтральных (нулевых); второе - предмаксимальной, т.е. их вторые степени (кратные) - нейтральные (нулевые) элементы, но сами таковыми не являются, таких тоже по одному на каждый $\mathbb{Z}_{2^{s_i}}$. До того рассуждения понятны?

Sonic86 в сообщении #1150143 писал(а):

А вычисления не проверяли?

После того, как написал - нет.

Sonic86 в сообщении #1150143 писал(а):

как считал автор:

Какой автор?