Проблема Фробениуса. 
Криптографические методы защиты информации. 
Часть 1. Математические аспекты

Пусть А = {a_if…, a_k} — возрастающая последовательность натуральных чисел, k > 1, (А) — аддитивная полугруппа, порожденная множеством А. Полугруппа (А) состоит из всех линейных комбинаций чисел a_v …, a_k с целыми неотрицательными коэффициентами.

Множество А называется примитивным, если НОД (я _1?a_k) = 1.

Теорема 2.21. Если множество А примитивное, то найдется s е N такое, что t е (А) при любом натуральном t > s.

4 Для примитивного множества А по теореме 2.8 найдутся целые числа с_Ху с_т такие, что с_ха_х + … + с_та_т = 1. В левой части данного выражения обозначим р и -q суммы положительных и отрицательных слагаемых. Тогда р, q е (А), и р — q = 1. Любое число t > 0 разделим с остатком на а_х: t = a_xh + г, где h > 0 и 0 < г < а_х. Тогда (а_х — 1 )q + t = a_xh + (aj — 1 — r)q + + rp e (А). Значит, все натуральные числа t > (а_х — 1 )q_y принадлежат (А).? Число Фробениуса g (a_{y …, a_k) определено для любого примитивного множества {а_Л,…, a_k) при а_х> 1 как наибольшее натуральное число t ? (Л), т. е. число, не представимое в виде линейной комбинации чисел а_{у …, a_k с неотрицательными целыми коэффициентами. При а_х = 1 полагаютg (l, а₂, а_к) = -1.

Обозначим С (А) множество всех чисел t и определим число Фробениуса: g (A) = g (a_{} a_k) = тахС (Л). Определение g (a_x, …, a_k) известно как диофантова проблема Фробениуса (ПФ). Определение множества С (А) называется расширенной проблемой Фробениуса (РПФ).

Опубликован обзор результатов^[1] до 2005 г. ПФ и РПФ для k = 2 решены^[2] еще в 1884 г.:

Алгоритм решения РПФ при k = 3 получен в [11], оценена сложность алгоритма. Отметим, что активно изучались свойства множества С (А), первые результаты получены Сильвестром.

Формула решения ПФ при k > 2 не была получена, уже при k = 3 доказано^[3], что не найдется конечного числа полиномов, выражающих в общем случае число g (a_v а_ъ ci%) с помощью разбиения области определения. Точные формулы имеются лишь для частных случаев.

Более продуктивным был алгоритмический подход к ПФ. Представлен [21] теоретико-графовый алгоритм определения g (a_{y …, a_k) со сложностью 0(a_x(k + log<2j)), ПФ сведена к поиску определенного вида наибольшего кратчайшего пути в орграфе с а_х вершинами и с ka_x дугами, где из каждой вершины исходит k дуг весов а_х, …, соответственно. В [16] оценка сложности ПФ снижена до величины 0(ka_x). В [14] для РПФ и ПФ предложена редукция множества А к собственному подмножеству, снижающая сложность задачи в ряде случаев.

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

а также оценка Брауэра¹ (здесь dj = НОД («₁,af), i = 2,/

• [1] AlfonsinJ. R. The Diophantine Frobenius Problem. Oxford University Press, 2005.
• [2] SylvesterJ.J. «Problem 7382», Educational Times 37 (1884), 26; reprinted in «Mathematicalquestions with their solution», with additional papers and solutions, Educational Times 41 (1884).P.21.
• [3] Curtis F. On formulas for the Frobenius number of a numerical semigroup, Math. Scand.67 (1990). P. 190−192.