Rsa — криптографическая система, где важную роль играют числа вида n = pq, где p и q —
различные простые числа. число n называют модулем rsa и используют для дальнейших вычислений.
стойкость rsa основана на том факте, что для известного числа n не известно достаточно
быстрого алгоритма разложения n на множители для достаточно длинных чисел n (от 1024 бит и
больше). при этом, рекомендуется выбирать p и q большими случайными простыми числами примерно
одинаковой длины. генерация таких n — процесс, требующий аккуратности и понимания
происходящего. существует большое количество атак на ключи rsa, которые были сгенерированы
ненадлежащим образом. знание других деталей реализации rsa для этой не понадобится.
прочитав, что в rsa используют близкие простые числа, карл реализовал свой алгоритм генерации: 1. сгенерировать случайное простое число p1, состоящее из b бит.
2. начиная с p1 + 1, перебрать все числа подряд по возрастанию, пока не встретим следующее
простое число p2.
3. выдать n = p1p2.
поскольку выбирается случайное простое число p1, а в среднем расстояние между соседними
простыми числами невелико, этот алгоритм достаточно быстро найдет следующее простое число p2.
друг карла пьер обнаружил, что числа, которые выдает алгоритм карла, можно быстро разложить
на делители. поэтому пьер предложил брать не два простых числа, а четыре! независимо от p1 мы
также выберем случайное b-битное простое число q1 и следующее за ним простое число q2 и возьмем
n = p1p2q1q2. однако такой генерации тоже оказался уязвим: число n возможно разложить
на множители.
вам дано число n, сгенерированное либо изначальным методом карла с 2 простыми множителями,
либо с обновленным методом пьера с 4 простыми множителями. разложите его на простые
множители.
формат входных данных
в первой строке заданы два числа b и k (4< =b< =60, k = 2 или k = 4). в следующей строке
содержится число n в шестнадцатеричной системе счисления, от старших разрядов к младшим, без
ведущих нулей.
гарантируется, что n является произведением ровно k простых множителей, сгенерированных
случайно одним из двух методов, описанных в условии. каждый из этих множителей состоит ровно
из b бит в двоичной системе счисления, все множители различны.
формат выходных данных
выведите k простых множителей n в шестнадцатеричной записи без ведущих нулей, по одному
в каждой строке.

КэтЗед    3   14.12.2019 17:49    1