псевдопростое число Лукаса

Псевдопростые числа Люка и псевдопростые числа Фибоначчи — это составные целые числа, которые проходят определенные тесты, которым проходят все простые числа и очень немногие составные числа: в данном случае критерии относительно некоторой последовательности Люка .

Бэйли и Вагстафф определяют псевдопростые числа Люка следующим образом: ^[1] Даны целые числа P и Q , где P > 0 и , пусть U _k ( P , Q ) и V _k ( P , Q ) — соответствующие последовательности Люка .${\displaystyle D=P^{2}-4Q}$

Пусть n — положительное целое число, а — символ Якоби . Определим${\displaystyle \left({\tfrac {D}{n}}\right)}$

${\displaystyle \delta (n)=n-\left({\tfrac {D}{n}}\right).}$

Если n — простое число , не делящее Q , то выполняется следующее условие конгруэнтности:

${\displaystyle U_{\delta (n)}\equiv 0{\pmod {n}}.}$

( 1 )

Если это соответствие не выполняется, то n не является простым числом. Если n является составным числом , то это соответствие обычно не выполняется. ^[1] Это ключевые факты, которые делают последовательности Люка полезными в тестировании простоты .

Сравнение ( 1 ) представляет собой одно из двух сравнений, определяющих псевдопростое число Фробениуса . Следовательно, каждое псевдопростое число Фробениуса также является псевдопростым числом Бейли-Вагстаффа-Лукаса, но обратное не всегда верно.

Хорошими ссылками являются глава 8 книги Брессо и Вагона (с кодом Mathematica ), ^[2] страницы 142–152 книги Крэндалла и Померанса, ^[3] и страницы 53–74 книги Рибенбойма. ^[4]

Вероятное простое число Люка для данной пары ( P, Q ) — это любое положительное целое число n , для которого уравнение ( 1 ) выше верно (см. ^[1] стр. 1398).

Псевдопростое число Люка для данной пары ( P, Q ) — это положительное составное целое число n , для которого уравнение ( 1 ) верно (см. ^[1] стр. 1391).

Тест Люка на вероятное простое число наиболее полезен, если D выбран таким образом, что символ Якоби равен −1 (см. страницы 1401–1409 из ^[1] , страницу 1024 из ^[5] или страницы 266–269 из ^[2] ). Это особенно важно при объединении теста Лукаса с сильным тестом на псевдопростое число, таким как тест на простоту Бейли–ПСВ . Обычно реализации будут использовать метод выбора параметров, который обеспечивает это условие (например, метод Селфриджа, рекомендованный в ^[1] и описанный ниже).${\displaystyle \left({\tfrac {D}{n}}\right)}$

Если тогда уравнение ( 1 ) становится${\displaystyle \left({\tfrac {D}{n}}\right)=-1,}$

${\displaystyle U_{n+1}\equiv 0{\pmod {n}}.}$

( 2 )

Если сравнение ( 2 ) ложно, это является доказательством того, что n является составным.

Если конгруэнтность ( 2 ) истинна, то n является вероятным простым числом Лукаса. В этом случае либо n является простым числом, либо оно является псевдопростым числом Лукаса. Если конгруэнтность ( 2 ) истинна, то n , скорее всего, будет простым числом (это оправдывает термин вероятный простой), но это не доказывает , что n является простым числом. Как и в случае с любым другим вероятностным тестом на простоту, если мы проводим дополнительные тесты Лукаса с различными D , P и Q , то, если только один из тестов не доказывает, что n является составным числом, мы получаем большую уверенность в том, что n является простым числом.

Примеры: Если P = 3, Q = −1 и D = 13, то последовательность U имеет вид OEIS : A006190 : U ₀ = 0, U ₁ = 1, U ₂ = 3, U ₃ = 10 и т. д.

Сначала пусть n = 19. Символ Якоби равен −1, поэтому δ( n ) = 20, U ₂₀ = 6616217487 = 19·348221973 и мы имеем${\displaystyle \left({\tfrac {13}{19}}\right)}$

${\displaystyle U_{20}=6616217487\equiv 0{\pmod {19}}.}$

Следовательно, 19 — вероятное простое число Люка для этой пары ( P, Q ). В этом случае 19 — простое число, поэтому оно не является псевдопростым числом Люка.

Для следующего примера пусть n = 119. У нас = −1, и мы можем вычислить${\displaystyle \left({\tfrac {13}{119}}\right)}$

${\displaystyle U_{120}\equiv 0{\pmod {119}}.}$

Однако 119 = 7·17 не является простым числом, поэтому 119 является псевдопростым числом Люка для этой пары ( P, Q ). Фактически, 119 является наименьшим псевдопростым числом для P = 3, Q = −1.

Ниже мы увидим, что для проверки уравнения ( 2 ) для заданного n нам не нужно вычислять все первые n + 1 членов в последовательности U.

Пусть Q = −1, наименьшее псевдопростое число Люка для P = 1, 2, 3, ... равно

323, 35, 119, 9, 9, 143, 25, 33, 9, 15, 123, 35, 9, 9, 15, 129, 51, 9, 33, 15, 21, 9, 9, 49, 15, 39, 9, 35, 49, 15, 9, 9, 33, 51, 15, 9, 35, 85, 39, 9, 9, 21, 25, 51, 9, 143, 33, 119, 9, 9, 51, 33, 95, 9, 15, 301, 25, 9, 9, 15, 49, 155, 9, 399, 15, 33, 9, 9, 49, 15, 119, 9, ...

Теперь преобразуем в форму, где — нечетное.${\displaystyle \delta (n)=n-\left({\tfrac {D}{n}}\right)}$${\displaystyle d\cdot 2^{s}}$${\displaystyle д}$

Сильное псевдопростое число Люка для данной пары ( P, Q ) — это нечетное составное число n с НОД( n, D ) = 1, удовлетворяющее одному из условий

${\displaystyle U_{d}\equiv 0{\pmod {n}}}$

или

${\displaystyle V_{d\cdot 2^{r}}\equiv 0{\pmod {n}}}$

для некоторого 0 ≤ r < s ; см. стр. 1396 ^[1] Сильное псевдопростое число Люка также является псевдопростым числом Люка (для той же пары ( P, Q )), но обратное не обязательно верно. Поэтому сильный тест является более строгим тестом на простоту, чем уравнение ( 1 ).

Существует бесконечно много сильных псевдопростых чисел Люка, и, следовательно, бесконечно много псевдопростых чисел Люка. Теорема 7 в ^[1] гласит: Пусть и — взаимно простые положительные целые числа, для которых положительно, но не является квадратом. Тогда существует положительная константа (зависящая от и ), такая, что число сильных псевдопростых чисел Люка, не превосходящих , больше , для достаточно больших.${\displaystyle P}$${\displaystyle Q}$${\displaystyle P^{2}-4Q}$${\displaystyle с}$${\displaystyle P}$${\displaystyle Q}$${\displaystyle x}$${\displaystyle c\cdot \log x}$${\displaystyle x}$

Мы можем положить Q = −1, тогда и являются последовательностями P -Фибоначчи и P -Лукаса, псевдопростые числа можно назвать сильными псевдопростыми числами Люка по основанию P , например, наименее сильными псевдопростыми числами Люка с P = 1, 2, 3, ... являются 4181, 169, 119, ...${\displaystyle U_{n}}$${\displaystyle V_{n}}$

Сверхсильное псевдопростое число Люка ^[6] — это сильное псевдопростое число Люка для набора параметров ( P , Q ), где Q = 1, удовлетворяющее одному из условий

${\displaystyle U_{d}\equiv 0{\pmod {n}}{\text{ и }}V_{d}\equiv \pm 2{\pmod {n}}}$

или

${\displaystyle V_{d\cdot 2^{r}}\equiv 0{\pmod {n}}}$

для некоторых . Сверхсильное псевдопростое число Люка также является сильным псевдопростым числом Люка для той же пары.${\displaystyle 0\leq r<s-1}$${\displaystyle (P,Q)}$

Прежде чем приступить к вероятному тесту на простоту, обычно проверяют, что n , число, которое нужно проверить на простоту, является нечетным, не является полным квадратом и не делится ни на какое малое простое число, меньшее некоторого удобного предела. Полные квадраты легко обнаружить с помощью метода Ньютона для квадратных корней.

Выбираем последовательность Люка, в которой символ Якоби равен , так что δ( n ) = n + 1.${\displaystyle \left({\tfrac {D}{n}}\right)=-1}$

При наличии n один из методов выбора D заключается в использовании метода проб и ошибок для нахождения первого D в последовательности 5, −7, 9, −11, ... такого, что . Обратите внимание, что . (Если D и n имеют общий простой множитель, то ). При такой последовательности значений D среднее количество значений D , которые необходимо перебрать, прежде чем мы встретим то, символ Якоби которого равен −1, составляет около 1,79; см. ^[1] с. 1416. Как только у нас есть D , мы устанавливаем и . Хорошей идеей будет проверить, что n не имеет общих простых множителей с P или Q . Этот метод выбора D , P и Q был предложен Джоном Селфриджем .${\displaystyle \left({\tfrac {D}{n}}\right)=-1}$${\displaystyle \left({\tfrac {k}{n}}\right)\left({\tfrac {-k}{n}}\right)=-1}$${\displaystyle \left({\tfrac {D}{n}}\right)=0}$${\displaystyle P=1}$${\displaystyle Q=(1-D)/4}$

(Этот поиск никогда не будет успешным, если n является квадратным, и наоборот, если он будет успешным, это будет доказательством того, что n не является квадратным. Таким образом, можно сэкономить некоторое время, отложив проверку n на квадратность до тех пор, пока все первые несколько шагов поиска не потерпят неудачу.)

При наличии D , P и Q существуют рекуррентные соотношения, которые позволяют нам быстро вычислять и по шагам; см. последовательность Люка § Другие соотношения . Для начала, ${\displaystyle U_{n+1}}$${\displaystyle V_{n+1}}$${\displaystyle O(\log _{2}n)}$

${\displaystyle U_{1}=1}$

${\displaystyle V_{1}=P=1}$

Во-первых, мы можем удвоить нижний индекс от до за один шаг, используя рекуррентные соотношения${\displaystyle k}$${\displaystyle 2k}$

${\displaystyle U_{2k}=U_{k}\cdot V_{k}}$

${\displaystyle V_{2k}=V_{k}^{2}-2Q^{k}={\frac {V_{k}^{2}+DU_{k}^{2}}{2}}}$.

Далее мы можем увеличить нижний индекс на 1, используя рекуррентные соотношения

${\displaystyle U_{2k+1}=(P\cdot U_{2k}+V_{2k})/2}$

${\displaystyle V_{2k+1}=(D\cdot U_{2k}+P\cdot V_{2k})/2}$.

Если нечетно, замените его на ; это четно, поэтому теперь его можно разделить на 2. Числитель обрабатывается таким же образом. (Добавление n не меняет результат по модулю n .) Обратите внимание, что для каждого члена, который мы вычисляем в последовательности U , мы вычисляем соответствующий член в последовательности V . По мере продвижения мы также вычисляем те же самые соответствующие степени Q .${\displaystyle P\cdot U_{2k}+V_{2k}}$${\displaystyle P\cdot U_{2k}+V_{2k}+n}$${\displaystyle V_{2k+1}}$

На каждом этапе мы уменьшаем , , и степень , mod n .${\displaystyle U}$${\displaystyle V}$${\displaystyle Q}$

Мы используем биты двоичного разложения n, чтобы определить, какие члены в последовательности U следует вычислить. Например, если n +1 = 44 (= 101100 в двоичной системе), то, беря биты по одному слева направо, мы получаем последовательность индексов для вычисления: 1 ₂ = 1, 10 ₂ = 2, 100 ₂ = 4, 101 ₂ = 5, 1010 ₂ = 10, 1011 ₂ = 11, 10110 ₂ = 22, 101100 ₂ = 44. Таким образом, мы вычисляем U ₁ , U ₂ , U ₄ , U ₅ , U ₁₀ , U ₁₁ , U ₂₂ и U ₄₄ . Мы также вычисляем члены с теми же номерами в последовательности V , а также Q ¹ , Q ² , Q ⁴ , Q ⁵ , Q ¹⁰ , Q ¹¹ , Q ²² и Q ⁴⁴ .

К концу расчета мы вычислим U _n+1 , V _n+1 и Q ⁿ⁺¹ , (mod n ). Затем мы проверяем соответствие ( 2 ) с использованием известного нам значения U _n+1 .

Когда D , P и Q выбраны так, как описано выше, первые 10 псевдопростых чисел Лукаса равны (см. стр. 1401 ^[1] ): 323, 377, 1159, 1829, 3827, 5459, 5777, 9071, 9179 и 10877 (последовательность A217120 в OEIS ).

Сильные версии теста Лукаса могут быть реализованы аналогичным образом .

Когда D , P и Q выбраны так, как описано выше, первые 10 сильных псевдопростых чисел Лукаса равны: 5459, 5777, 10877, 16109, 18971, 22499, 24569, 25199, 40309 и 58519 (последовательность A217255 в OEIS ).

Чтобы вычислить список особо сильных псевдопростых чисел Люка, установите . Затем попробуйте P = 3, 4, 5, 6, ..., пока не будет найдено значение , такое, что символ Якоби . При таком методе выбора D , P , и Q , первые 10 особо сильных псевдопростых чисел Люка равны 989, 3239, 5777, 10877, 27971, 29681, 30739, 31631, 39059 и 72389 (последовательность A217719 в OEIS )${\displaystyle Q=1}$${\displaystyle D=P^{2}-4Q}$${\displaystyle \left({\tfrac {D}{n}}\right)=-1}$

Если мы проверили, что конгруэнтность ( 2 ) истинна, есть дополнительные условия конгруэнтности, которые мы можем проверить, и которые не требуют почти никаких дополнительных вычислительных затрат. Если n оказывается составным, эти дополнительные условия могут помочь обнаружить этот факт.

Если n — нечетное простое число и , то имеем следующее (см. уравнение 2 на стр. 1392 ^[1] ):${\displaystyle \left({\tfrac {D}{n}}\right)=-1}$

${\displaystyle V_{n+1}\equiv 2Q{\pmod {n}}.}$

( 3 )

Хотя это условие конгруэнтности по определению не является частью теста Лукаса на вероятное простое число, проверить это условие можно практически бесплатно, поскольку, как отмечено выше, значение V _n+1 было вычислено в процессе вычисления U _n+1 .

Если либо сравнение ( 2 ), либо сравнение ( 3 ) ложно, это составляет доказательство того, что n не является простым числом. Если оба сравнения истинны, то вероятность того, что n является простым числом, еще выше, чем если бы мы проверили только сравнение ( 2 ).

Если метод Селфриджа (выше) для выбора D , P , и Q случайно установил Q = −1, то мы можем настроить P и Q так, чтобы D и оставались неизменными и P = Q = 5 (см. последовательность Лукаса - алгебраические соотношения ). Если мы используем этот улучшенный метод для выбора P и Q , то 913 = 11·83 является единственным составным числом, меньшим 10 ⁸ , для которого справедливо сравнение ( 3 ) (см. страницу 1409 и таблицу 6 из ^[1] ). Более обширные вычисления показывают, что при этом методе выбора D , P , и Q существует только пять нечетных составных чисел, меньших 10 ^{15 ,} для которых справедливо сравнение ( 3 ). ^[7]${\displaystyle \left({\tfrac {D}{n}}\right)}$

Если , то можно реализовать дополнительное условие конгруэнтности, требующее очень небольшого количества дополнительных вычислений.${\displaystyle Q\neq \pm 1}$

Напомним, что вычисляется во время вычисления , и мы можем легко сохранить ранее вычисленную степень , а именно, .${\displaystyle Q^{n+1}}$${\displaystyle U_{n+1}}$${\displaystyle Q}$${\displaystyle Q^{(n+1)/2}}$

Если n — простое число, то по критерию Эйлера

${\displaystyle Q^{(n-1)/2}\equiv \left({\tfrac {Q}{n}}\right){\pmod {n}}}$.

(Здесь — символ Лежандра ; если n — простое число, то это то же самое, что и символ Якоби).${\displaystyle \left({\tfrac {Q}{n}}\right)}$

Следовательно, если n — простое число, то мы должны иметь,

${\displaystyle Q^{(n+1)/2}\equiv Q\cdot Q^{(n-1)/2}\equiv Q\cdot \left({\tfrac {Q}{n}}\right){\pmod {n}}.}$

( 4 )

Символ Якоби справа легко вычислить, поэтому это соответствие легко проверить. Если это соответствие не выполняется, то n не может быть простым числом. При условии, что GCD( n, Q ) = 1, то проверка на соответствие ( 4 ) эквивалентна дополнению нашего теста Лукаса тестом простоты Соловея–Штрассена «базой Q» .

Дополнительные условия конгруэнтности, которые должны быть выполнены, если n — простое число, описаны в разделе 6 ^[1] . Если какое-либо из этих условий не выполняется, то мы доказали, что n — не простое число.

k применений теста простоты Миллера–Рабина объявляют составное число n , вероятно, простым с вероятностью не более (1/4) ^k .

Аналогичная оценка вероятности существует для сильного теста Лукаса на вероятное простое число. ^[8]

За исключением двух тривиальных исключений (см. ниже), доля пар ( P , Q ) (по модулю n ), которые объявляют составное число n вероятно простым, составляет не более (4/15).

Таким образом, k применений сильного теста Лукаса объявят составное число n , вероятно, простым с вероятностью не более (4/15) ^k .

Есть два тривиальных исключения. Одно из них — n = 9. Другое — когда n = p ( p +2) — произведение двух простых чисел-близнецов . Такое n легко разложить на множители, потому что в этом случае n +1 = ( p +1) ² — полный квадрат. Можно быстро обнаружить полные квадраты, используя метод Ньютона для квадратных корней.

Объединив тест на псевдопростоту Люка с тестом Ферма на простоту , скажем, по основанию 2, можно получить очень мощные вероятностные тесты на простоту, такие как тест на простоту Бейли–ПСВ .

Когда P = 1 и Q = −1, последовательность U _n ( P , Q ) представляет собой числа Фибоначчи.

Псевдопростое число Фибоначчи часто ^{[2] : 264,   [3] : 142,   [4] : 127} определяется как составное число n, не делящееся на 5, для которого выполняется сравнение ( 1 ) с P = 1 и Q = −1. Согласно этому определению, псевдопростые числа Фибоначчи образуют последовательность:

323, 377, 1891, 3827, 4181, 5777, 6601, 6721, 8149, 10877, ... (последовательность A081264 в OEIS ).

В приведенных ниже ссылках Андерсона и Якобсена используется это определение.

Если n сравнимо с 2 или 3 по модулю 5, то Брессо ^{[2] : 272–273} и Крэндалл и Померанс ^{[3] : 143, 168} указывают, что редкость, когда псевдопростое число Фибоначчи также является псевдопростым числом Ферма по основанию 2. Однако, когда n сравнимо с 1 или 4 по модулю 5, верно обратное: более 12% псевдопростых чисел Фибоначчи до 10 ¹¹ также являются псевдопростыми числами Ферма по основанию 2.

Если n — простое число и НОД( n , Q ) = 1, то мы также имеем ^{[1] : 1392}

${\displaystyle V_{n}(P,Q)\equiv P{\pmod {n}}.}$

( 5 )

Это приводит к альтернативному определению псевдопростого числа Фибоначчи: ^{[9] [10]}

Псевдопростое число Фибоначчи — это составное число n, для которого выполняется сравнение ( 5 ) при P = 1 и Q = −1.

Это определение приводит к тому, что псевдопростые числа Фибоначчи образуют последовательность:

705, 2465, 2737, 3745, 4181, 5777, 6721, 10877, 13201, 15251, ... (последовательность A005845 в OEIS ),

которые также называются псевдопростыми числами Брукмана-Лукаса . ^{[4] : 129} Хоггатт и Бикнелл изучали свойства этих псевдопростых чисел в 1974 году. ^[11] Сингмастер вычислил эти псевдопростые числа до 100000. ^[12] Якобсен перечисляет все 111443 этих псевдопростых чисел, меньших 10 ¹³ . ^[13]

Было показано, что не существует четных псевдопростых чисел Фибоначчи, определяемых уравнением (5). ^{[14] [15]} Однако существуют четные псевдопростые числа Фибоначчи (последовательность A141137 в OEIS ) в соответствии с первым определением, данным уравнением ( 1 ).

Сильное псевдопростое число Фибоначчи — это составное число n , для которого сравнение ( 5 ) выполняется при Q = −1 и всех P. ^[16] Из этого следует ^{[16] : 460} , что нечетное составное целое число n является сильным псевдопростым числом Фибоначчи тогда и только тогда, когда:

1. n — число Кармайкла
2. 2( p + 1) | ( n − 1) или 2( p + 1) | ( n − p ) для каждого простого числа p, делящего n .

Наименьшим примером сильного псевдопростого числа Фибоначчи является 443372888629441 = 17·31·41·43·89·97·167·331.

Псевдопростое число Пелла может быть определено как составное число n, для которого уравнение ( 1 ) выше верно с P = 2 и Q = −1; последовательность U _n тогда является последовательностью Пелла . Первые псевдопростые числа тогда 35, 169, 385, 779, 899, 961, 1121, 1189, 2419, ...

Это отличается от определения в OEIS : A099011, которое можно записать так:

${\displaystyle {\text{ }}U_{n}\equiv \left({\tfrac {2}{n}}\right){\pmod {n}}}$

с ( P , Q ) = (2, −1) снова определяя U _n как последовательность Пелля . Первые псевдопростые числа тогда 169, 385, 741, 961, 1121, 2001, 3827, 4879, 5719, 6215 ...

Третье определение использует уравнение (5) с ( P , Q ) = (2, −1), что приводит к псевдопростым числам 169, 385, 961, 1105, 1121, 3827, 4901, 6265, 6441, 6601, 7107, 7801, 8119, ...

• Андерсон, Питер Г. Псевдопростые числа Фибоначчи, их множители и точки входа.
• Андерсон, Питер Г. Псевдопростые числа Фибоначчи до 2 217 967 487 и их множители.
• Якобсен, Дана Статистика псевдопростых чисел, таблицы и данные (данные для псевдопростых чисел Лукаса, Стронга Лукаса, AES Лукаса, ES Лукаса ниже 10 ¹⁴ ; псевдопростых чисел Фибоначчи и Пелля ниже 10 ¹² )
• Вайсштейн, Эрик В. «Псевдопростые числа Фибоначчи». Математический мир .
• Вайсштейн, Эрик В. «Лукас Псевдопрайм». Математический мир .
• Вайсштейн, Эрик В. «Сильный Лукас Псевдопрайм». Математический мир .
• Вайсштейн, Эрик В. «Очень сильный Лукас Псевдопрайм». Математический мир .