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

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

Добавил условие $p⩾<!--\; ⩾\; -->3$$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^{p}-1$  умножение на $2^k$$2^k$  действительно эквивалентно циклическому сдвигу. adamant (обс./вклад) 21:05, 3 октября 2019 (UTC)Ответить[ответить]