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

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

Профилирование программы в 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']

>>> from cProfile import Profile
>>> pr = Profile()
>>> dir(pr)
['__class__',
 '__delattr__',
 '__dict__',
 '__doc__',
 '__eq__',
 '__format__',
 '__ge__',
 '__getattribute__',
 '__gt__',
 '__hash__',
 '__init__',
 '__le__',
 '__lt__',
 '__module__',
 '__ne__',
 '__new__',
 '__reduce__',
 '__reduce_ex__',
 '__repr__',
 '__setattr__',
 '__sizeof__',
 '__str__',
 '__subclasshook__',
 '__weakref__',
 'clear',
 'create_stats',
 'disable',
 'dump_stats',
 'enable',
 'getstats',
 'print_stats',
 'run',
 'runcall',
 'runctx',
 'snapshot_stats']
>>> 

01: Тест Ферма

Вам уже известна малая теорема Ферма: если число \(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

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

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

5

Prime
4

5555

Composite
8

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

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

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

Числом Кармайкла называется всякое составное число \(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

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

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

12345 67890

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

Тест простоты, основанный на тесте Ферма, заключается в следующем. Пусть мы хотим проверить простоту числа \(n\). Зафиксируем для себя натуральное число \(m\), выберем \(m\) случайных чисел от \(2\) до \(n-1\), и для каждого проведём тест Ферма из задачи 01. Если хотя бы одно число не прошло тест, то число \(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), проверяющую простоту числа при помощи 30 раундов теста Ферма. Функция должна возвращать False, если число \(n\) составное, и True, если число \(n\) скорее всего простое. Число \(n\) может содержать до 400 десятичных знаков.

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

170141183460469231731687303715884105721

False

170141183460469231731687303715884105727

True

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

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

Пусть \(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

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

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

65537

Prime
65534

65533

Composite
4

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

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

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

170141183460469231731687303715884105721

False

170141183460469231731687303715884105727

True

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

1000000000000000000

1000000000000000003

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

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

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

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

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

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

Подробности будут в ближайшее время.

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

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

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

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

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

1

3

10

618970019642690137449562111

15: ρ-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}\). Если нарисовать картинку, то получится как раз греческая буква «ро».

Теперь воспользуемся трюком от Роберта Флойда для экономного поиска этого самого цикла из буквы «ро». Для этого заметим, что найдется такое число \(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

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

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

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

132

[2, 2, 3, 11]

597131754515728882877009356793407519

[753702137, 873511201, 877672009, 1033402943]

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

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

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

16

4

35

5

98269816438745095196487194932272150644479

313480169131549843236

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

Метод Ферма позволяет быстро найти делитель нечётного числа \(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

19: Метод Ферма факторизации чисел

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

132

[2, 2, 3, 11]

1152996944542614893

[1073761099, 1073792807]