Большие целые числа

В этом листке мы будем работать с большими целыми числами. Оказывается, что проверить простоту числа можно очень быстро (правда существует почти нулевая вероятность ошибки), а вот разложить число на простые множители сложно. Не в полной мере разбираясь, как и почему оно работает, мы реализуем достаточно быстрые алгоритмы проверки простоты (меньше 1с для чисел из 400 цифр), а также достаточно быстрый алгоритм факторизации (разложения на множители), работающий за время порядка $\sqrt[4]{n}$ (даже быстрее: за время порядка $\sqrt{p}$, где $p$ — максимальный простой делитель числа).

Часть задач предполагают теоретические выкладки, которые нужно сдавать устно, либо в виде текста решения в тестирующую систему, либо письмом на почту/телеграм.

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

A: Тест Ферма

Вам уже известна малая теорема Ферма: если число \(n\) — простое, то для любого числа \(1 \le a \le (n - 1)\) выполнено сравнение \(a^{n-1} \equiv 1\pmod{n}\). Отсюда следует, что если мы найдём такое \(a\), что это сравнение не выполнено, то число \(n\) заведомо не простое. Такая проверка простоты числа называется тестом Ферма.

Даны два натуральных числа: a и n. Напишите функцию fermat_test(a, n), возвращающую True если число \(a\) проходит тест Ферма для \(n\), и False иначе.

Для ускорения работы с большими числами в Python существует возможность возводить в степень по модулю некоторого числа: функция pow(a, k, n) вычислит \(a^k \mod{n}\).

2 5
True
65537 4295098369
False

B: Тест Ферма —2

Дано число N. Выведите в первой строке слово «Prime», если число N простое, и «Composite» иначе. Выведите во второй строке количество чисел от 1 до (N-1), проходящих тест Ферма.

5
Prime 4
5555
Composite 8

C: Качество теста Ферма

Очевидно, что если число \(n\) — простое, то любое число \(a\) пройдёт тест Ферма. Докажите, что если число \(n\) — составное, то все числа не взаимно простые с \(n\) тест не пройдут. Кроме того докажите, что если хотя бы одно из чисел, взаимно простых с \(n\) не пройдёт тест Ферма, то хотя бы половина чисел, взаимно простых с \(n\) его не пройдут. Таким образом, если число \(n\) составное, а число \(a\) случайное из диапазона от \(2\) до \(n-1\), то с вероятностью \(\dfrac12\) оно не пройдёт тест Ферма. Однако это утверждение не совсем верно, см. задачу D.

D: Числа Кармайкла

Числом Кармайкла называется всякое составное число \(n\), которое удовлетворяет сравнению \(b^{n-1}\equiv 1\pmod{n}\) для всех целых \(b\), взаимно простых с \(n\). В 1994 году доказали, что чисел Кармайкла бесконечно много, более того, при \(n\gg0\) среди чисел от 1 до \(n\) по крайне мере \(n^{2/7}\) кармайкловых чисел. Из-за этого тест Ферма работает не идеально, хотя вероятность встретить число Кармайкла с ростом \(n\) стремится к нулю.

Даны числа a, b. Выведите все числа Кармайкла на отрезке [a, b] (или пустую строчку, если их нет).

1000 2000
1105 1729

E: Числа Кармайкла и невероятные совпадения

Напишите программу, которая вычисляет два числа: наименьшее число, представимое в виде суммы двух квадратов четырьмя способами; наименьшее число, представимое в виде суммы двух кубов двумя способами;

12345 67890

F: Тест простоты Ферма

Тест простоты, основанный на тесте Ферма, заключается в следующем. Пусть мы хотим проверить простоту числа \(n\). Зафиксируем для себя натуральное число \(m\), выберем \(m\) случайных чисел от \(2\) до \(n-1\), и для каждого проведём тест Ферма из задачи A. Если хотя бы одно число не прошло тест, то число \(n\) заведомо составное. Если же все тесты пройдены, то либо число \(n\) — число Кармайкла, либо с вероятностью по крайней мере \(\frac{1}{2^m}\) является простым. Среди чисел от 1 до 1000000000 существует 50847534 простых чисел и всего 646 чисел Кармайкла. То есть вероятность наткнуться на число Кармайкла всего \(646/50847534 \approx 1.27 \cdot 10^{-5} \approx 1/100000\). При выборе \(m=20\) вероятность того, что составное число, не являющееся числом Кармайкла, пройдёт тест, будет равна \(\frac{1}{2^{20}}\approx 1/1000000\).

Напишите функцию fermat_primality_test(n), проверяющую простоту числа при помощи 20 раундов теста Ферма. Функция должна возвращать False, если число \(n\) составное, и True, если число \(n\) скорее всего простое. Число \(n\) может содержать до 400 десятичных знаков.

Для того, чтобы выбрать случайные числа из диапазона, используйте функцию randint(a, b) из модуля random, возвращающую случайное число из отрезка \([a,b]\).

170141183460469231731687303715884105721
False
170141183460469231731687303715884105727
True

FT: Доказательство теста Ферма

Пусть число $n$ — составное, а число $1 < a < n - 1$ — не проходит тест Ферма (то есть \(a^{n-1} \not\equiv 1\pmod{n}\)). Докажите, что по крайней мере половина чисел от 1 до $n-1$ не проходят тест Ферма.

G: Свидетели простоты в тесте Миллера — Рабина

Тест Миллера — Рабина является усовершенствованием теста Ферма. Числа Кармайкла не проходят тест Миллера — Рабина, поэтому он является универсальным.

Пусть \(n\) — некоторое нечётное простое число. Представим число \(n-1\) в виде \(n-1 = 2^s \cdot u\), где \(s\) натуральное, а \(u\) — нечётное. Возьмём любое число \(a\) от \(2\) до \(n-1\). Тогда из малой теоремы Ферма следует, что \(a^{n-1} = a^{2^s u} \equiv 1\pmod{n} \). Кроме того, по простому модулю \(n\) существуют ровно два квадратных корня из единицы: \(1\) и \(-1\). Поэтому число \(a^{2^{s-1} u}\), являясь квадратным корнем из единицы, равно либо \(1\), либо \(-1\). Если \(a^{2^{s-1} u}\equiv 1\pmod{n}\), то мы снова можем извлечь корень. Мы можем продолжать это действие до тех пор, пока либо не закончится \(s\), либо очередной корень не будет равен \(-1\).

Число \(a\) называется свидетелем простоты числа \(n\), если либо \(a^{u}\equiv 1\pmod{n}\), либо в последовательности \(a^{u}, a^{2^1 u}, \ldots, a^{2^{s-1} u}\) встречается \(-1\) по модулю \(n\). Ясно, что если некоторое число \(a\) не является свидетелем простоты, то число \(n\) заведомо составное. Оказывается, что для составного числа \(n\) не более \((n-1)/4\) чисел от \(1\) до \(n-1\) являются свидетелями простоты \(n\).

Даны два натуральных числа: a и n. Напишите функцию miller_rabin_test(a, n), возвращающую True если число \(a\) является свидетелем простоты для \(n\), и False иначе.

2 5
True
65537 4295098369
False

H: Количество свидетелей простоты

Дано число N. Выведите в первой строке слово «Prime», если число N простое, и «Composite» иначе. Выведите во второй строке количество чисел от 2 до (N-2), являющихся свидетелями простоты числа N.

65537
Prime 65534
65533
Composite 4

I: Тест простоты Миллера — Рабина

Пусть мы хотим проверить простоту нечётного числа \(n\). Зафиксируем для себя натуральное число \(m\), выберем \(m\) случайных чисел от \(2\) до \(n-1\). Если хотя бы одно из чисел не является свидетелем простоты, то число \(n\) заведомо составное. Иначе число \(n\) с вероятностью по крайней мере \(\frac{1}{4^m}\) является простым.

Напишите функцию miller_rabin_primality_test(n), реализующую эту идею. В качестве числа \(m\) используйте битовую длину числа \(n\) (n.bit_length()) (какова вероятность того, что проверив все k-битовые числа, мы хоть раз ошибёмся?). Функция должна возвращать False, если число \(n\) составное, и True, если число \(n\) скорее всего простое. Число \(n\) может содержать до 400 десятичных знаков.

170141183460469231731687303715884105721
False
170141183460469231731687303715884105727
True

J: Ближайшее простое число

Дано число \(n\). Найдите минимальное простое число, больше либо равное \(n\). Число \(n\) может содержать до 400 десятичных знаков.
1000000000000000000
1000000000000000003

Профилирование программы в Python

Чтобы разобраться, какие части программы работают дольше всего, существуют специальные инструменты. Вот пример использования одного из них:

from cProfile import Profile
pr = Profile()
pr.enable()

# Ваш код

pr.disable()
pr.print_stats()

Нет нужны помнить всю эту конструкцию, достаточно помнить ключевое слово cProfile.

Вот как это «запомнить»
Используем командную строку:
*** Python 3.2.5 (default, May 15 2013, 23:06:03) [MSC v.1500 32 bit (Intel)] on win32. ***
>>> import cProfile
>>> dir(cProfile)
['Profile',
 '__all__',
 '__builtins__',
 '__cached__',
 '__doc__',
 '__file__',
 '__name__',
 '__package__',
 '_lsprof',
 'label',
 'main',
 'run',
 'runctx']
Видим среди элементов модуля cProfile класс Profile. Импортируем его.
>>> from cProfile import Profile
>>> pr = Profile()
>>> dir(pr)
['__class__',
 ...,
 '__weakref__',
 'clear',
 'create_stats',
 'disable',
 'dump_stats',
 'enable',
 'getstats',
 'print_stats',
 'run',
 'runcall',
 'runctx',
 'snapshot_stats']
>>> 
Видим у класса Profile методы enable, disable и print_stats, которые нам и нужны.

Построчное профилирование программы в Python

Также возможно построчное профилирование. Однако для его использования потребуется установить библиотеку line_profiler. Это может оказаться не так просто... Скорее всего команда pip install line_profiler --user потерпит неудачу из-за отсутсвия компилятора языка C. Поэтому можно сразу отправиться на страницу собранных для windows пакетов и скачать оттуда подходящий whl-файл (в имени line_profiler‑2.1.2‑cp36‑cp36m‑win_amd64.whl 36 — это версия питона 3.6, win32/win_amd64 — это битность ОС). Дальше для установки пакета нужно будет из anaconda prompt выполнить команду вида pip install "Y:\path\to\whl\line_profiler‑2.1.2‑cp36‑cp36m‑win_amd64.whl" --user, и дело в шляпе!

Наконец-таки, если библиотека установлена, то воспользоваться ей можно так:

# Наш код без input'ов  ######################
def glue(a, b):
    res = a + ' ' + b
    return res

def main_func(n):
    res = ""
    for i in range(n):
        res = glue(res, str(i))
    fast_res = ' ' + ' '.join(str(i) for i in range(n))
    assert res == fast_res
    return res
# Конец кода  ################################

from line_profiler import LineProfiler
profiler = LineProfiler()
# Добавляем в профайлер все необходимые функции
profiler.add_function(glue)
profiler.add_function(main_func)
# Запускаем главную функцию. Вместо 50000 вписать её параметры (если их нет, то оставить пустым)
profiler(main_func)(50000)
# Выводим результат
profiler.print_stats()
На выходе будет вот такой отчёт:
Timer unit: 1e-07 s

Total time: 0.483919 s
File: dummy.py
Function: glue at line 2

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
     2                                           def glue(a, b):
     3     50000    4531886.0     90.6     93.6      res = a + ' ' + b
     4     50000     307305.0      6.1      6.4      return res

Total time: 0.710338 s
File: dummy.py
Function: main_func at line 6

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
     6                                           def main_func(n):
     7         1         30.0     30.0      0.0      res = ""
     8     50001     372843.0      7.5      5.2      for i in range(n):
     9     50000    6393715.0    127.9     90.0          res = glue(res, str(i))
    10         1     336431.0 336431.0      4.7      fast_res = ' ' + ' '.join(str(i) for i in range(n))
    11         1        350.0    350.0      0.0      assert res == fast_res
    12         1          9.0      9.0      0.0      return res

Здесь видно, что 90.0% времени уходит на строчку res = glue(res, str(i)), которая вызывается 50000 раз. Внутри функции glue 93.6% времени уходит на склейку строк. И действительно, так строки клеить нельзя: это приводит к квадратичному времени работы. Склейка при помощи join работает в 20 раз быстрее.

K: Случайные простые числа

Даны числа k и n. Выведите n случайных простых чисел битовой длины k.

Для генерации больших случайных простых чисел часто используют следующий алгоритм:

  1. При помощи решета Эратосфена получаем список простых чисел от 2 до 65537;
  2. Берём случайное число от \(2^{k-1}\) до \(2^k - 1\);
  3. Если оно делится на одно из простых от 2 до 65537, то переходим к пункту 2;
  4. Иначе проводим k тестов Миллера — Рабина;
  5. Если число не прошло хотя бы один тест, то переходим к пункту 2, иначе принимаем данное случайное число как простое;
  6. Повторяем пункты 2-5 до тех пор, пока не накопится необходимое количество простых чисел.

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

7 5
113 67 107 103 107
50 5
574328689204999 1093469055310991 934759628998883 763430397828173 985863319402817

Теорема Рабина

Пусть \(n\) — натуральное число, большее 3. Представим число \(n-1\) в виде \(n-1 = 2^s \cdot u\), где \(s\) натуральное, а \(u\) — нечётное. Число \(a\) называется свидетелем простоты числа \(n\), если либо \(a^{u}\equiv 1\pmod{n}\), либо в последовательности \(a^{u}, a^{2^1 u}, \ldots, a^{2^{s-1} u}\) встречается \(-1\) по модулю \(n\).

Теорема Рабина гласит, что у составного числа \(n>4\) — не более \((n-1)/4\) свидетелей простоты.

Это непростая теорема, однако отдельные её части не такие уж и сложные.

В задачах будет использоваться функция Эйлера — $\varphi(n)$ — равна количеству натуральных чисел, меньших $n$ и взаимно простых с ним.

L1: Теорема Рабина — 1

Пусть $n=2^k$ и $k>2$. Докажите, что только 1 проходит тест Ферма, а значит является единственным является свидетелем простоты.

L2: Теорема Рабина — 2

Пусть $n$ — чётное, но не степень двойки. Докажите, что не более $(n/2-1)/2$ чисел являются свидетелями простоты.

Первообразные корни

Пусть $n=p^k$ — степень нечётного простого числа. Тогда, во-первых, существует в точности $\varphi(n)=p^{k-1}(p-1)$ остатков $a$ (по модулю $n$) взаимно простых с $n$; А во-вторых, существует такой остаток $g$ (он называется первообразным корнем), что любой остаток $a$, взаимнопростой с $n$, является его степенью.
Например, если $n=5$, то $\varphi(n)=4$, $g=2$: $2^0=1$, $2^1=2$, $2^2=4$, $2^3=3$.
Если $n=3^2=9$, то $\varphi(n)=6$, $g=2$: $2^0=1$, $2^1=2$, $2^2=4$, $2^3=8$, $2^4=7$, $2^5=5$.
Если $n=17$, то $\varphi(n)=16$, $g=3$: $3^0=1$, $3^1=3$, $3^2=9$, $3^3=10$, $3^4=13$, $3^5=5$, $3^6=15$, $3^7=11$, $3^8=16$, $3^9=14$, $3^{10}=8$, $3^{11}=7$, $3^{12}=4$, $3^{13}=12$, $3^{14}=2$, $3^{15}=6$.
Если $n=5^2$, то $\varphi(n)=20$, $g=2$: $2^0=1$, $2^1=2$, $2^2=4$, $2^3=8$, $2^4=16$, $2^5=7$, $2^6=14$, $2^7=3$, $2^8=6$, $2^9=12$, $2^{10}=24$, $2^{11}=23$, $2^{12}=21$, $2^{13}=17$, $2^{14}=9$, $2^{15}=18$, $2^{16}=11$, $2^{17}=22$, $2^{18}=19$, $2^{19}=13$.

L3: Теорема Рабина — 3

Пусть $n = p^k$, где $p$ — простое. Докажите, что тест Ферма пройдут ровно $p-1$ число, следовательно не более $p-1$ чисел являются свидетелями простоты.

L4★: Теорема Рабина — 4

Пусть $n$ — нечётное и имеет по крайней мере три различных простых делителя. Докажите, что не более $\varphi(n)/4$ чисел являются свидетелями простоты.

L5★: Теорема Рабина — 5

Пусть $n = p^m \cdot q^l$, где $p$ и $q$ — простые. Докажите, что не более $\varphi(n)/2$ чисел проходят тест Ферма, и что не более половины из них являются свидетелями простоты.

M: Числа Мерсенна

Числа Мерсенна — это числа вида \(M_n = 2^n - 1\), где n — натуральное число. Докажите, что если число Мерсенна \(M_n\) является простым, то и число \(n\) также является простым.

N: Тест Люка — Лемера

Оказывается, что для проверки простоты чисел Мерсенна существуют крайне эффективный алгоритм. Он называется тестом простоты Люка — Лемера, благодаря которому простые числа Мерсенна давно удерживают лидерство как самые большие известные простые числа. На январь 2015 года самым большим известным человечеству простым числом является число \(M_{57885161}\), в котором 17425170 десятичных знаков. Это простое число было обнаружено 25 января 2013 и удерживает первое место уже почти два года.

Разберитесь с алгоритмом по страничке в Википедии. Напишите программу, которая по числу k вычисляет k-е простое число Мерсенна. Гарантируется, что это число не превосходит \(M_{3000}\).

1
3
10
618970019642690137449562111

O: ρ-aлгоритм Полларда для поиска делителей

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

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

Пусть \(n\) — нечётное составное число, а \(p\) — его наименьший простой делитель.

Наивный алгоритм потребует порядка \(p\) операций для его нахождения. Пусть, например, число \(n\) содержит 30 десятичных цифр и является произведением двух больших простых чисел (по 15 знаков в каждом). Наивному алгоритму потребуется порядка \(10^{15}\) операций. Если выполнять по \(10^9\) операций в секунду, то на поиск делителя уйдёт порядка 11 дней. Не слишком шустро... Оказывается можно найти делитель за время порядка \(\sqrt{p}\) (правда не обязательно наименьший). Если в нашем примере \(10^9\) операций в секунду заменить на более реальные \(10^6\) операций в секунду для Python, то потребуется порядка 30 секунд.

Основная идея алгоритма прячется за идеей парадокса дней рождения: если в группе хотя бы 23 человека, то с вероятностью хотя бы 50% у двух из них совпадают дни рождения. Никакого парадокса в этом утверждении нет, однако утверждение может показаться неочевидным, так как вероятность совпадения дней рождения двух человек в любой день года (1/365 = 0,27%), помноженная на число человек в группе из 23, даёт лишь 23/365 = 6,3%. Весь секрет в том, что для совпадения дней рождения необходимо совпадения хотя бы в одной из пар чисел, а их не 23, а \(23\cdot 22 / 2 = 253\). А для 50% вероятности совпадения только номера дня в месяце достаточно всего 7 человек.

Теперь ближе к алгоритму: рассмотрим последовательность случайных чисел \(x_1, x_2, \ldots, x_k\). Будем смотреть на неё как на последовательность чисел по модулю \(n\), и как на последовательность чисел по модулю \(p\) (пока нам неизвестному). Очевидно, что вероятность того, что два числа совпадут по модулю \(p\) больше, чем вероятность совпадения по модулю \(n\). Пусть числа \(x_i\) и \(x_j\) совпали по модулю \(p\), но не по модулю \(n\). Тогда \((x_i - x_j)\,\vdots\, p\) и НОД \((x_i - x_j, n)\) делится на \(p\), но не совпадает с \(n\), то есть мы нашли делитель числа \(n\).

Илюстрация с ρ Однако пока эта идея в реальности работает плохо, так как нужно слишком часто считать НОД (порядка квадрата количества случайных чисел). Для дальнейшей оптимизации требуется идея, от которой алгоритм и получил имя «ρ-алгоритм». Рассмотрим какую-нибудь функцию \(F(x)\) такую, что её во-первых можно легко вычислять, во-вторых, для любого числа \(p\) если \(x\equiv y\pmod{p}\), то \(F(x)\equiv F(y)\pmod{p}\), в-третьих, последовательность чисел \(F(F(\ldots F(x)\ldots))\) выглядит достаточно случайной, и наконец \(F(x)\) не взаимно однозначна. Джон Поллард использовал \(F(x) = (x^2 - 1)\pmod{n}\), однако сейчас принято использовать \(F(x) = (x^2 + 1)\pmod{n}\). Выберем в качестве \(x_1\) какое-нибудь случайное число, и будем далее строить последовательность по правилу \(x_k = F(x_{k-1})\). Пусть на каком-то очередном шаге после добавления числа \(x_l\) возникло совпадение остатка по модулю \(p\) с более ранним числом \(x_s\). Тогда для любого натурального \(t\) имеем \(x_{l+t} \equiv x_{s+t}\pmod{p}\). Если нарисовать картинку, то получится как раз греческая буква «ро»: сначала какой-то уникальный префикс, а затем остатки будут повторяться с периодом $l-s$.

Теперь воспользуемся трюком от Роберта Флойда для экономного поиска этого самого цикла из буквы «ро». Для этого заметим, что найдется такое число \(w\), не превосходящее \(l\), что \(x_w\equiv x_{2w}\pmod{p}\) (покажите это, явно указав такое \(w\)). Поэтому мы можем взять две равных переменных, к первой последовательно применять \(F(x)\), а ко второй — \(F(F(x))\), до тех пор, пока не возникнет совпадения по модулю какого-нибудь делителя (которое мы обнаружим НОД'ом), либо по модулю самого числа \(n\), если не повезло. Отсюда уже следует наш алгоритм:

  1. В качестве x берём случайное число, берём y=x;
  2. Заменяем x на F(x), а y — на F(F(y)) (таким образом, если \(x=x_i\), то \(y=x_{2i}\));
  3. Вычисляем d = НОД(x - y, n);
  4. Если d = 1, то переходим к шагу 2, если d = n, то переходим к шагу 1, иначе возвращаем d.

Пример работы алгоритма при факторизации числа 11021:

x        y         НОД(x - y, n)
------------------------------
2        2         1
5        26        1
26       6469      1
677      1770      1
6469     7548      1
1225     4445      1
1770     1984      107
Делитель 107 числа 11021 найден всего за 7 шагов. Вот пример с факторизацией числа 112313779:
x           y             НОД(x - y, n)
---------------------------------------
2           2             1
5           26            1
26          458330        1
677         47580192      1
458330      97053593      1
39622171    54070390      1
47580192    43379730      1
83156460    62097056      1
97053593    91301546      11909

Реализуйте ρ-aлгоритм Полларда для поиска делителей числа в виде функции pollards_rho_divisor(n), принимающей на вход составное число и возвращающей любой его нетривиальный делитель.

В алгоритме выше есть неточность. В некоторых случаях функция \(F(x) = (x^2 + 1)\pmod{n}\) не позволяет найти делитель ни при каком начальном числе. Найдите несколько таких \(n\), что в них общего? При первом зацикливании рекомендуется заменить 1 на какое-нибудь другое желательно небольшое по модулю число, но не 0, и не 2.

6
3
10403
101
288152667470641644773611607061622753
627076271

P: ρ-aлгоритм Полларда факторизации чисел

Используя ρ-aлгоритм Полларда для поиска делителей и тест простоты Миллера — Рабина, напишите функцию factor(n), возвращающую список простых делителей числа (не забудьте, что бывают чётные числа). Выведите этот список при помощи функции print, предварительно его отсортировав.

132
[2, 2, 3, 11]
597131754515728882877009356793407519
[753702137, 873511201, 877672009, 1033402943]

Q: Целочисленный корень

Напишите функцию isqrt(n), возвращающую целочисленный корень из n, то есть наибольшее натуральное число, квадрат которого не превышает n. В числе может быть до 100000 десятичных знаков.

В поиске алгоритма поможет Вавилон и последовательность \(x_{i+1} = (x_{i} + n / x_{i}) / 2\). Нужно разобраться, почему она работает, и как ей эффективно воспользоваться для извлечения целочисленного квадратного корня.

16
4
35
5
98269816438745095196487194932272150644479
313480169131549843236

R: Метод Ферма поиска делителей

Метод Ферма позволяет быстро найти делитель нечётного числа \(n\), наиболее близкий к \(\sqrt{n}\). Если таких делителей нет (например, в случае произведения маленького простого и очень большого простого числа), то алгоритм работает ещё хуже, чем наивный перебор. Однако в криптографических алгоритмах часто используются составные числа вида \(pq\), и если \(p\) и \(q\) окажутся близки друг к другу, то метод Ферма позволит найти делитель быстро.

Идея алгоритма крайне проста: если \(n=ab\), то для \(x = (a+b)/2 \) и \(y=(a-b)/2\) выполнено равенство \(n = x^2 - y^2 = (x - y) (x + y)\). Таким образом, если мы представим \(n\) в виде разности квадратов, то найдём нетривиальный делитель.

Дальнейшие подробности алгоритма придумайте сами, целочисленный квадратный корень поможет.

Реализуйте метод Ферма для поиска делителей числа в виде функции fermat_divisor(n), принимающей на вход составное нечётное число и возвращающей любой его нетривиальный делитель.

9
3
35
5
1152996944542614893
1073761099