Лукас псевдопрайм - Lucas pseudoprime

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

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

Бэйли и Вагстафф определяют псевдопростые числа Лукаса следующим образом: даны целые числа 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).}$

Если п является простое такое , что наибольший общий делитель из п и Q (то есть, НОД ( N, Q )) равен 1, то выполняется следующее условие конгрузнцтеорему:

${\ Displaystyle U _ {\ delta (n)} \ Equiv 0 {\ pmod {n}}.}$

( 1 )

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

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

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

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

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

Псевдопростое число люка для заданного ( Р, Q пары) является положительным композитом целого числа п , для которых уравнения ( 1 ) является истинным (см, стр) один тысяча триста девяносто один.

Вероятный простой критерий Люка наиболее полезен, если D выбрано таким образом, что символ Якоби равен -1 (см. Страницы 1401–1409, стр. 1024 или страницы 266–269). Это особенно важно при сочетании теста Лукаса с сильным тестом на псевдоперминал , таким как тест на простоту Бейли – PSW . Обычно реализации будут использовать метод выбора параметра, который обеспечивает это условие (например, метод Selfridge, рекомендованный и описанный ниже). ${\ 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 \ дельта (п) = п- \ влево ({\ tfrac {D} {п}} \ вправо)}$${\ displaystyle d \ cdot 2 ^ {s}}$${\ displaystyle d}$

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

${\ Displaystyle U_ {d} \ эквив 0 {\ pmod {п}}}$

или же

${\ Displaystyle V_ {д \ CDOT 2 ^ {г}} \ эквив 0 {\ pmod {п}}}$

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

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

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

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

или же

${\ Displaystyle V_ {д \ CDOT 2 ^ {г}} \ эквив 0 {\ pmod {п}}}$

для некоторых . Сверхсильное псевдопростое число Лукаса также является сильным псевдопричинением Лукаса для той же пары. ${\ Displaystyle 0 \ Leq г <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; см. стр. 1416. Когда у нас есть D , мы устанавливаем и . Это хорошая идея , чтобы проверить , что п не имеет простых множителей общего с 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 О (\ журнал _ {2} п)}$

${\ 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 ^{n + 1} , (mod n ). Затем мы проверяем сравнение ( 2 ), используя известное нам значение U _{n + 1} .

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

Чтобы вычислить список сверхсильных псевдопримеров Лукаса, установите . Затем попробуйте 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 из): ${\ 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 ^8, для которой верно сравнение ( 3 ) (см. Стр. 1409 и Таблицу 6;). Более подробные вычисления показывают, что при таком методе выбора D , P и Q есть только пять нечетных составных чисел меньше 10 ^15, для которых верно сравнение ( 3 ). ${\ displaystyle \ left ({\ tfrac {D} {n}} \ right)}$

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

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

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

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

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

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

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

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

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

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

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

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

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

Псевдопростое число Фибоначчи часто определяется как составное число п не делится на 5 , для которых сравнение ( 1 ) имеет место с Р = 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, то также имеем

${\ Displaystyle V_ {n} (P, Q) \ Equiv P {\ pmod {n}}.}$

( 5 )

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

Фибоначчи псевдопростое число является составным числом п , для которых сравнение ( 5 ) выполняется с Р = 1 и Q = -1.

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

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

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

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

Сильные Фибоначчи псевдопростого число является составным числом п , для которых сравнение ( 5 ) имеет место при Q = -1 и все Р . Отсюда следует, что нечетное составное целое число 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.

Pell pseudoprimes

Пелл псевдопростое число может быть определенно как составное число п , для которых уравнения ( 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 и их факторы.
• Jacobsen, Dana Pseudoprime Statistics, Tables, and Data (данные для псевдопростых чисел Лукаса, Стронга Лукаса, AES Lucas, ES Lucas ниже 10 ¹⁴ ; псевдопростых чисел Фибоначчи и Пелла ниже 10 ¹² )
• Вайсштейн, Эрик В. «Псевдопросто Фибоначчи» . MathWorld .
• Вайсштейн, Эрик В. «Лукас Псевдопрайм» . MathWorld .
• Вайсштейн, Эрик У. "Сильное псевдопрайм Лукаса" . MathWorld .
• Вайсштейн, Эрик В. "Сверхсильный псевдопрайм Лукаса" . MathWorld .