SICP Ex.1.28

[ivvan]

Цитата:

Можно, кроме того, доказать, что если $n$ — нечетное число, не
являющееся простым, то по крайней мере для половины чисел $a < n$ вычисление $an−1$ с помощью
такой процедуры обнаружит нетривиальный квадратный корень из $1$ по модулю $n$ (вот почему
тест Миллера–Рабина невозможно обмануть).

Однако $2^2=4,4^2=16=2\cdot 9-2$, т.е. нетривиальных корней по модулю 9 не обнаруживается. Что здесь неправильно?

[Deggial]

Тема перемещена из форума «Computer Science» в форум «Помогите решить / разобраться (М)»
Конечно: если в SICP написали чистую теоретико-числовую задачу, значит это Computer Science

[Sonic86]

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

вычисление $an−1$ с помощью
такой процедуры

Вычисление с помощью какой процедуры?

Попытка телепатии: Вы спрашиваете, почему если $n$ нечетное, то существуют нетривиальные квадратные корни из $1$ по модулю $n$?
Если да, то это сводится к делителям нуля в кольце вычетов по модулю $n$, но да, Вы верно отметили, что если $n=p^k,p>2$, то нетривиальных корней у уравнения $x^2\equiv 1\pmod{p^k}$ не будет. Это легко доказать от противного (попробуйте - там общий вид делителей нуля простой). Но прикол в том, что числа вида $n=p^k$ в поле зрения тестов проверки простоты или алгоритмов факторизации не попадают, просто потому, что их очень легко разложить на множители без Миллеров и Рабинов.
Если нет, то напишите вопрос понятнее.

[ivvan]

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

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

вычисление $an−1$ с помощью
такой процедуры

Вычисление с помощью какой процедуры?

Во-первых, у меня вместо $an−1$ должно быть $a^{n-1}$, во-вторых, вот описание алгоритма:

Цитата:

Проверяя простоту числа $n$ методом Миллера–Рабина, мы берем случайное число $a < n$ и возводим его в $(n - 1)$-ю степень по модулю $n$ с помощью процедуры expmod. Однако когда в процедуре expmod мы проводим возведение в квадрат, мы проверяем, не нашли ли мы «нетривиальный квадратный корень из $1$ по модулю $n$», то есть число, не равное $1$ или $n - 1$, квадрат которого по модулю $n$ равен $1$. Можно доказать, что если такой нетривиальный квадратный корень из $1$ существует, то $n$ не простое число.

(Судя по Википедии, правда, алгоритм организуется по-другому.) Я для $n=2,\dots,100$ вычислил отношение обнаруживающих нетривиальные корни единицы $a$ к $n-1$, и это отношение не превысило $0,5$. Вопрос в том, как понимать процитированное утверждение в начальном посте.

[Sonic86]

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

Я для $n=2,\dots,100$ вычислил отношение обнаруживающих нетривиальные корни единицы $a$ к $n-1$, и это отношение не превысило $0,5$.

Да ну! Вот контрпример:
$n=15$, под $\to$ понимается отображение $x\to x^2$.
$1 \to 1$
$2 \to 4 \to 16=1$
$4 \to 16=1$
$7 \to 49 = 4 \to 16=1$
$-7 \to 64 = 4 \to 16=1$
$-4 \to 16=1$
$-2 \to 4 \to 16=1$
$-1 \to 1$
Таким образом, здесь $8=\varphi(15)$, из них $1,-1$ дают тривиальные корни из единицы, а остальные 6 дают нетривиальные корни $\pm 4$. Т.е. доля успешных нахождений равна $\frac{6}{8}>\frac{1}{2}$.
У Вас ошибка в вычислении где-то.

[ivvan]

Процедура expmod определяется так:

Используется синтаксис Scheme

(define (expmod base exp m)
   (cond ((= exp 0) 1)
         ((even? exp)
          (remainder (square (expmod base (/ exp 2) m))
                     m))
         (else
          (remainder (* base (expmod base (- exp 1) m))
                     m))))

Надеюсь, больше ничего не забыл.

[Sonic86]

А, ну так expmod Вам сначала возводит число в квадраты, а потом - в оставшийся нечетный множитель. А для поиска нетривиальных корней из $1$ надо наоборот (хотя для $n=15$ должно было сработать).
В Вики этот момент отражен в коде, но просто не выделен.
Понятно почему?
Не, самого вызывающего кода, кажется, не хватает тоже для того, чтобы дать ответ. Сама expmod нормально написана. Но в любом случае частота должна быть не меньше $\frac{1}{2}$.

(Оффтоп)

а я правые скобки лесенкой писал

[ivvan]

Для

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

$n=15$

получается:

$$2^{14}=((2^2\cdot 2)^2\cdot 2)^2=((4\cdot 2)^2\cdot 2)^2=((-7)^2\cdot 2)^2=(4\cdot 2)^2=(-7)^2=4,$$$$4^{14}=((4^2\cdot 4)^2\cdot 4)^2=((1\cdot 4)^2\cdot 4)^2,$$$$7^{14}=((7^2\cdot 7)^2\cdot 7)^2=((4\cdot 7)^2\cdot 7)^2=((-2)^2\cdot 7)^2=(4\cdot 7)^2=(-2)^2=4,$$

и для противоположных вычетов у результатов только знаки меняются после умножения на возводимое число. Таким образом, получаются только 2 выявляющих нетривиальный корень числа.

-- 04.09.2016, 13:38 --

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

Не, самого вызывающего кода, кажется, не хватает тоже для того, чтобы дать ответ.

Плохо понял, какие код и ответ имеются в виду.

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

(Оффтоп)

а я правые скобки лесенкой писал

Тот код просто скопирован из книги. Лесенкой это так

Используется синтаксис Scheme

(define (expmod base exp m)
    (cond ((= exp 0) 1)
          ((even? exp)
           (remainder (square (expmod base (/ exp 2) m))
                      m
           )
          )
          (else
           (remainder (* base (expmod base (- exp 1) m))
                      m
           )
          )
    )
)

?

[Sonic86]

Блин, я беру таймаут. Я думал, что я понимаю этот тест, а похоже, что нет, надо читать.
Потому что если возводить $a$ именно в степень $n-1$, то просто так ничего не получится - $1$ будет встречаться редко. И там вся надежда не на $1$, а на $\gcd((a^{\frac{n-1}{2^k}}-1)\bmod n,n)$. В Вики и в SICP этого я не вижу, вижу в Василенко - там понятно изложено, но надо читать.
Выше про получение $1$ я говорил в случае, если возводить в степень $\frac{\varphi(n)}{2^s}$, а ее нам неоткуда взять.

(Оффтоп)

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

Лесенкой это так

Угу

[arseniiv]

(Оффтоп)

Давайте не будем про лесенку, а то разовьётся оффтоп на тему «лесенка — это смертный грех: почему и как так».

[Sonic86]

Так, я дибил - все просто: нам же просто надо проверить, составное число или нет.

Вот есть малая теорема Ферма: для всех простых $p$ для любого $a$ $a^{p-1}\equiv 1\pmod p$
Для прозвольного нечетного $n$ условие $a^{n-1}\equiv 1\pmod n$ необходимо, но не достаточно для того, чтобы $n$ было простым. Т.е. если оно неверно, то $n$ явно составное.
А если же $a^{n-1}\equiv 1\pmod n$ верно, то это довольно информативно: представим $n-1=2^s q$, тогда, если $b=a^{\frac{n-1}{2^s}}\not\equiv 1\pmod p$ (что маловероятно), то мы будем вычислять $b^2,b^4,b^8,...,$, на каком то шаге по условию мы получим 1, значит на предыдущем шаге мы получим нетривиальный квадратный корень из 1 по модулю $n$.
Т.е. квадратные корни мы ищем не для всех $a$, а только для таких, для которых $a^{n-1}\equiv 1\pmod n$. Таких $a$ грубо говоря мало. И вот только для таких $a$ (а не для всех) если мы будем искать квадратные корни из $1$, мы найдем нетривиальный квадратный корень более чем в половине случаев. Видимо именно это имеется ввиду в SICP 1.28, хотя условие написано немного неявно. И это даже очевидно, почему: степень группы делит $n-1$, значит $n-1=|\mathbb{Z}_n^{\times}|q=\varphi(n)q=2^swq$, число нетривиальных квадратных корней будет равно $2^s-2>2^{s-1}$ при $s>1$, а частота нетривиальных квадратных корней будет $>\frac{2^{s-1}}{2^s}=\frac{1}{2}$.
В нашем примере $n=15$, таких $a$ всего 2: $\pm 4$. И они сразу являются нетривиальным квадратными корнями, т.е. частота $=\frac{2}{2}=1>\frac{1}{2}$

З.Ы. В Василенко описан алгоритм Миллера. Это - другой алгоритм. Алгоритм Миллера-Рабина в нем - это теорема 1.55.

[ivvan]

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

$n-1=|\mathbb{Z}_n^{\times}|q=\varphi(n)q=2^swq$

Можете выписать это для $n=15$, а то рассуждения не очень понятны?

[Sonic86]

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

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

$n-1=|\mathbb{Z}_n^{\times}|q=\varphi(n)q=2^swq$

Можете выписать это для $n=15$, а то рассуждения не очень понятны?

Ага, я лгу. Надо точнее. Соотношение $n-1=|\mathbb{Z}_n^{\times}|q$ ложно, поскольку не для всех $a$ выполняется $a^{n-1}\equiv 1\pmod n$. Но если $a=b^r$, то м.б. $r(n-1)=|\mathbb{Z}_n^{\times}|q$. Но конкретно для $4$:
$\lambda(15)=\mathrm{lcm}(3-1,5-1)=4$ - максимальный порядок элементов группы $\mathbb{Z}_{15}^\times$
$4^{14}\equiv 2^{28}\equiv (2^{4})^7\equiv 1^7\equiv 1\pmod {15}$
значит, если будем возводить в степень в 2 раза меньшую, то получим какой-то квадратный корень из $1$:
$4^7\equiv 4\cdot 16^3\equiv 4 \not\equiv \pm 1 \pmod{15}$ - нетривиальный квадратный корень!

[ivvan]

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

Но если $a=b^r$, то м.б. $r(n-1)=|\mathbb{Z}_n^{\times}|q$.

Что за число $r$?

[Sonic86]

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

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

Но если $a=b^r$, то м.б. $r(n-1)=|\mathbb{Z}_n^{\times}|q$.

Что за число $r$?

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