2-محاسبات مدولار

کلاس های همخوانی[ ویرایش ]

مانند هر رابطه تطابقی، مدول همخوانی n یک رابطه هم ارزی است و کلاس هم ارزی عدد صحیح a که با a n نشان داده می شود مجموعه {... , a − 2 n , a − n , a , a + n است. a + 2 n , ... }. این مجموعه که از تمام اعداد صحیح متجانس با یک مدول n تشکیل شده است، کلاس همخوانی ، کلاس باقیمانده یا به سادگی باقی مانده نامیده می شود.از عدد صحیح a پیمانه n . هنگامی که مدول n از متن شناخته می شود، آن باقیمانده نیز ممکن است [ a ] نشان داده شود .

سیستم های باقی مانده [ ویرایش ]

هر کلاس باقیمانده مدول n ممکن است توسط هر یک از اعضای آن نمایش داده شود، اگرچه ما معمولاً هر کلاس باقیمانده را با کوچکترین عدد صحیح غیر منفی که به آن کلاس تعلق دارد نشان می دهیم [2] (زیرا این باقیمانده مناسبی است که از تقسیم حاصل می شود). هر دو عضو از کلاس های باقیمانده مختلف مدول n، مدول n ناهمخوان هستند . علاوه بر این، هر عدد صحیح متعلق به یک و تنها یک کلاس باقیمانده پیمانه n است. [3]

مجموعه اعداد صحیح {0, 1, 2, ..., n − 1 } را کمترین سیستم باقیمانده پیمانه n می نامند . به هر مجموعه ای از n عدد صحیح که هیچ دوتای آن ها مدول n متجانس نیستند ، سیستم باقیمانده کامل مدول n نامیده می شود .

سیستم کمترین باقیمانده یک سیستم باقیمانده کامل است و یک سیستم باقیمانده کامل به سادگی مجموعه‌ای است که دقیقاً شامل یک نماینده از هر کلاس باقیمانده مدول n است. [4] به عنوان مثال. کمترین مقدار باقیمانده سیستم مدول 4 {0، 1، 2، 3} است. برخی دیگر از سیستم های باقیمانده کامل مدول 4 عبارتند از:

{1، 2، 3، 4}
{13، 14، 15، 16}
{−2، −1، 0، 1}
{−13، 4، 17، 18}
{−5، 0، 6، 21}
{27، 32، 37، 42}

برخی از مجموعه هایی که مدول 4 سیستم باقیمانده کامل نیستند عبارتند از:

{−5، 0، 6، 22}، زیرا 6 با 22 مدول 4 همخوانی دارد.
{5، 15}، زیرا یک مدول سیستم باقیمانده کامل 4 باید دقیقاً 4 کلاس باقیمانده ناهمخوان داشته باشد.

سیستم های باقیمانده کاهش یافته [ ویرایش ]

مقاله اصلی: سیستم باقیمانده کاهش یافته

با توجه به تابع اویلر φ( n ) , هر مجموعه ای از اعداد صحیح φ( n ) که نسبتاً اول با n هستند و تحت مدول n متقابلاً ناهمخوان هستند، مدول سیستم باقیمانده کاهش یافته n نامیده می شود . [5] مجموعه {5،15} از بالا، برای مثال، نمونه‌ای از مدول 4 سیستم باقیمانده کاهش‌یافته است.

مدول n اعداد صحیح [ ویرایش ]

مجموعه تمام طبقات همخوانی اعداد صحیح برای مدول n حلقه اعداد صحیح مدول n نامیده می شود ، [6] و نشان داده می شود. ${\textstyle \mathbb {Z} /n\mathbb {Z} }$ ، $\mathbb {Z} /n$ ، یا $\mathbb {Z} _{n}$ . [7] نماد $\mathbb {Z} _{n}$ با این حال، توصیه نمی شود زیرا می توان آن را با مجموعه اعداد صحیح n- adic اشتباه گرفت . حلقه _ $\mathbb {Z} /n\mathbb {Z}$ برای شاخه های مختلف ریاضیات اساسی است (به § برنامه های کاربردی زیر مراجعه کنید).

مجموعه برای n > 0 به صورت زیر تعریف می شود:

$\mathbb {Z} /n\mathbb {Z} =\left\{{\overline {a}}_{n}\mid a\in \mathbb {Z} \right\}=\left\{ {\overline {0}}_{n}،{\overline {1}}_{n}،{\overline {2}}_{n}،\ldots،{\overline {n{-}1}} _{n}\right\}.$

(وقتی n = 0 ، $\mathbb {Z} /n\mathbb {Z}$ یک مجموعه خالی نیست . بلکه ایزومورف به است $\mathbb {Z}$ ، زیرا 0 = { a }. )

جمع، تفریق و ضرب را بر روی تعریف می کنیم $\mathbb {Z} /n\mathbb {Z}$ با قوانین زیر:

${\overline {a}}_{n}+{\overline {b}}_{n}={\overline {(a+b)}}_{n}$
${\overline {a}}_{n}-{\overline {b}}_{n}={\overline {(ab)}}_{n}$
${\overline {a}}_{n}{\overline {b}}_{n}={\overline {(ab)}}_{n}.$

تأیید اینکه این یک تعریف مناسب است، از ویژگی های ارائه شده قبل استفاده می کند.

به این ترتیب، $\mathbb {Z} /n\mathbb {Z}$ حلقه جابه جایی می شود . مثلا در رینگ $\mathbb {Z} /24\mathbb {Z}$ ، ما داریم

${\overline {12}}_{24}+{\overline {21}_{24}={\overline {33}}_{24}={\overline {9}}_{24}$

همانطور که در حساب برای ساعت 24 ساعته.

ما از علامت گذاری استفاده می کنیم $\mathbb {Z} /n\mathbb {Z}$ زیرا این حلقه ضریب است $\mathbb {Z}$ توسط ایده آل $n\mathbb {Z}$ ، مجموعه ای شامل تمام اعداد صحیح قابل تقسیم بر n ، که در آن $0\mathbb {Z}$ مجموعه تک تن {0 } است. بدین ترتیب $\mathbb {Z} /n\mathbb {Z}$ یک میدان است که $n\mathbb {Z}$ یک ایده آل حداکثر است (یعنی وقتی n اول باشد).

این نیز می تواند از گروه ساخته شود $\mathbb {Z}$ تحت عملیات اضافه به تنهایی. کلاس باقیمانده a n کوست گروه a در گروه ضریب است $\mathbb {Z} /n\mathbb {Z}$ ، یک گروه چرخه ای . [8]

به جای حذف حالت خاص n = 0 ، استفاده از آن مفیدتر است $\mathbb {Z} /0\mathbb {Z}$ (که همانطور که قبلا ذکر شد با حلقه هم شکل است $\mathbb {Z}$ از اعداد صحیح). در واقع، این گنجاندن هنگام بحث در مورد ویژگی یک حلقه مفید است .

حلقه اعداد صحیح مدول n یک میدان متناهی است اگر و فقط اگر n اول باشد (این تضمین می کند که هر عنصر غیر صفر دارای یک معکوس ضربی است ). اگر $n=p^{k}$ یک توان اول با k > 1 است، یک میدان محدود منحصر به فرد (تا هم ریختی) وجود دارد. $\mathrm {GF} (n)=\mathbb {F} _{n}$ با n عنصر، اما اینطور نیست $\mathbb {Z} /n\mathbb {Z}$ ، که نمی تواند یک فیلد باشد زیرا دارای مقسوم علیه صفر است .

زیر گروه ضربی اعداد صحیح پیمانه n با نشان داده می شود $(\mathbb {Z} /n\mathbb {Z} )^{\times }$ . این شامل ${\overline {a}}_{n}$ (که در آن a همزمان با n است ) ، که دقیقاً کلاس هایی هستند که دارای یک معکوس ضربی هستند. این یک گروه جابجایی تحت ضرب، با ترتیب تشکیل می دهد $\varphi (n)$ .

بسط اعداد واقعی [ ویرایش ]

همچنین ببینید: عملیات ماژول

این بخش خالی است شما می توانید با اضافه کردن به آن کمک کنید . ( ژوئیه 2022 )

برنامه های کاربردی [ ویرایش ]

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

یک کاربرد بسیار عملی، محاسبه جمع‌های چک در شناسه‌های شماره سریال است. به عنوان مثال، شماره کتاب استاندارد بین‌المللی (ISBN) از مدول 11 (برای شابک 10 رقمی) یا مدول 10 (برای ISBN 13 رقمی) برای تشخیص خطا استفاده می‌کند. به همین ترتیب، برای مثال، شماره حساب های بانکی بین المللی (IBAN) از محاسبات مدول 97 برای تشخیص خطاهای ورودی کاربر در شماره حساب های بانکی استفاده می کند. در شیمی، آخرین رقم شماره ثبت CAS (یک شماره شناسایی منحصر به فرد برای هر ترکیب شیمیایی) یک رقم چک است.که با گرفتن آخرین رقم از دو قسمت اول شماره رجیستری CAS برابر 1، رقم قبلی ضربدر 2، رقم قبلی ضربدر 3 و غیره، جمع کردن همه اینها و محاسبه مجموع مدول 10 محاسبه می شود.

در رمزنگاری، محاسبات مدولار مستقیماً زیربنای سیستم‌های کلید عمومی مانند RSA و Diffie-Hellman است و زمینه‌های محدودی را فراهم می‌کند که زیربنای منحنی‌های بیضوی قرار دارند و در انواع الگوریتم‌های کلید متقارن از جمله استاندارد رمزگذاری پیشرفته ( AES)، الگوریتم رمزگذاری بین‌المللی داده استفاده می‌شود. IDEA)، و RC4 . RSA و Diffie-Hellman از توان مدولار استفاده می کنند.

در جبر کامپیوتری، معمولاً از محاسبات مدولار برای محدود کردن اندازه ضرایب صحیح در محاسبات و داده‌های میانی استفاده می‌شود. از آن در فاکتورسازی چند جمله ای استفاده می شود ، مسئله ای که همه الگوریتم های کارآمد شناخته شده برای آن از محاسبات مدولار استفاده می کنند. این توسط کارآمدترین پیاده سازی های چند جمله ای بزرگترین مقسوم علیه مشترک ، جبر خطی دقیق و الگوریتم های پایه گروبنر بر روی اعداد صحیح و اعداد گویا استفاده می شود. همانطور که در Fidonet در دهه 1980 ارسال شد و در Rosetta Code بایگانی شد ، از محاسبات مدولار برای رد فرضیه مجموع توان های اویلر در میکروکامپیوتر QL Sinclair استفاده شد. با استفاده از تنها یک چهارم دقت اعداد صحیح مورد استفاده توسط یک ابررایانه CDC 6600 برای رد آن دو دهه قبل از طریق جستجوی brute force . [9]

در علوم کامپیوتر، محاسبات مدولار اغلب در عملیات بیتی و سایر عملیات‌هایی که شامل ساختارهای داده چرخه‌ای با عرض ثابت هستند، به کار می‌رود . عملیات مدول ، همانطور که در بسیاری از زبان های برنامه نویسی و ماشین حساب ها پیاده سازی می شود ، یک کاربرد از محاسبات مدولار است که اغلب در این زمینه استفاده می شود. عملگر منطقی XOR 2 بیت، مدول 2 را جمع می کند.

در موسیقی، مدول حسابی 12 برای در نظر گرفتن سیستم خلق و خوی مساوی دوازده تنی ، که در آن اکتاو و هم ارزی هماهنگ رخ می دهد، استفاده می شود (یعنی زیر و بمی ها در نسبت 1:2 یا 2:1 معادل هستند، و C- شار برابر است. همان D- Flat در نظر گرفته می شود ).

روش بیرون ریختن نه ها ، بررسی سریع محاسبات حسابی اعشاری انجام شده با دست را ارائه می دهد. این بر اساس مدول حسابی مدولار 9 است، و به طور خاص بر روی خاصیت حیاتی که 10 ≡ 1 (mod 9) است.

مدول حسابی 7 در الگوریتم هایی استفاده می شود که روز هفته را برای یک تاریخ معین تعیین می کند. به طور خاص، تطابق زلر و الگوریتم روز قیامت به شدت از محاسبات مدولو-7 استفاده می کنند.

به طور کلی تر، حساب مدولار در رشته هایی مانند حقوق (مثلاً تقسیم بندی )، اقتصاد (مثلاً نظریه بازی ) و سایر حوزه های علوم اجتماعی کاربرد دارد، که در آن تقسیم و تخصیص متناسب منابع، بخش مرکزی تحلیل را ایفا می کند.

پیچیدگی محاسباتی [ ویرایش ]

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

برخی از عملیات، مانند یافتن یک لگاریتم گسسته یا یک تطابق درجه دوم ، به نظر می رسد به سختی فاکتورسازی اعداد صحیح هستند و بنابراین نقطه شروعی برای الگوریتم های رمزنگاری و رمزگذاری هستند. این مشکلات ممکن است NP-intermediate باشند.

حل یک سیستم معادلات حسابی مدولار غیر خطی NP-complete است. [10]

نمونه های پیاده سازی [ ویرایش ]

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

در زیر سه تابع C نسبتاً سریع وجود دارد، دو تابع برای انجام ضرب مدولار و یکی برای توان مدولار در اعداد صحیح بدون علامت بزرگتر از 63 بیت، بدون سرریز عملیات گذرا.

روشی الگوریتمی برای محاسبه $a\cdot b{\pmod {m}}$ : [11]

uint64_t mul_mod ( uint64_t a , uint64_t b , uint64_t m ) {       
    اگر ( ! (( a | b ) & ( 0xFFFFFFFFULL << 32 )) ) a * b % m ;             

    uint64_t d = 0 , mp2 = m >> 1 ;        
    int i ; 
    if ( a >= m ) a %= m ;      
    اگر ( b >= m ) b %= m ;      
    برای ( i = 0 ; i < 64 ; ++ i ) {        
        d = ( d > mp2 ) ? ( d << 1 ) - m : d << 1 ;              
        اگر ( a & 0x800000000000000ULL ) d += b ;      
        اگر ( d >= m ) d -= m ;      
        a <<= 1 ;  
    }
    بازگشت d ; 
}

در معماری‌های رایانه‌ای که در آن یک قالب دقیق گسترده با حداقل 64 بیت مانتیس موجود است (مانند نوع طولانی دوتایی اکثر کامپایلرهای x86 C)، روال زیر [ توضیحات لازم است ] ، با استفاده از ترفندی که توسط سخت‌افزار، شناور است. ضرب نقطه منجر به مهم‌ترین بیت‌های حاصل در نگهداری می‌شود، در حالی که ضرب اعداد صحیح باعث می‌شود کمترین بیت‌های مهم حفظ شوند: [ نیازمند منبع ]

uint64_t mul_mod ( uint64_t a , uint64_t b , uint64_t m ) {       
    x طولانی دوبل ;  
    uint64_t c ; 
    int64_t r ; 
    if ( a >= m ) a %= m ;      
    اگر ( b >= m ) b %= m ;      
    x = a ;  
    c = x * b / m ;      
    r = ( int64_t )( a * b - c * m ) % ( int64_t ) m ;          
    برگردانید r < 0 ? r + m : r ;         
}

در زیر یک تابع C برای انجام توان مدولار وجود دارد که از تابع mul_mod پیاده سازی شده در بالا استفاده می کند.

روشی الگوریتمی برای محاسبه $a^{b}{\pmod {m}}$ :

uint64_t pow_mod ( uint64_t a , uint64_t b , uint64_t m ) {       
    uint64_t r = m == 1 ? 0 : 1 ;         
    در حالی که ( b > 0 ) {    
        if ( b & 1 ) r = mul_mod ( r , a , m );        
        b = b >> 1 ;    
        a = mul_mod ( a , a , m );    
    }
    بازگشت r ; 
}

با این حال، برای اینکه همه روال های بالا کار کنند، m نباید از 63 بیت تجاوز کند.

همچنین ببینید [ ویرایش ]

حلقه بولی
بافر دایره ای
بخش (ریاضی)
میدان محدود
نماد افسانه
توان مدولار
مدول (ریاضیات)
گروه ضربی از اعداد صحیح پیمانه n
دوره پیزانو (دنباله های فیبوناچی مدول n )
ریشه اولیه پیمانه n
متقابل درجه دوم
باقیمانده درجه دوم
بازسازی منطقی (ریاضیات)
سیستم باقیمانده کاهش یافته
حسابی شماره سریال (مورد خاصی از محاسبات مدولار)
جبر بولی دو عنصری
موضوعات مربوط به نظریه گروه در پشت محاسبات مدولار:
- گروه چرخه ای
- گروه ضربی از اعداد صحیح پیمانه n
سایر قضایای مهم مربوط به محاسبات مدولار:
- قضیه کارمایکل
- قضیه باقی مانده چینی
- قضیه اویلر
- قضیه کوچک فرما (مورد خاص قضیه اویلر)
- قضیه لاگرانژ
- Thue's lemma

منبع

https://en.wikipedia.org/wiki/Modular_arithmetic

+ نوشته شده در چهارشنبه نوزدهم مرداد ۱۴۰۱ ساعت 2:27 توسط علی رضا نقش نیلچی |

ریاضیات

آموزش ریاضی