Обсуждение:Тест Люка — Лемера

Вопрос: для $p=2$ данный тест не работает ($L_{1}=4,4\mod 3\neq 0$). На основании чего получено простое число Мерсенна $M_{2}=2^{2}-1=3$? Dark Magus 05:58, 10 апреля 2006 (UTC)

Добавил условие $p\geqslant 3$. Maxal 13:33, 16 декабря 2009 (UTC)

Нужно переименовать в Т л.-л. для чисел мерсенна, поскольку существует более общий вариант этого теста: en:Lucas–Lehmer test `a5b 09:59, 12 июня 2006 (UTC)

Когда будет статья об общем варианте теста — тогда и переименуем. Maxal 13:33, 16 декабря 2009 (UTC)

Пожалуй уже можно переименовать :-) Статья об общем варианте теста уже есть. Sonic86 09:18, 13 января 2012 (UTC)Sonic86

Но общий вариант называет тестом Люка, так что разночтений здесь нет. Maxal 14:01, 13 января 2012 (UTC)

Циклический сдвиг

• причём умножение на 2 k {\displaystyle 2^{k}} 2^k по модулю M p {\displaystyle M_{p}} M_{p} равносильно левому циклическому сдвигу на k {\displaystyle k} k бит

В АИ явная опечатка. Почитайте где угодно (хотя бы тут), умножение на 2^k эквивалентно ОБЫЧНОМУ сдвигу на k бит, а не циклическому (соответственно, деление — сдвигу вправо). Что, кстати, подтверждается и самим АИ, т.к дальше (512 страница) приводится алгоритм 9.2.13, где используется самый обычный сдвиг вправо. Алгоритм прошу не удалять, он взят из АИ (только там он приведен в общем виде, для чисел вида 2^n+c, в случае чисел Мерсена c=-1) 212.73.99.89 05:46, 18 сентября 2019 (UTC)

Вы апеллируете к АИ, соответственно, сперва следует опровергнуть утверждение из АИ, после чего вносить правки. Ссылка на другую статью из Википедии, равно как и рекомендация «почитать где угодно», не может являться опровержением чего-либо. Указание на алгоритм 9.2.13 также не является опровержением корректности формулировки теоремы, поскольку в нем не используется вторая часть теоремы (в явном виде). Опровержением может быть, например, ссылка на другие АИ. А пока настоятельно рекомендую отменить свою последнюю правку, которая является прямым нарушением ВП:ПТО и ВП:ВПР. Derise (обс.) 11:18, 18 сентября 2019 (UTC)

Видите ли, то что умножение-деление на степень двойки n эквивалентно сдвигам на n бит — настолько очевидный факт для любого программиста (и вообще любого знакомого с двоичной системой счисления), что мне и в голову не пришло это доказывать, это как доказывать что 2*2=4. Но если вам нужна ссылка, то [вот] пожалуйста. "Указание на алгоритм 9.2.13 также не является опровержением корректности формулировки теоремы, поскольку в нем не используется вторая часть теоремы (в явном виде)." — теорема заключается в том, что деление по модулю на 2^n-1 можно заменить указанной суммой. Второе утверждение это уже не теорема, а пояснение, чем именно полезно такое разложение — а полезно оно тем, что обе части можно вычислить быстрыми битовыми операциями. В принципе, согласен, что эту расшифровку лучше вынести из самой теоремы, т.к. она относится уже не столько к теореме сколько к реализации алгоритма на компьютере. 212.73.99.89 05:34, 19 сентября 2019 (UTC)

Желательно, конечно, ссылаться на сам источник, а не на его перепечатку на каком-то сайте (собственно, вверху статьи эта ссылка и указана). В любом случае, содержание приведенной статьи не имеет никакого отношения к обсуждаемому вопросу. Вам нужно, ссылаясь на АИ, опровергнуть ту часть теоремы, с формулировкой которой вы не согласны. Derise (обс.) 07:39, 19 сентября 2019 (UTC)

В АИ не опечатка. При подсчёте остатка по модулю вида $2^{p}-1$ умножение на $2^{k}$ действительно эквивалентно циклическому сдвигу. adamant (обс./вклад) 21:05, 3 октября 2019 (UTC)