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

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

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

Бэйли и Вагстафф определяют псевдопростые числа Люка следующим образом: ^[1] Даны целые числа 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] Это ключевые факты, которые делают последовательности Люка полезными при тестировании на простоту .

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

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

Вероятные простые и псевдопростые числа по Лукасу

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

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

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

Если $\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 оф. ^[1] Сильное псевдопростое число Люка также является псевдопростым числом Люка (для той же пары ( P, Q )), но обратное не обязательно верно.Следовательно, сильный тест является более строгим тестом на простоту, чем уравнение ( 1 ).

Существует бесконечно много сильных псевдопростых чисел Люкаса и, следовательно, бесконечно много псевдопростых чисел Люка.Теорема 7 в ^[1] утверждает: Пусть $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, ...

Очень сильное псевдопростое число Лукаса. ^[6]является сильным псевдопростым числом Люка для набора параметров ( 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; видеть, ^[1] п. 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 ₊₁ , V _n+1 и Q ^п+1, (мод . n ).Затем мы проверяем сравнение ( 2 ), используя известное значение Un ₊₁ .

Когда 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 )

Чтобы вычислить список сверхсильных псевдопростых чисел Люка, установите $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 книги ^[1]):

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; для которого верно ^[1]). Более обширные расчеты показывают, что при таком методе выбора D , P и Q существует только пять нечетных составных чисел меньше 10. ¹⁵ для которого сравнение ( 3 ). справедливо ^[7]

Если $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. ^[1] Если какое-либо из этих условий не выполнено, то мы доказали, что n не является простым.

Сравнение с критерием простоты Миллера – Рабина.

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

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

За исключением двух тривиальных исключений (см. ниже), доля ( 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 ) представляет числа Фибоначчи.

Псевдопростое число Фибоначчи часто бывает ^[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

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] Сингмастер вычислил эти псевдопростые числа до 100 000. ^[12] Якобсен перечисляет все 111443 таких псевдопростых чисел меньше 10. ¹³. ^[13]

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

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

n — число Кармайкла
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, ...

Ссылки

^ Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н Роберт Бэйли; Сэмюэл С. Вагстафф-младший (октябрь 1980 г.). «Лукас Псевдопраймс» (PDF) . Математика вычислений . 35 (152): 1391–1417. дои : 10.1090/S0025-5718-1980-0583518-6 . JSTOR 2006406 . МР 0583518 .
^ Jump up to: Перейти обратно: ^а ^б ^с ^д Дэвид Брессу ; Стэн Вагон (2000). Курс вычислительной теории чисел . Нью-Йорк: Key College Publishing в сотрудничестве со Springer. ISBN 978-1-930190-10-8 .
^ Jump up to: Перейти обратно: ^а ^б ^с Ричард Э. Крэндалл ; Карл Померанс (2005). Простые числа: вычислительная перспектива (2-е изд.). Спрингер-Верлаг . ISBN 0-387-25282-7 .
^ Jump up to: Перейти обратно: ^а ^б ^с Пауло Рибенбойм (1996). Новая книга рекордов простых чисел . Спрингер-Верлаг . ISBN 0-387-94457-5 .
^ Карл Померанс ; Джон Л. Селфридж ; Сэмюэл С. Вагстафф-младший (июль 1980 г.). «Псевдопростые числа до 25·10 ⁹» (PDF) . Математика вычислений . 35 (151): 1003–1026. doi : 10.1090/S0025-5718-1980-0572872-7 . JSTOR 2006210 .
^ Джон Грэнтэм (2001). «Псевдопростые числа Фробениуса» . Математика вычислений . 70 (234): 873–891. arXiv : 1903.06820 . Бибкод : 2001MaCom..70..873G . дои : 10.1090/S0025-5718-00-01197-2 . МР 1680879 .
^ Роберт Бэйли; Эндрю Фиори; Сэмюэл С. Вагстафф-младший (июль 2021 г.). «Усиление теста на первичность Бэйли-PSW». Математика вычислений . 90 (330): 1931–1955. arXiv : 2006.14425 . дои : 10.1090/mcom/3616 . S2CID 220055722 .
^ Ф. Арно (апрель 1997 г.). «Теорема Рабина-Монье для псевдопростых чисел Люка». Математика вычислений . 66 (218): 869–881. CiteSeerX 10.1.1.192.4789 . дои : 10.1090/s0025-5718-97-00836-3 .
^ Адина Ди Порто; Пьеро Филиппони (1989). «Подробнее о псевдопростых числах Фибоначчи» (PDF) . Ежеквартальный журнал Фибоначчи . 27 (3): 232–242.
^ Ди Порту, Адина; Филиппони, Пьеро; Монтоливо, Эмилио (1990). «Об обобщенных псевдопростых числах Фибоначчи». Ежеквартальный журнал Фибоначчи . 28 : 347–354. CiteSeerX 10.1.1.388.4993 .
^ В. Е. Хоггатт-младший ; Марджори Бикнелл (сентябрь 1974 г.). «Некоторые сравнения чисел Фибоначчи по модулю простого числа p». Журнал «Математика» . 47 (4): 210–214. дои : 10.2307/2689212 . JSTOR 2689212 .
^ Дэвид Сингмастер (1983). «Некоторые псевдопростые числа Лукаса». Рефераты амер. Математика. Соц . 4 (83Т–10–146): 197.
^ «Псевдопростые статистики и таблицы» . Проверено 5 мая 2019 г.
^ П. С. Брукман (1994). «Псевдопростые числа Лукаса странные». Ежеквартальный журнал Фибоначчи . 32 : 155–157.
^ Ди Порту, Адина (1993). «Несуществование даже псевдопростых чисел Фибоначчи первого рода». Ежеквартальный журнал Фибоначчи . 31 : 173–177. CiteSeerX 10.1.1.376.2601 .
^ Jump up to: Перейти обратно: ^а ^б Мюллер, Винфрид Б.; Освальд, Алан (1993). «Обобщенные псевдопростые числа Фибоначчи и вероятные простые числа». В GE Bergum; и др. (ред.). Применение чисел Фибоначчи . Том. 5. Клювер. стр. 459–464. дои : 10.1007/978-94-011-2058-6_45 .

Внешние ссылки

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

[lpsp-1] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н Роберт Бэйли; Сэмюэл С. Вагстафф-младший (октябрь 1980 г.). «Лукас Псевдопраймс» (PDF) . Математика вычислений . 35 (152): 1391–1417. дои : 10.1090/S0025-5718-1980-0583518-6 . JSTOR 2006406 . МР 0583518 .

[Bressoud-2] Jump up to: Перейти обратно: ^а ^б ^с ^д Дэвид Брессу ; Стэн Вагон (2000). Курс вычислительной теории чисел . Нью-Йорк: Key College Publishing в сотрудничестве со Springer. ISBN 978-1-930190-10-8 .

[CrandallPomerance-3] Jump up to: Перейти обратно: ^а ^б ^с Ричард Э. Крэндалл ; Карл Померанс (2005). Простые числа: вычислительная перспектива (2-е изд.). Спрингер-Верлаг . ISBN 0-387-25282-7 .

[Ribenboim-4] Jump up to: Перейти обратно: ^а ^б ^с Пауло Рибенбойм (1996). Новая книга рекордов простых чисел . Спрингер-Верлаг . ISBN 0-387-94457-5 .

[PSW-5] Карл Померанс ; Джон Л. Селфридж ; Сэмюэл С. Вагстафф-младший (июль 1980 г.). «Псевдопростые числа до 25·10 ⁹» (PDF) . Математика вычислений . 35 (151): 1003–1026. doi : 10.1090/S0025-5718-1980-0572872-7 . JSTOR 2006210 .

[FrobeniusPSP-6] Джон Грэнтэм (2001). «Псевдопростые числа Фробениуса» . Математика вычислений . 70 (234): 873–891. arXiv : 1903.06820 . Бибкод : 2001MaCom..70..873G . дои : 10.1090/S0025-5718-00-01197-2 . МР 1680879 .

[bpsw2-7] Роберт Бэйли; Эндрю Фиори; Сэмюэл С. Вагстафф-младший (июль 2021 г.). «Усиление теста на первичность Бэйли-PSW». Математика вычислений . 90 (330): 1931–1955. arXiv : 2006.14425 . дои : 10.1090/mcom/3616 . S2CID 220055722 .

[8] Ф. Арно (апрель 1997 г.). «Теорема Рабина-Монье для псевдопростых чисел Люка». Математика вычислений . 66 (218): 869–881. CiteSeerX 10.1.1.192.4789 . дои : 10.1090/s0025-5718-97-00836-3 .

[FibonacciPSP-9] Адина Ди Порто; Пьеро Филиппони (1989). «Подробнее о псевдопростых числах Фибоначчи» (PDF) . Ежеквартальный журнал Фибоначчи . 27 (3): 232–242.

[10] Ди Порту, Адина; Филиппони, Пьеро; Монтоливо, Эмилио (1990). «Об обобщенных псевдопростых числах Фибоначчи». Ежеквартальный журнал Фибоначчи . 28 : 347–354. CiteSeerX 10.1.1.388.4993 .

[11] В. Е. Хоггатт-младший ; Марджори Бикнелл (сентябрь 1974 г.). «Некоторые сравнения чисел Фибоначчи по модулю простого числа p». Журнал «Математика» . 47 (4): 210–214. дои : 10.2307/2689212 . JSTOR 2689212 .

[12] Дэвид Сингмастер (1983). «Некоторые псевдопростые числа Лукаса». Рефераты амер. Математика. Соц . 4 (83Т–10–146): 197.

[13] «Псевдопростые статистики и таблицы» . Проверено 5 мая 2019 г.

[Bruckman-14] П. С. Брукман (1994). «Псевдопростые числа Лукаса странные». Ежеквартальный журнал Фибоначчи . 32 : 155–157.

[15] Ди Порту, Адина (1993). «Несуществование даже псевдопростых чисел Фибоначчи первого рода». Ежеквартальный журнал Фибоначчи . 31 : 173–177. CiteSeerX 10.1.1.376.2601 .

[Muller-16] Jump up to: Перейти обратно: ^а ^б Мюллер, Винфрид Б.; Освальд, Алан (1993). «Обобщенные псевдопростые числа Фибоначчи и вероятные простые числа». В GE Bergum; и др. (ред.). Применение чисел Фибоначчи . Том. 5. Клювер. стр. 459–464. дои : 10.1007/978-94-011-2058-6_45 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]