تقسیم رمز با استفاده از قضیه باقی‌مانده چینی کیست؟ توضیح بده.
تقسیم راز به معنای برگرداندن راز با استفاده از یک سری سهم، به طوری که هر سهم یک سری اطلاعات از راز دارد. در این صفحه به تقسیم راز با استفاده از قضیه باقیمانده چینی می‌پردازیم.تقسیم راز انواع مختلفی دارد یکی از پایه‌ای‌ترین نوع‌ها طرح‌های می‌باشد که در آن به ازای یک formula_1 برای دستیابی به راز حداقل به formula_1 سهم نیاز داریم و اگر formula_1 سهم داشته باشیم حتماً می‌توانیم به راز دست پیدا کنیم، روش تقسیم رمز با استفاده از قضیه باقیمانده چینی نیز یکی از روش‌های طرح آستانه‌ای می‌باشد.شرح.فرض کنید راز مورد نظر formula_4باشد، با توجه به قضیه باقیمانده چینی اگر برای یک formula_1تایی formula_6که هردوتایی از آن‌ها نسبت به هم اول هستند و formula_7 باقیمانده formula_4بر formula_9ها را بدانیم، formula_4یکتا بدست می‌آید و اگر formula_11حداقل دو جواب برای formula_4طبق قضیه باقیمانده چینی وجود دارد. این گزاره ایده ای برای انتخاب کردن سهم‌ها می‌دهد.اگر formula_13 عدد مثبت انتخاب کنیم که دو به دو نسبت به هم اول باشند مثل formula_14 و سهم‌ها باقیمانده formula_4 بر formula_9ها باشند، برای اینکه با استفاده از هر formula_1 تا سهم بتوان formula_4 را پیدا کرد و با کمتر از formula_1 سهم نتوان formula_4را پیدا کرد باید شرط روبرو برقرار باشد: formula_21 (چون formula_22 بین همه زیرمجموعه‌های حداقل formula_1 عضوی کمترین ضرب است و formula_24 بین همه زیرمجموعه‌های کمتر از formula_1 عضوی بیشترین ضرب است) در این صورت طبق چیزی که قبلاً گفتیم چون ضرب formula_9‌های هر formula_27سهم کمتر از formula_4است پس نمی‌توان به صورت یکتا به formula_4دست یافت و از طرفی چون ضرب هر formula_1سهم از formula_4بیشتر است می‌توان formula_4را به صورت یکتا بدست آورد.روش مینوت (Mignotte).دنباله formula_33شامل formula_13عدد مثبت است مثل formula_14 که دو به دو نسبت به هم اول هستند و formula_36.به ازای یک formula_4 رندوم که شرط formula_21 را دارا می‌باشد سهم‌ها به این صورت تعریف می‌شوند : formula_39 (formula_40 برابر باقیمانده تقسیم formula_41 بر formula_42 است)و طبق قضیه باقیمانده چینی برای به دست آوردن formula_4 از formula_1 سهم باید معادله زیر را حل کنیم:formula_45روش ازموث-بلوم (Asmuth-Bloom).دو عدد طبیعی formula_13 و formula_1 را در نظر بگیرید که دارای شرط روبرو باشند formula_48 و یک مجموعه از اعداد طبیعی مثل formula_49 که دو به دو نسبت به هم اول هستند و شرط formula_50 برقرار است، فرض کنید formula_4 یک عدد تصادفی باشد که در شرط formula_52 صدق می‌کند، حال برای مشخص کردن سهم‌ها یک عدد تصادفی formula_53انتخاب می‌کنیم که در شرط formula_54صدق کند، سپس سهم‌ها را به این صورت تعریف می‌کنیم : formula_55در این صورت به ازای هر formula_1 سهم چون formula_54 طبق قضیه باقیمانده چینی می‌توان formula_58 را به صورت یکتا پیدا کرد پس می‌توان با باقیمانده گرفتن formula_58 بر formula_60 می‌توان formula_4 را پیدا کرد.برتری این روش نسبت به روش قبل این است که در روش قبلی با داشتن formula_27 سهم اطلاعاتی راجع به formula_4 داشتیم چون اگر ضرب formula_9های متناظر این formula_27 سهم برابر formula_66 باشد با استفاده از قضیه باقیمانده چینی باقیمانده formula_4 را بر formula_66داشتیم، در صورتی که در روش ازموث-بلوم با داشتن همین formula_27 سهم باقیمانده formula_58 را بر formula_66 داریم و چون formula_53 را یک عدد تصادفی انتخاب کردیم در واقع اطلاعاتی دربارهٔ خود formula_4 نداریم.مثال.در ادامه مثالی از روش ازموث-بلوم را بررسی می‌کنیم:formula_74در مثال بالا formula_9ها دارای شرایط گفته شده می‌باشند چون هم دو به دو نسبت به هم اول هستند (چون همه اعداد اول هستند و هر دو عدد اولی نیز نسبت به هم اول هستند) و در شرط formula_50 نیز برقرار هستند (formula_77).فرض کنید formula_78 باشد و عدد تصادفی‌ای که انتخاب کردیم formula_79باشد در این صورت در شرط formula_54 صدق می‌کند (چون formula_81).در این صورت سهم‌ها برابر formula_82 می‌باشند. حال با استفاده از باقیمانده چینی به ازای هر سه سهم می‌توان به عدد formula_4 رسید.