Given a sum and a set of weights, find the weights which were used to generate the sum. The values of the weights are then encrypted in the sum. This system relies on the existence of a class of knapsack problems which can be solved trivially (those in which the weights are separated such that they can be "peeled off" one at a time using a greedy-like algorithm), and transformations which convert the trivial problem to a difficult one and vice versa. Modular multiplication is used as the trapdoor one-way function. The simple knapsack system was broken by Shamir in 1982, the Graham-Shamir system by Adleman, and the iterated knapsack by Ernie Brickell in 1984.

REFERENCES:

Coppersmith, D. "Knapsack Used in Factoring." §4.6 in Open Problems in Communication and Computation (Ed. T. M. Cover and B. Gopinath). New York: Springer-Verlag, pp. 117-119, 1987.

Lichtblau, D. "Solving Knapsack and Related Problems." Unpublished manuscript.

Honsberger, R. Mathematical Gems III. Washington, DC: Math. Assoc. Amer., pp. 163-166, 1985.

اخر الاخبار

اخبار العتبة العباسية المقدسة

مجموعة العميد التربوية تعقد اجتماعًا لمناقشة الاستعدادات الخاصة بالموسم التدريبي الصيفي

قسم الإعلام ينظم ورشة تدريبية حول تطبيق (إعلامي) لعدد من منتسبي قسم حفظ النظام

قسم الشؤون الخدمية ينفذ حملة لتنظيف الشوارع المحيطة بصحن مرقد أبي الفضل العباس (عليه السلام)

وفد العتبة العباسية المقدسة يزور شعبة الإعداد البدني للاطّلاع على برنامج تأهيل المنتسبين الجدد

المزيد

الآخبار الصحية

ماذا يحدث إذا تناولنا الطعام مرة واحدة فقط في اليوم

اكتشاف عوامل خطر غير متوقعة لمرض الكبد الدهني

فيروس هانتا والسفينة الموبوءة.. تحديث من الصحة العالمية

طبيب يحسم الجدل السجائر الإلكترونية وعلاقتها بالسرطان

المزيد

الآخبار التكنلوجية

لأول مرة في الولايات المتحدة.. تشغيل مفاعل مصغر نووي يغذي الذكاء الاصطناعي بالطاقة

الكشف عن تفاصيل أول عملية ناجحة لاستعادة انتاج الحيوانات المنوية

أطلس يكشف خفايا الجسم البشري بدقة أرفع بـ50 مرة من شعر الإنسان

المتحف المصري الكبير يتحول إلى "أيقونة خضراء" بدعم ياباني

المزيد