הצפנת תרמיל גב – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
שורה 34:
===סדרה סוּפֶּר-עולה===
בעיקרון אם <math>n</math> גדול הפתרון המתואר אינו יעיל ולכן הבעיה הכללית מוגדרת קשה, אולם אינה מתאימה לקריפטוגרפיה כיוון שלא קיימת דלת מלכודת, אותו מידע סודי שהופך את פתרון הבעיה לקל מאוד למי שמחזיק בו ואילו עבור כל האחרים שאינם יודעים מהו הבעיה נותרת קשה. דרך אחת להכניס דלת מלכודת היא להשתמש בבעיית תרמיל עם תכונה מיוחדת שפתרונה קל. הרעיוןן של מרקל והלמן היה להשתמש בתרמיל המורכב מסדרה
:<math>r_{i+1}\ge 2r_i</math> עבור כל <math>1\le i\le n-1</math>.
היא נקראת סופר-עולה (superincreasing) כיוון שעבור כל <math>k</math> מתקיים <math>r_{k+1}\ge 2r_k</math> או <math>r_k+r_k>r_k+(r_{k-1}+\cdots r_2+r_1)</math>. במקרה זה פתרון בעיית התרמיל קל מאוד לפי האלגוריתם הבא: מבצעים לולאה שמתחילה באיבר האחרון (<math>M_n</math>) כלפי מטה עד האיבר הראשון (<math>M_1</math>) ובודקים עבור כל <math>M_i</math>: אם <math>S\ge M_i</math> מציבים <math>x_i=1</math> ומחסרים <math>S=S-M_i</math> אחרת מציבים <math>x_i=0</math> וממשיכים עד ש-<math>S=0</math> (בהנחה שפתרון קיים).
| |||