Лукас псевдопростой

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

Псевдопростые числа Бэйли-Вагстаффа-Лукаса

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

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

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

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

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

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

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

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

Вероятные простые и псевдопростые

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

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

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

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

$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 's равна OEIS : A006190 : U ₀ = 0, U ₁ = 1, U ₂ = 3, U ₃ = 10 и т. д.

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

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

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

В следующем примере пусть n = 119. Имеем $\left({\tfrac {13}{119}}\right)$ = −1, и мы можем вычислить

$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, ...

Сильные

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

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

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

или

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

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

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

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

Очень сильное псевдопростое число Лукаса. является сильным псевдопростым числом Люка для набора параметров ( P , Q ), где Q = 1, удовлетворяющего одному из условий

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

или

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

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

простого теста

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

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

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

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

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

$U_{1}=1$

$V_{1}=P=1$

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

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

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

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

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

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

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

На каждом этапе мы уменьшаем $U$, $V$, и сила $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 ⁴⁴ .

К концу расчета мы вычислим Un ₊₁ , Vn ₊₁ и Q ^п+1 , (мод . n ).Затем мы проверяем сравнение ( 2 ), используя известное значение Un ₊₁ .

Когда D , P и Q выбраны, как описано выше, первые 10 псевдопростых чисел Люка (см. стр. 1401 книги ):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 )

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

Проверка дополнительных условий соответствия

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

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

$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 и Q $\left({\tfrac {D}{n}}\right)$ остаются неизменными и P = Q = 5 (см. последовательности Люка — алгебраические отношения ).Если мы воспользуемся этим расширенным методом выбора P и Q , то 913 = 11·83 будет единственным составным числом меньше 10. ⁸ сравнение ( 3 ) (см. стр. 1409 и таблицу 6; для которого верно ). Более обширные расчеты показывают, что при таком методе выбора D , P и Q существует только пять нечетных составных чисел меньше 10. ¹⁵ для которого сравнение ( 3 ). справедливо

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

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

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

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

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

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

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

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

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

Миллера-Рабина

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

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

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

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

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

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

Псевдопростые числа Фибоначчи

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

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

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

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

Если n конгруэнтно 2 или 3 по модулю 5, то Брессу, и Крэндалл и Померанс отметим, что псевдопростые числа Фибоначчи редко одновременно являются псевдопростыми числами Фибоначчи по основанию 2. Однако, когда n конгруэнтно 1 или 4 по модулю 5, верно обратное: более 12% псевдопростых чисел Фибоначчи меньше 10. ¹¹ также являются псевдопростыми числами Ферма по основанию 2.

Если n простое число и НОД( n , Q ) = 1, то мы также имеем

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

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

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

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

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

которые также называют псевдопростыми числами Брукмана-Люкаса . Хоггатт и Бикнелл изучили свойства этих псевдопростых чисел в 1974 году. Сингмастер вычислил эти псевдопростые числа до 100 000. Якобсен перечисляет все 111443 таких псевдопростых чисел меньше 10. ¹³ .

Было показано, что не существует четных псевдопростых чисел Фибоначчи, определенных уравнением (5). Однако даже псевдопростые числа Фибоначчи существуют (последовательность A141137 в OEIS ) согласно первому определению, данному ( 1 ).

Сильное псевдопростое число Фибоначчи — это составное число n для которого выполняется сравнение ( 5 ) для Q = −1 и всех P. , Отсюда следует что нечетное составное целое число n является сильным псевдопростым числом Фибоначчи тогда и только тогда, когда:

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

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

Псевдопростые числа Пелла

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

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

${\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 Lucas, ES Lucas ниже 10 ¹⁴ ; Псевдопростые числа Фибоначчи и Пелла ниже 10 ¹² )
• Вайсштейн, Эрик В. «Псевдопростые числа Фибоначчи» . Математический мир .
• Вайсштейн, Эрик В. «Лукас Псевдопрайм» . Математический мир .
• Вайсштейн, Эрик В. «Сильный Лукас Псевдопрайм» . Математический мир .
• Вайсштейн, Эрик В. «Сверхсильный Лукас Псевдопрайм» . Математический мир .