چگونه منحنی های ریاضی ارتباطات پیشرفته را فعال می کنند

با توجه به مجموعه ای از نقاط در فضا، آیا می توانید نوع خاصی از منحنی را پیدا کنید که از همه آنها عبور کند؟ این سوال - نسخه ای از آنچه که مسئله درون یابی نامیده می شود - ریاضیدانان را از دوران باستان مورد توجه قرار داده است. در اوایل امسال، ریاضیدانان اریک لارسون و ایزابل وگت آن را به طور کامل حل کرد.

اما در حالی که این کار هیجان زیادی را در بین ریاضیدانان محض ایجاد کرده است، درون یابی پیامدهای عملی دارد که بسیار فراتر از قلمرو هندسه است. درون یابی برای ذخیره و برقراری ارتباط داده های الکترونیکی، ساخت طرح های رمزنگاری و موارد دیگر، مرکزی است. به همین دلیل است که می توانید یک سی دی را خراش دهید و همچنان موسیقی را بشنوید، یا یک کد QR را کثیف کنید و همچنان آن را اسکن کنید. به همین دلیل است که مأموریت‌های فضایی مانند برنامه وویجر می‌توانند تصاویر دیجیتالی واضحی را به زمین ارسال کنند. به همین دلیل است که دسته ای از رایانه ها می توانند محاسبات پیچیده ای را انجام دهند حتی اگر یکی از آن رایانه ها خراب شود.

این برنامه‌ها همگی بر استفاده بسیار زیبا و مفهومی ساده از درون‌یابی متکی هستند: به اصطلاح کدهای Reed-Solomon و کدهایی که بر روی آنها ساخته می‌شوند.

نقطه به نقطه

فرض کنید می‌خواهید پیامی متشکل از دو عدد ارسال کنید: 2 و 7. ممکن است برخی از داده‌هایی که ارسال می‌کنید گم شوند یا خراب شوند - برای مثال، عدد 2 ممکن است به 2- تبدیل شود. بنابراین به‌جای ارسال ساده داده‌ها، می‌توانید اطلاعات بیشتری را برای کمک به گیرنده در شناسایی و رفع خطاهای احتمالی اضافه کنید. این همان چیزی است که به آن کد تصحیح خطا می گویند.

ساده ترین مثال از چنین کدی شامل ارسال چندین بار یک پیام است. برای اینکه به گیرنده اجازه دهید تشخیص دهد که آیا خطایی رخ داده است یا خیر، یک پیام را دوبار ارسال کنید: 2، 7، 2، 7. اگر اعداد در موقعیت های مربوطه مطابقت ندارند (مثلاً اگر انتقال به جای آن 2، 7، −2 باشد، 7)، گیرنده متوجه خواهد شد که یکی از آنها اشتباه است - اما نه اینکه کدام یک. برای اینکه آنها متوجه شوند و خطا را تصحیح کنند، یک پیام را سه بار ارسال کنید: 2، 7، 2، 7، 2، 7. گیرنده به سادگی باید رای اکثریت را بگیرد تا پیام مورد نظر شما را بفهمد.

اما این وسیله برای تصحیح خطاها بسیار ناکارآمد است. در اینجا یک رویکرد هوشمندتر وجود دارد: پیام را به عنوان یک منحنی رمزگذاری کنید و اطلاعات کافی را ارسال کنید تا به گیرنده اجازه دهد آن منحنی را بازسازی کند.

در مورد ساده ما برای انتقال 2 و 7، منحنی خط خواهد بود y = 2x + 7. این منحنی را در دو مقدار از پیش تعیین شده ارزیابی کنید x، و نتیجه را منتقل کنید y-ارزش های. گیرنده اکنون دو نقطه دارد، و چون مسئله درون یابی به ما می گوید که دو نقطه یک خط منحصر به فرد را تعیین می کنند، گیرنده به سادگی باید خطی را که از نقاط دریافتی خود می گذرد، پیدا کند. ضرایب خط پیام مورد نظر را نشان می دهد.

برای جلوگیری از خطا، یک بار دیگر اطلاعات اضافی را اضافه می کنید. در اینجا، شما ارسال کنید y- مقداری که با دیگر از پیش تعیین شده مطابقت دارد x-هماهنگ كردن. اگر سه نقطه روی یک خط قرار نگیرند، خطا وجود دارد. و برای اینکه بفهمید خطا کجاست، فقط یک مقدار دیگر ارسال می‌کنید - به این معنی که در مجموع چهار عدد ارسال کرده‌اید، نه شش عددی که در روش قبلی لازم بود.

مزیت با اندازه پیام افزایش می یابد. فرض کنید می خواهید پیام طولانی تری ارسال کنید - 1,000 شماره. کد کمتر کارآمد نیاز به ارسال 2,000 عدد برای شناسایی خطا و 3,000 عدد برای تصحیح آن دارد. اما اگر از کدی استفاده کنید که شامل درون یابی یک چند جمله ای در نقاط داده شده است، برای یافتن خطا فقط به 1,001 عدد و برای تصحیح آن به عدد 1,002 نیاز دارید. (می توانید برای شناسایی و تصحیح خطاهای احتمالی امتیاز بیشتری اضافه کنید.) با افزایش طول پیام شما، تفاوت کارایی بین این دو کد آشکارتر می شود.

کد کارآمدتر، کد Reed-Solomon نامیده می شود. از زمان معرفی آن در سال 1960، ریاضیدانان به پیشرفت های بیشتری دست یافته اند و الگوریتم هایی را توسعه داده اند که می توانند خطاهای بیشتری را با کارایی بیشتر تصحیح کنند. گفت: «بسیار ظریف، تمیز، بتونی است Swastik Kopparty، ریاضیدان و دانشمند کامپیوتر در دانشگاه تورنتو. "این را می توان به یک سال دوم کارشناسی در نیم ساعت آموزش داد."

کدهای Reed-Solomon به ویژه برای ذخیره و انتقال اطلاعات به صورت الکترونیکی مفید بوده اند. اما همین مفهوم در رمزنگاری و محاسبات توزیع شده نیز ضروری بوده است.

اشتراک‌گذاری راز را در نظر بگیرید: فرض کنید می‌خواهید یک راز را بین چندین طرف توزیع کنید به طوری که هیچ فردی نتواند به کل راز دسترسی داشته باشد، اما با هم می‌توانند. (مثلاً یک کلید رمزگذاری یا یک کد پرتاب موشک را تصور کنید.) شما اعداد را در یک چند جمله ای رمزگذاری می کنید، آن چند جمله ای را در مجموعه ای از نقاط از پیش تعیین شده ارزیابی می کنید و هر یک از نتایج را بین افراد متفاوتی توزیع می کنید.

اخیراً، کدهای Reed-Solomon در زمینه هایی مانند محاسبات ابری و فناوری بلاک چین به کار گرفته شده اند. فرض کنید باید محاسباتی را اجرا کنید که برای لپ‌تاپ شما بسیار پیچیده است، بنابراین یک خوشه محاسباتی بزرگ آن را اجرا می‌کند - اما اکنون باید تأیید کنید که محاسباتی که دریافت می‌کنید درست است. کدهای Reed-Solomon به شما این امکان را می دهند که اطلاعات بیشتری را درخواست کنید که اگر خوشه محاسبات را به درستی انجام نداده باشد، احتمالاً قادر به تولید آنها نخواهد بود. گفت: "این کار جادویی است." جید ناردییک محقق در موسسه ریاضیات رن در فرانسه. این فرآیند واقعاً فوق‌العاده است، و روشی که بر [این کدها] تکیه می‌کند، ذهن من را متحیر می‌کند.»

اما کدهای Reed-Solomon یک محدودیت مهم نیز دارند. آنها به گونه ای ساخته شده اند که شما فقط می توانید چند جمله ای خود را در یک مجموعه مقادیر ثابت (و معمولاً نسبتاً کوچک) ارزیابی کنید. یعنی شما محدود به استفاده از مجموعه اعداد خاصی برای رمزگذاری پیام خود هستید. اندازه آن مجموعه یا الفبا به نوبه خود طول پیام هایی را که می توانید ارسال کنید محدود می کند - و هر چه سعی کنید الفبای خود را بزرگتر بسازید، به قدرت محاسباتی بیشتری برای رمزگشایی آن پیام ها نیاز خواهید داشت.

و بنابراین ریاضیدانان به دنبال یک کد بهینه تر بودند.

کدهای آینده

یک کد عمومی تر و قوی تر به شما امکان می دهد پیام های طولانی تری را بدون نیاز به افزایش اندازه الفبای خود ذخیره یا ارسال کنید. برای انجام این کار، ریاضیدانان کدهایی ابداع کردند که شامل درون یابی یک تابع - که در یک فضای خاص مرتبط با یک منحنی پیچیده تر زندگی می کند - از طریق نقاط داده شده روی آن منحنی است. کوپپارتی گفت، این کدهای به اصطلاح هندسه جبری "از هیچ جا بیرون آمدند، و بهتر از هر کد دیگری هستند که ما می دانیم چگونه بسازیم [با الفبای کوچکتر]". "این همه چیز را شکست می دهد. این یک شوک واقعی بود.»

فقط یک مشکل وجود دارد در عمل، پیاده‌سازی کد رید سولومون بسیار آسان‌تر از پیاده‌سازی کد هندسه جبری است. این رمزنگار گفت: "این پیشرفته ترین است، اما هنوز در دست بررسی است تا واقعاً به چیزی عملی تبدیل شود." سیمون آبلارد. "این شامل ریاضیات کاملاً انتزاعی است و کار با این کدها در رایانه دشوار است."

در حال حاضر، این نگران کننده نیست: در برنامه های کاربردی دنیای واقعی، کدهای Reed-Solomon و اشکال مربوط به تصحیح خطا کافی است. اما ممکن است همیشه اینطور نباشد. برای مثال، اگر کامپیوترهای کوانتومی قدرتمندی در آینده در دسترس قرار گیرند، قادر خواهند بود شکستن پروتکل های رمزنگاری امروزی. در نتیجه، محققان به دنبال طرح هایی هستند که می توانند در برابر حملات کوانتومی مقاومت کنند. یکی از رقبای برتر برای چنین طرح هایی به چیزی قوی تر از کدهای Reed-Solomon نیاز دارد. نسخه های خاصی از کدهای هندسه جبری ممکن است کار کنند. محققان دیگر درباره نقشی که کدهای هندسه جبری ممکن است در رایانش ابری ایفا کنند، امیدوار هستند.

اما حتی در غیاب چنین کاربردهای بالقوه ای، "در تاریخ ریاضیات، گاهی اوقات چیزهای جدیدی کشف می کنید که امروزه واقعاً کاربردی ندارند." النا براردینیمحققی در دانشگاه فناوری آیندهوون در هلند که روی کدهای هندسه جبری کار می کند. «اما بعد از 50 سال، متوجه می‌شوید که ممکن است برای چیزی کاملاً غیرمنتظره مفید باشد» - درست مانند خود مشکل باستانی درون‌یابی.