Математика · объяснение и практика

Почему успешная проверка по Ферма ещё не доказывает простоту

Почему прохождение сравнения Ферма не является доказательством простоты, как проверить составной контрпример и отличить свидетельство составности от неудачи найти его.

Синяя и оранжевая половины складываются в целый круг.

В теме Теория чисел: углубление · Учебная карта

В маршруте Новые структуры целой арифметики · 10 тем

Главная мысль

Простое n, взаимно простое с основанием a, обязано удовлетворять a^(n−1)≡1. Нарушение доказывает составность, но выполнение допускает составные числа — псевдопростые по выбранному основанию.

Теорема работает только в заявленную сторону

Малая теорема Ферма даёт необходимое свойство простого модуля. Если при взаимно простом основании получили иной остаток, предположение о простоте невозможно. Но из наличия необходимого свойства простота сама по себе не следует. Это тот же логический разрыв, который встречается между признаком в одну сторону и равносильным критерием.

Составное число, прошедшее выбранное сравнение, называют псевдопростым Ферма по этому основанию. Уточнение основания существенно: одно число может пройти одну проверку и провалить другую. До возведения в степень полезно вычислить общий делитель основания и числа. Нетривиальный общий делитель уже непосредственно доказывает составность без степенного теста.

Пройти проверку и всё равно быть составным

Число 341 равно 11·31. При этом 2¹⁰=1024=3·341+1, так что 2¹⁰≡1 по модулю 341. Показатель 340 кратен десяти, поэтому 2³⁴⁰≡1. Получен явный составной объект, удовлетворяющий сравнению Ферма с основанием два. Никакой неопределённости вычислений здесь нет: ошибка была бы только в слишком сильном выводе.

Расчёт удобно вести через короткое сравнение и его степени, не выписывая огромную десятичную запись. Отдельное разложение на множители подтверждает составность. Если бы разложения не было известно, успешная проверка всё равно оставалась бы лишь отсутствием обнаруженного нарушения, а не разрешением назвать результат простым.

Пример

Почему 91 проходит проверку Ферма по основанию три и остаётся составным?

Число 91=7·13, а 3⁶=729=8·91+1. Поскольку 90 кратно шести, 3⁹⁰≡1 по модулю 91. Основание три взаимно просто с 91, так что это настоящий составной контрпример, а не нарушение области теста.

Несколько оснований и честная формулировка результата

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

В учебной задаче полезно точно подписывать результат: «обнаружено свидетельство составности» или «данная проверка пройдена». Нельзя менять вторую фразу на «простота доказана». Критерий Вильсона имеет иную логическую силу, хотя его непосредственное вычисление может быть значительно тяжелее. Быстрота и достаточность — отдельные свойства метода.

От чтения к действию

А теперь — вы

Известно gcd(2,21)=1 и 2²⁰ даёт остаток 4 по модулю 21. Какой вывод оправдан?

Частые вопросы

Можно ли назвать псевдопростым настоящее простое число?

Нет. В определение псевдопростого входит составность; простое лишь удовлетворяет тому же сравнению по теореме.

Что делать, если общий делитель a и n больше единицы?

Если он меньше n, уже найден собственный делитель и составность доказана. Сравнение Ферма в копраймной форме применять не требуется.

Углублённый разбор

Сильный свидетель составности в тесте Миллера — Рабина

Тест Ферма может пропустить составное число, потому что проверяет только последнюю степень. Миллер — Рабин рассматривает цепочку квадратов до неё. Нетривиальный квадратный корень единицы или отсутствие обязательного минус одного создаёт короткое проверяемое свидетельство составности.

Перед началом: Малая теорема Ферма; Быстрое возведение в степень.

Для простого модуля цепочка имеет обязательную форму

Пусть нечётное n>2 записано как n−1=2ˢd с нечётным d. Выберем 1<a<n−1. Для простого n и ненулевого a обязательно aᵈ≡1 либо одно из a^(2ʲd)≡−1 при 0≤j<s. Это следует из разложения a^(n−1)−1 на множители aᵈ−1 и a^(2ʲd)+1: в поле нулевое произведение требует нулевого множителя.

Алгоритм сначала вычисляет aᵈ, затем последовательно возводит в квадрат. Начальная единица разрешает основание. Минус единица на одном из разрешённых уровней тоже разрешает его. Если ни одного такого события нет, основание является сильным свидетелем составности. Общий делитель 1<gcd(a,n)<n ещё раньше даёт составность напрямую; при вычислении теста этот простой контроль не нужно терять.

Единица после неправильного предшественника запрещена в поле

Если в цепочке x²≡1, но x не равен ±1, найден нетривиальный корень единицы. Для простого модуля это невозможно: n делило бы (x−1)(x+1), не деля ни один множитель. Для составного модуля ситуация возможна, и НОД(x−1,n) либо НОД(x+1,n) может дать собственный делитель. Это объясняет, какую информацию теряет один финальный тест Ферма.

Прохождение одного сильного испытания не является доказательством простоты. У составного числа могут быть сильные лжецы — основания, для которых нужная форма цепочки случайно выполняется. Вероятностная оценка после нескольких испытаний требует случайного выбора оснований по заявленной модели. В этой главе вывод детерминированный и односторонний: предъявленная плохая цепочка доказывает составность, без оценки случайной ошибки.

Сохраняйте и промежуточные остатки, и границу уровней

Минус один разрешается только до последнего возведения, соответствующего показателю n−1. Вычисление лишних уровней может принять число по событию вне условия теста. Для учебного свидетельства удобно записать d,s и список остатков: проверяющий повторяет несколько модульных квадратов. Полная факторизация n для такого отрицательного свидетельства не нужна, хотя иногда извлекается как полезный дополнительный результат.

Ферма проходит, сильный тест отвергает

Условие. Примените основание 2 к n=1105. Запишите сильную цепочку и найдите собственный делитель через нетривиальный корень единицы.

  1. Имеем 1104=16·69, поэтому d=69, s=4. Прямое модульное возведение даёт 2⁶⁹≡967.
  2. Последовательные квадраты по модулю 1105 равны 259,781,1; ещё один квадрат остаётся единицей. Ни начальный остаток, ни разрешённые четыре уровня не равны −1≡1104; начальный остаток не равен 1.
  3. Следовательно 2 является сильным свидетелем составности. При этом 2¹¹⁰⁴≡1, так что обычное испытание Ферма это основание пропустило бы.
  4. Предшественник единицы x=781 не равен ±1. Вычисляем gcd(780,1105)=65 и gcd(782,1105)=17. Оба результата являются собственными делителями.

Ответ. 1105 составное; сильная цепочка 967,259,781,1 даёт свидетельство, несмотря на успешное сравнение Ферма.

Проверка. Независимое целое произведение 5·13·17=1105 подтверждает составность. Все звенья проверены модульным квадратом, а сравнения 2¹¹⁰⁴ и каждого разрешённого уровня пересчитаны отдельным pow.

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

Проверьте понимание

Какой вывод даёт указанная цепочка для основания 2 и числа 1105?

Вопросы к этой главе

Обязательно ли извлекается делитель?

Нет. Свидетельство составности может возникнуть без предъявленного нетривиального корня единицы и без найденного НОД. Отрицательное решение теста уже доказано нарушением необходимого условия для простого числа.

Почему чётные числа рассматривают отдельно?

Разложение n−1=2ˢd с s≥1 требует нечётного n. Чётное n>2 сразу составное, а n=2 простое. Эти граничные случаи обрабатывают до описанной цепочки.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Keith Conrad: The Miller–Rabin Test, §2

    Прочитаны факторизация n−1, Definition2.3 и необходимая дизъюнкция для простого модуля. Наш расчёт для 1105 использует только определение теста и отдельный НОД; примеры источника не воспроизводятся.

Сертификат простоты из факторизации n−1

Положительный результат степенного испытания можно превратить в доказательство простоты, если контролировать полный порядок основания. Факторизация n−1 позволяет проверить этот порядок несколькими меньшими степенями. Получается конечный сертификат, проверка которого логически сильнее одного успешного сравнения Ферма.

Перед началом: Порядок обратимого остатка; НОД и простое разложение.

Полная факторизация задаёт набор проверок

Пусть n>2, полное разложение n−1 на простые известно и его простые множители действительно сертифицированы. Найдём a с a^(n−1)≡1 (mod n) и gcd(a^((n−1)/q)−1,n)=1 для каждого различного простого q, делящего n−1. Эти условия достаточны для простоты. НОД-версия сильнее простого неравенства остатков, но допускает особенно прозрачное доказательство через делители n.

Первое сравнение уже делает a обратимым. Возьмём произвольный простой p|n. Порядок h основания по модулю p делит n−1. Каждый НОД гарантирует, что a^((n−1)/q) не равен 1 даже по модулю этого p. Поэтому h не делит ни один из показателей (n−1)/q. Любой собственный делитель n−1 делил бы хотя бы один из них, значит h=n−1.

Большой порядок запрещает собственный простой делитель

По теореме Лагранжа h делит p−1, поскольку ненулевые остатки простого поля образуют группу размера p−1. Из h=n−1 следует p≥n. Но p — делитель положительного n, поэтому p=n и число простое. Это доказательство не предполагает простоту n при использовании группового порядка: поле берётся по заведомо простому делителю p.

Проверки выполняют по различным простым q, а не по всем делителям и не только по одному выбранному множителю. Если в разложении есть qᵉ, исключение показателя (n−1)/q заставляет порядок содержать всю нужную степень qᵉ. Пропущенный простой фактор может оставить собственный порядок, и сертификат перестанет доказывать заявленный результат.

Поиск сертификата и его проверка имеют разную стоимость

Трудность состоит в получении полного простого разложения n−1 и подходящего основания. Когда данные найдены, проверяющий перемножает факторы, проверяет их простоту, повторяет модульные степени и НОД. Для огромных чисел рекурсивные сертификаты факторов позволяют не доверять их неподтверждённым названиям. На маленьком примере ниже все эти предпосылки проверяются непосредственно, а отсутствие удачного основания при первой попытке не объявляется доказательством составности.

Сертификат для 73

Условие. Докажите простоту n=73 с основанием a=5 и полной факторизацией 72=2³·3², используя НОД-условия.

  1. Числа 2 и 3 простые, а 2³·3²=72=n−1. Поэтому нужны проверки только для различных q=2 и q=3.
  2. Быстрые модульные степени дают 5⁷²≡1, 5³⁶≡72 и 5²⁴≡8 по модулю 73.
  3. НОД(72−1,73)=НОД(71,73)=1 и НОД(8−1,73)=НОД(7,73)=1. Оба обязательных условия выполнены.
  4. Для любого простого p|73 порядок пятёрки поэтому равен 72 и делит p−1. Получаем p≥73, значит 73 не имеет собственного простого делителя и простое.

Ответ. Данные (73,5,72=2³·3²) являются проверенным сертификатом простоты.

Проверка. Независимый перебор делителей до √73 проверяет 2,3,5,7 и не находит делителя. Прямой цикл степеней пятёрки по модулю 73 впервые возвращается к 1 на показателе 72, подтверждая использованный порядок.

Где легко ошибиться. Не предполагайте заранее, что группа по модулю n является полем или имеет размер n−1. В доказательстве это свойство используется только для простого делителя p, а простота самого n выводится позже.

Проверьте понимание

Чему равен порядок 5 по модулю 73 согласно проверенному сертификату?

Вопросы к этой главе

Достаточно ли проверить только q=2?

Нет. Например, основание может иметь порядок, содержащий всю двойку из n−1, но недостающую степень тройки. Каждая различная простая составляющая требует отдельного исключения собственного порядка.

Почему используются НОД, а не просто остаток, отличный от 1?

Ненулевой по модулю n остаток может быть нулевым по одному из его простых делителей. НОД=1 исключает это для каждого p|n и позволяет данное доказательство через порядок в поле.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Carl Pomerance: Primality testing, slides7–8

    Прочитаны критерий Lucas по всем простым делителям n−1 и доказательство через порядок и φ(n). Здесь используется более сильное gcd-условие, чтобы дать отдельное доказательство через каждый простой делитель n. Сертификат для 73 построен отдельно.

Числа Кармайкла и критерий Корсельта

Некоторые составные числа удовлетворяют сравнению Ферма для каждого взаимно простого основания. Критерий Корсельта характеризует их через факторизацию: отсутствие квадратных простых делителей и согласование всех локальных порядков. Это структурный ответ обо всех основаниях сразу, а не ещё одно удачное степенное испытание.

Перед началом: Малая теорема Ферма; Китайская теорема об остатках и квадратсвободность.

Все основания означают сильное универсальное требование

Числом Кармайкла называется составное n>1, для которого a^(n−1)≡1 mod n при каждом a с НОД(a,n)=1. Условие составности входит в определение: простые числа тоже выполняют сравнение, но к этой категории не относятся. Проверка одного или нескольких выбранных оснований не устанавливает универсальный квантор.

Критерий Корсельта утверждает: составное n является числом Кармайкла тогда и только тогда, когда оно квадратсвободно и p−1 делит n−1 для каждого простого p|n. В факторизации должны быть известны все простые множители; неполная проверка нескольких делителей не удостоверяет условия для остальных.

Достаточность собирает локальные сравнения

Пусть условия выполнены. Для взаимно простого a малая теорема Ферма даёт a^(p−1)=1 mod p. Так как p−1|n−1, получаем a^(n−1)=1 mod p для каждого простого делителя. Квадратсвободность означает, что произведение этих различных простых равно n, и китайская теорема объединяет сравнения в одно по n.

Без квадратсвободности такое объединение контролировало бы лишь произведение различных простых, а не их более высокие степени. Например, число девять имеет p−1=2, делящее восемь, но 2⁸≡4 mod 9. Поэтому требование отсутствия квадратов не является избыточным следствием остальных делимостей.

Необходимость использует подходящие основания

Если p²|n, можно выбрать основание, равное 1+p по модулю p² и единице по другим простым степенным компонентам. Оно взаимно просто с n. Биномиальное раскрытие даёт a^(n−1)≡1+(n−1)p mod p², что не равно единице, поскольку p не делит n−1. Так универсальное требование исключает повторный простой множитель.

Для уже квадратсвободного n выберем основание, являющееся генератором по модулю конкретного p и единицей по другим простым компонентам. Китайская теорема позволяет такой выбор. Сравнение Ферма для него вынуждает порядок p−1 делить n−1. Тем самым оба условия критерия следуют именно из требования ко всем взаимно простым основаниям.

Универсальное псевдопростое число

Условие. Докажите, что 1729=7·13·19 является числом Кармайкла. Сравните с девятью и объясните, почему простой модуль 13 не включается в ответ.

  1. Числа 7,13,19 простые и различны. Следовательно, указанная факторизация полна, а 1729 составно и квадратсвободно.
  2. Вычисляем n−1=1728. Локальные порядки p−1 равны 6,12,18; соответствующие частные равны 288,144,96 и являются целыми.
  3. Критерий Корсельта доказывает сравнение Ферма для каждого взаимно простого основания. Число таких классов равно (7−1)(13−1)(19−1)=1296.
  4. У девяти квадратсвободность нарушена. Прямой свидетель: НОД(2,9)=1, но 2⁸ mod 9=4, поэтому девять не является числом Кармайкла.
  5. Число 13 простое и потому удовлетворяет сравнениям Ферма, но не условию составности определения. Оно также не является числом Кармайкла.

Ответ. 1729 — число Кармайкла; девять и 13 — нет. Для 1729 одновременно доказаны все 1296 взаимно простых оснований.

Проверка. Ограниченное перечисление всех единиц по модулю 1729 независимо проверяет универсальное сравнение. Контрпример для девяти подтверждает необходимость квадратсвободности.

Где легко ошибиться. Не называйте число простым после прохождения всех доступных проверок Ферма. Числа Кармайкла проходят их для каждого взаимно простого основания, оставаясь составными.

Проверьте понимание

Какое из чисел является числом Кармайкла?

Вопросы к этой главе

Что происходит с основанием, имеющим общий делитель с n?

Оно не входит в универсальное требование определения. Найденный общий делитель сам по себе может раскрыть составность, но сравнение Ферма в такой постановке на это основание не распространяется.

Почему простое 13 не считается частным случаем числа Кармайкла?

Термин по определению зарезервирован для составных чисел. Иначе критерий описывал бы вместе обычные простые и составные исключения, скрывая смысл провала теста Ферма.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Handbook of Applied Cryptography, §4.2: Fermat tests and Carmichael numbers

    Прочитаны определение чисел Кармайкла и квадратсвободный критерий через p−1|n−1. Доказательства необходимости с выбранными основаниями и полный пример 1729 сформулированы самостоятельно; проверка Ферма не выдаётся за критерий простоты.

Разложение Полларда p−1 и гладкий порядок

Порядки элементов можно использовать не только для испытания простоты, но и для извлечения делителя составного числа. Метод Полларда p−1 подбирает показатель, кратный гладкому порядку одного простого компонента. НОД отделяет компоненты, на которых степень уже стала единицей, от остальных.

Перед началом: Малая теорема Ферма и порядок элемента; Наибольший общий делитель.

Показатель строится из ограниченных простых степеней

Для границы B возьмём M=НОК(1,2,…,B). Он содержит каждую простую степень не больше B в максимальной допустимой степени. Если простой делитель p числа n удовлетворяет p−1|M и основание a взаимно просто с n, то aᴹ≡1 mod p. Следовательно, p делит НОД(aᴹ−1,n).

Важно контролировать не только величины простых делителей p−1, но и их степени. Например, для p−1=12 при B=3 показатель M=6 не содержит нужной четвёрки. Термин гладкости без уточнения степенной границы может скрыть это различие. Условие p−1|M достаточно, но не необходимо: конкретное основание иногда имеет меньший порядок.

Степень вычисляют по модулю n до взятия НОД

Вычислим b=aᴹ mod n повторным возведением в квадрат, затем d=НОД(b−1,n). Не требуется строить огромное целое aᴹ. Если 1<d<n, получен собственный делитель, и его проверяют точным делением n. Предварительный НОД(a,n) иногда сам сразу находит фактор.

Эта процедура не является тестом простоты. Её положительный результат даёт факторизацию, а отрицательный говорит лишь о неудаче выбранных параметров. Гладкая структура относится к неизвестным простым компонентам n; поэтому алгоритм использует предположение о них как поисковую стратегию, не выдавая его за заранее доказанное свойство входа.

Две неудачи требуют разных объяснений

При d=1 выбранный показатель не сделал основание единицей ни на одном простом компоненте, который мог бы дать делитель. При d=n он сделал это сразу на всех компонентах в нужной степени, и НОД уже не разделяет их. Оба результата не дают собственного фактора.

Увеличение B не гарантирует улучшения: удачное разделение может исчезнуть, если новый M захватит порядки оставшихся компонентов. Тогда полезны изменение основания, более тонкое сохранение промежуточных стадий или другая стратегия факторизации. Для учебного анализа достаточно показать на одном числе все три исхода и проверить их точными остатками.

Увеличение границы превращает успех в полную неудачу

Условие. Примените основание a=2 к n=299 при B=3,4,11. Найдите показатели M, остатки b и НОД, объяснив различие результатов через простые компоненты.

  1. Факторизация для независимой проверки равна 299=13·23. При B=3 показатель M=6, b=2⁶ mod 299=64 и НОД(63,299)=1: фактор не найден.
  2. При B=4 имеем M=12. Остаток b=209, поэтому НОД(208,299)=13. Это собственный делитель, а частное равно 23.
  3. Причина успеха: 13−1=12 делит M, тогда как порядок двойки по модулю 23 равен 11 и не делит 12. Степень стала единицей лишь на одном компоненте.
  4. При B=11 показатель НОК(1,…,11)=27720 кратен и 12, и 22. Теперь b=1 mod 299, поэтому НОД(0,299)=299: разделение потеряно.
  5. Прямые проверки 13·23=299 и локальные степени подтверждают фактор и объясняют обе неудачи. Большая граница здесь дала более дорогой и менее полезный результат.

Ответ. Для B=3 получен d=1, для B=4 — фактор 13, для B=11 — всё число 299. Увеличение гладкой границы не монотонно по полезности.

Проверка. Повторное возведение в квадрат проверяет b=64,209,1. Независимые локальные порядки 12 и 11 объясняют, какие компоненты входят в каждый НОД.

Где легко ошибиться. Не трактуйте d=1 как доказательство простоты, а d=n — как найденный собственный делитель. Оба исхода означают неудачу разделения для данных параметров.

Проверьте понимание

Какой d получается для n=299, a=2, B=4?

Вопросы к этой главе

Почему показатель берут как НОК, а не произведение всех чисел?

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

Можно ли найти фактор, если p−1 не делит M?

Иногда да: достаточно, чтобы M делился на порядок выбранного a по модулю p. Делимость p−1 является удобной общей достаточной гарантией для любого ненулевого основания, а не обязательным условием каждого успеха.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Handbook of Applied Cryptography, §3.2: Pollard p−1

    Прочитаны мотивировка гладкости и алгоритм 3.14. Три границы, различие НОД 1/n и собственный фактор 299 рассчитаны отдельно; никакая оценка пригодности для произвольного большого входа не заявляется.

Поллард rho: совпавшие остатки обнаруживают делитель

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

Перед началом: НОД и делимость разности при совпавших остатках; Итерация функции на конечном множестве.

Одна последовательность имеет несколько проекций

Поиск собственного делителя нечётного составного n итерациями целого многочлена; конкретная трасса детерминирована выбранными началом и параметром.

Выберем f(x)=x²+c и положим xᵢ₊₁=f(xᵢ) mod n. Для любого делителя p числа n редукция этой последовательности по p совпадает с отдельным запуском той же функции по p. Это следует из сохранения сложения и умножения при взятии остатка. Знать p для вычисления глобальной последовательности не требуется.

Если xᵢ≡xⱼ по p, число p делит разность и входит в gcd(xᵢ−xⱼ,n). Но такой НОД может содержать несколько простых компонентов и даже всё n. Он не обязан быть простым. Для факторизации достаточно собственного делителя d с 1<d<n: затем делят n на d и при необходимости продолжают отдельно для обоих множителей.

Флойд сравнивает медленный и быстрый ход

Чтобы не хранить все предыдущие остатки, держат a и b с одинаковым началом. На каждом шаге a заменяют на f(a), а b на f(f(b)). После i шагов это xᵢ и x₂ᵢ. На конечном пространстве любая траектория имеет хвост и цикл; такое сравнение в конце обнаружит совпадение в каждом фиксированном компоненте.

Вместо проверки a=b по полному модулю вычисляют d=gcd(|a−b|,n). При d=1 продолжают; при собственном d возвращают фактор; при d=n данная попытка не разделила компоненты. Начало или c меняют и запускают новую попытку. Полное совпадение само по себе не сообщает ни простоты, ни отсутствия факторизации.

Сертификат точен, ожидание скорости условно

Полезный результат легко проверить точным делением: остаток n mod d должен быть нулём, а границы d — строгими. Напротив, быструю находку нельзя обещать для любого фиксированного многочлена. Оценка порядка √p до столкновения использует модель поведения, похожего на случайное отображение по небольшому делителю p; она не является доказанной границей каждой детерминированной трассы.

Метод отличается от Полларда p−1: здесь не строится показатель, захватывающий гладкий порядок. Используется структура совпадений итераций, а не делимость p−1 выбранным НОК. В практической ограниченной попытке нужен предел шагов: исчерпание бюджета означает незавершённый поиск, а не математическое утверждение о простоте входа.

Компоненты совпали только по одному простому

Условие. Для n=1763 запустите f(x)=x²+1, a=b=2 и сравнение Флойда. Найдите первый собственный НОД и объясните его через простые компоненты.

  1. На первом шаге a=5,b=26, gcd(21,1763)=1. На втором a=26,b=1713, НОД также равен 1; все степени каждый раз сокращаются по 1763.
  2. Третий шаг даёт a=677,b=1641, четвёртый a=1713,b=1727. Разности 964 и 14 взаимно просты с 1763, поэтому попытка продолжается.
  3. На пятом шаге a=738,b=308. Разность 430 даёт gcd(430,1763)=43. Это собственный делитель, частное 1763/43=41.
  4. Независимо смотрим компоненты: 738 и 308 оба равны 7 по модулю 43, но по модулю 41 равны 0 и 21. Поэтому совпадение захватило именно компонент 43 и не захватило 41.

Ответ. Первый собственный НОД найден на шаге 5: d=43. Получена факторизация 1763=43·41.

Проверка. Прямое умножение 43·41=1763 подтверждает фактор. Независимый список x₀,…,x₁₀ и сравнения xᵢ,x₂ᵢ воспроизводят всю таблицу без двойного обновления быстрого указателя.

Где легко ошибиться. Значение gcd=n не является собственным фактором. Например, при n=21,c=1 и начале 2 уже первая пара (5,5) даёт 21, хотя само число вполне раскладывается.

Проверьте понимание

Какой собственный делитель даёт пятый шаг разобранной трассы n=1763,a=738,b=308?

Вопросы к этой главе

Найденное d обязательно простое?

Нет. Разность может одновременно делиться на несколько компонентов n. Любой собственный делитель полезен, но окончательная простая факторизация требует дальнейшей работы.

Зачем нужен НОД, если можно ждать равенства a=b?

Равенство по всему n означает совпадение во всех компонентах и даёт НОД n. Полезное раннее совпадение только в части компонентов незаметно обычной проверке равенства, но обнаруживается НОД.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться