Modular multiplicative inverse
ગણિતમાં, ખાસ કરીને અંકગણિતના ક્ષેત્રમાં, પૂર્ણાંકનો મોડ્યુલર ગુણાકાર વ્યસ્ત એ એવો પૂર્ણાંક છે કે જે ગુણાકારના સંદર્ભમાં ગુણાકાર 1 સાથે એકરૂપ હોય. મોડ્યુલર અંકગણિતના પ્રમાણભૂત સંકેતલિપીમાં આ એકરૂપતા લખવામાં આવે છે જે નિવેદન લખવાની ટૂંકી રીત છે જે (સમાનરૂપે) જથ્થાને વિભાજિત કરે છે, અથવા, બીજી રીતે કહીએ તો, પૂર્ણાંક દ્વારા વિભાજીત કર્યા પછી બાકી 1 છે. જો તેમાં ઇન્વર્સ મોડ્યુલો હોય, તો આ એકરૂપતાના અનંત ઉકેલો છે, જે આ અનુરૂપના સંદર્ભમાં એકરૂપ વર્ગ બનાવે છે. વધુમાં, કોઈપણ પૂર્ણાંક કે જે (એટલે કે, તેના એકરૂપ વર્ગમાં) એકરૂપ હોય છે, તેમાં એકરૂપ વર્ગનું કોઈપણ તત્વ મોડ્યુલર ગુણાકાર વ્યુત્ક્રમ તરીકે હોય છે. સમાવિષ્ટ એકરૂપ વર્ગને સૂચવવા માટે નોટેશનનો ઉપયોગ કરીને, આ એમ કહીને વ્યક્ત કરી શકાય છે કે એકરૂપ વર્ગનો મોડ્યુલો ગુણાકાર વ્યસ્ત એ એકરૂપ વર્ગ છે જેમ કેઃ જ્યાં પ્રતીક સમકક્ષ વર્ગ મોડ્યુલોના ગુણાકારને સૂચવે છે. આ રીતે લખાયેલ, તર્કસંગત અથવા વાસ્તવિક સંખ્યાઓના સમૂહમાં ગુણાકાર વ્યુત્ક્રમની સામાન્ય વિભાવના સાથેની સામ્યતાને સ્પષ્ટ રીતે રજૂ કરવામાં આવે છે, જે સંખ્યાઓને એકરૂપ વર્ગો દ્વારા બદલે છે અને દ્વિસંગી કામગીરીને યોગ્ય રીતે બદલે છે. વાસ્તવિક સંખ્યાઓ પર સમાન કામગીરીની જેમ, આ કામગીરીનો મૂળભૂત ઉપયોગ ઉકેલવામાં થાય છે, જ્યારે શક્ય હોય ત્યારે, ફોર્મની રેખીય એકરૂપતાઓ મોડ્યુલર ગુણાકાર વ્યુત્ક્રમો શોધવામાં પણ ક્રિપ્ટોગ્રાફીના ક્ષેત્રમાં વ્યવહારુ ઉપયોગો છે, દા. ત. પબ્લિક-કી ક્રિપ્ટોગ્રાફી અને આરએસએ અલ્ગોરિધમ. આ એપ્લિકેશનોના કમ્પ્યુટર અમલીકરણ માટેનો એક ફાયદો એ છે કે ત્યાં એક ખૂબ જ ઝડપી અલ્ગોરિધમ (વિસ્તૃત યુક્લિડિયન અલ્ગોરિધમ) અસ્તિત્વમાં છે જેનો ઉપયોગ મોડ્યુલર મલ્ટિપ્લિકેટિવ ઇન્વર્સની ગણતરી માટે થઈ શકે છે. મોડ્યુલર અંકગણિત આપેલ હકારાત્મક પૂર્ણાંક માટે, બે પૂર્ણાંકો, અને, જો તેમના તફાવતને વિભાજિત કરે તો તેને સર્વસંમત મોડ્યુલો કહેવામાં આવે છે. આ દ્વિસંગી સંબંધ આ રીતે સૂચવવામાં આવે છે, આ પૂર્ણાંકોના સમૂહ પરનો સમાનતા સંબંધ છે, અને સમાનતા વર્ગોને એકરૂપતા વર્ગો મોડ્યુલો અથવા અવશેષ વર્ગો મોડ્યુલો કહેવામાં આવે છે. ચાલો પૂર્ણાંક ધરાવતા એકરૂપ વર્ગને દર્શાવીએ, પછી એક રેખીય એકરૂપતા એ સ્વરૂપનું મોડ્યુલર એકરૂપતા છે વાસ્તવિક સમીકરણોથી વિપરીત, રેખીય એકરૂપતામાં શૂન્ય, એક અથવા અનેક ઉકેલો હોઈ શકે છે. જો રેખીય એકરૂપતાનો ઉકેલ હોય તો તેમાંનું દરેક તત્વ પણ એક ઉકેલ છે, તેથી, જ્યારે રેખીય એકરૂપતાના ઉકેલોની સંખ્યાની વાત કરવામાં આવે ત્યારે આપણે ઉકેલો ધરાવતા વિવિધ એકરૂપતા વર્ગોની સંખ્યાનો ઉલ્લેખ કરી રહ્યા છીએ. જો તે સૌથી મોટો સામાન્ય ભાજક છે અને પછી રેખીય એકરૂપતાનો ઉકેલ હોય છે જો અને માત્ર ત્યારે જ જો તે વિભાજિત થાય. જો વિભાજન થાય, તો ચોક્કસ ઉકેલો છે. મોડ્યુલસના સંદર્ભમાં પૂર્ણાંકનો મોડ્યુલર મલ્ટિપ્લિકેટિવ ઇન્વર્સ એ રેખીય એકરૂપતાનો ઉકેલ છે અગાઉનું પરિણામ કહે છે કે ઉકેલ અસ્તિત્વમાં છે જો અને માત્ર જો, એટલે કે, અને પ્રમાણમાં અવિભાજ્ય હોવો જોઈએ (એટલે કે. કોપ્રાઇમ). વધુમાં, જ્યારે આ સ્થિતિ રહે છે, ત્યારે બરાબર એક જ ઉકેલ હોય છે, એટલે કે, જ્યારે તે અસ્તિત્વમાં હોય, ત્યારે મોડ્યુલર ગુણાકાર વ્યુત્ક્રમ અનન્ય હોય છેઃ જો અને બંને મોડ્યુલસના સંદર્ભમાં મોડ્યુલર ગુણાકાર વ્યુત્ક્રમ હોય, તો તેથી જો, તો, અને તેમાં મોડ્યુલર ગુણાકાર વ્યુત્ક્રમ પણ નહીં હોય. તેથી, {{math|b ષ્ણ b (મોડ m)}}. જ્યારે ઉકેલ હોય ત્યારે તેને ઘણીવાર આ રીતે દર્શાવવામાં આવે છે-પરંતુ આને સંકેતનો દુરુપયોગ ગણી શકાય કારણ કે તેને પારસ્પરિક તરીકે ખોટું અર્થઘટન કરી શકાય છે (જે, મોડ્યુલર ગુણાકાર વ્યુત્ક્રમની વિરુદ્ધમાં, જ્યારે 1 અથવા-1 હોય તે સિવાય પૂર્ણાંક નથી). જો એકરૂપ વર્ગ માટે ટોકન સ્ટેન્ડિંગ તરીકે અર્થઘટન કરવામાં આવે તો સંકેત યોગ્ય રહેશે, કારણ કે એકરૂપ વર્ગનો ગુણાકાર વ્યસ્ત એ આગામી વિભાગમાં વ્યાખ્યાયિત ગુણાકાર સાથે એકરૂપ વર્ગ છે. પૂર્ણાંકો મોડ્યુલો એકરૂપ સંબંધ, મોડ્યુલો, પૂર્ણાંકોના સમૂહને એકરૂપ વર્ગોમાં વિભાજીત કરે છે. આ પદાર્થો પર સરવાળા અને ગુણાકારની કામગીરીને નીચેની રીતે વ્યાખ્યાયિત કરી શકાય છેઃ બે એકરૂપ વર્ગોને ઉમેરવા અથવા ગુણાકાર કરવા માટે, પહેલા દરેક વર્ગમાંથી એક પ્રતિનિધિ (કોઈપણ રીતે) પસંદ કરો, પછી બે પ્રતિનિધિઓ પર પૂર્ણાંકો માટે સામાન્ય કામગીરી કરો અને અંતે એકરૂપ વર્ગ લો કે જે એકરૂપ વર્ગો પરની કામગીરીના પરિણામે પૂર્ણાંક કામગીરીનું પરિણામ છે. પ્રતીકોમાં, સુસંગતતા વર્ગો પરની કામગીરીઓ સાથે અને તેનું પ્રતિનિધિત્વ કરતી આ વ્યાખ્યાઓ છે અને આ કામગીરીઓ સારી રીતે વ્યાખ્યાયિત છે, એટલે કે અંતિમ પરિણામ પ્રતિનિધિઓની પસંદગીઓ પર આધારિત નથી કે જે પરિણામ મેળવવા માટે કરવામાં આવી હતી. આ બે વ્યાખ્યાયિત કામગીરીઓ સાથેના સુસંગતતા વર્ગો એક રિંગ બનાવે છે, જેને પૂર્ણાંકોની રીંગ મોડ્યુલો કહેવાય છે. આ બીજગણિત પદાર્થો માટે ઘણા સંકેતો વપરાય છે, મોટાભાગે અથવા, પરંતુ જ્યારે અન્ય બીજગણિત પદાર્થો સાથે મૂંઝવણ થવાની સંભાવના ન હોય ત્યારે કેટલાક પ્રાથમિક ગ્રંથો અને ઉપયોગ ક્ષેત્રો સરળ સંકેતલિપીનો ઉપયોગ કરે છે. પૂર્ણાંકો મોડ્યુલોના એકરૂપ વર્ગો પરંપરાગત રીતે અવશેષ વર્ગો મોડ્યુલો એમ તરીકે ઓળખાતા હતા, જે એ હકીકતને પ્રતિબિંબિત કરે છે કે એકરૂપ વર્ગના તમામ ઘટકો દ્વારા વિભાજિત થવા પર સમાન શેષ (એટલે કે, "અવશેષ") હોય છે. પૂર્ણાંકોનો કોઈપણ સમૂહ પસંદ કરવામાં આવે છે જેથી દરેક અલગ એકરૂપ વર્ગ મોડ્યુલો m માંથી આવે તેને અવશેષ મોડ્યુલોની સંપૂર્ણ પ્રણાલી કહેવામાં આવે છે. વિભાજન અલ્ગોરિધમ દર્શાવે છે કે પૂર્ણાંકોનો સમૂહ, અવશેષ મોડ્યુલોની સંપૂર્ણ પ્રણાલી બનાવે છે, જેને ઓછામાં ઓછા અવશેષ સિસ્ટમ મોડ્યુલો તરીકે ઓળખવામાં આવે છે. અંકગણિત સમસ્યાઓ સાથે કામ કરવામાં કેટલીકવાર અવશેષોની સંપૂર્ણ પ્રણાલી સાથે કામ કરવું અને એકરૂપતાની ભાષાનો ઉપયોગ કરવો વધુ અનુકૂળ હોય છે જ્યારે અન્ય સમયે રિંગના એકરૂપ વર્ગોનો દૃષ્ટિકોણ વધુ ઉપયોગી હોય છે. પૂર્ણાંકો મોડ્યુલોના ગુણાકાર જૂથ સંપૂર્ણ અવશેષ સિસ્ટમ મોડ્યુલોના દરેક તત્વમાં ગુણાકાર ઇન્વર્સ મોડ્યુલર નથી, ઉદાહરણ તરીકે, શૂન્ય ક્યારેય નથી. સંપૂર્ણ અવશેષ પ્રણાલીના એવા તત્વોને દૂર કર્યા પછી કે જે પ્રમાણમાં મુખ્ય નથી, જે બાકી રહે છે તેને ઘટાડેલી અવશેષ પ્રણાલી કહેવામાં આવે છે, જેના તમામ ઘટકોમાં મોડ્યુલર ગુણાકાર વ્યુત્ક્રમ હોય છે. ઘટાડેલી અવશેષ પ્રણાલીમાં તત્વોની સંખ્યા છે, જ્યાં યુલર ટોશિયન્ટ ફંક્શન છે, એટલે કે, તેના કરતા ઓછા હકારાત્મક પૂર્ણાંકોની સંખ્યા પ્રમાણમાં મુખ્ય છે. એકતા ધરાવતી સામાન્ય વીંટીમાં દરેક તત્વનો ગુણાકાર વ્યુત્ક્રમ હોતો નથી અને જે કરે છે તેને એકમો કહેવામાં આવે છે. બે એકમોનું ઉત્પાદન એક એકમ હોવાથી, વીંટીના એકમો એક જૂથ બનાવે છે, જે વીંટીના એકમોનું જૂથ છે અને ઘણીવાર જો એ વીંટીનું નામ હોય તો તેના દ્વારા સૂચવવામાં આવે છે. પૂર્ણાંકો મોડ્યુલોની વીંટીના એકમોના જૂથને પૂર્ણાંકો મોડ્યુલો 'નું ગુણાકાર જૂથ કહેવામાં આવે છે, અને તે ઘટાડેલી અવશેષ પ્રણાલી માટે સમરૂપ છે. ખાસ કરીને, તેમાં ક્રમ (કદ) છે. એવા કિસ્સામાં કે જે અવિભાજ્ય છે, કહો, અને તેના તમામ બિન-શૂન્ય ઘટકો ગુણાકાર વ્યુત્ક્રમ ધરાવે છે, આમ તે એક મર્યાદિત ક્ષેત્ર છે. આ કિસ્સામાં, પૂર્ણાંકો મોડ્યુલોનું ગુણાકાર જૂથ ક્રમનું ચક્રીય જૂથ બનાવે છે. ઉદાહરણ કોઈપણ પૂર્ણાંક માટે, તે હંમેશા મોડ્યુલસના સંદર્ભમાં મોડ્યુલર મલ્ટિપ્લિકેટિવ ઇન્વર્સ હોય છે. ઉદાહરણો છે, અને તેથી વધુ. નીચેનું ઉદાહરણ મોડ્યુલસ 10 નો ઉપયોગ કરે છેઃ બે પૂર્ણાંકો એકરૂપ મોડ 10 છે જો અને માત્ર ત્યારે જ જો તેમનો તફાવત 10 વડે વિભાજ્ય હોય, ઉદાહરણ તરીકે 10 એ 32 − 2 = 30 ને વિભાજિત કરે છે, અને 10 એ 111 − 1 = 110 ને વિભાજિત કરે છે. આ મોડ્યુલસના સંદર્ભમાં દસ એકરૂપ વર્ગોમાંથી કેટલાક આ પ્રમાણે છેઃ અને રેખીય એકરૂપતાનો કોઈ ઉકેલ નથી કારણ કે જે પૂર્ણાંકો 5 (એટલે કે, જે અંદર છે) સાથે એકરૂપ હોય છે તે બધા વિષમ હોય છે જ્યારે હંમેશા સમ હોય છે. જો કે, રેખીય એકરૂપતામાં બે ઉકેલો છે, એટલે કે, અને. અને 2 એ 5 ને વિભાજીત કરતું નથી, પરંતુ 6 ને વિભાજીત કરે છે. કારણ કે, રેખીય એકરૂપતામાં ઉકેલો હશે, એટલે કે, 3 મોડ્યુલો 10 ના મોડ્યુલર મલ્ટિપ્લિકેટિવ ઇન્વર્સ અસ્તિત્વમાં હશે. હકીકતમાં, 7 આ એકરૂપતાને સંતોષે છે (એટલે કે, 21−1 = 20). જો કે, અન્ય પૂર્ણાંકો પણ એકરૂપતાને સંતોષે છે, ઉદાહરણ તરીકે 17 અને −3 (એટલે કે, 3 (17) −1 = 50 અને 3 (−3) −1 = −10). ખાસ કરીને, દરેક પૂર્ણાંક એકરૂપતાને સંતોષશે કારણ કે આ પૂર્ણાંકો અમુક પૂર્ણાંકો માટેનું સ્વરૂપ ધરાવે છે અને 10 વડે વિભાજીત થાય છે. આ એકરૂપતામાં ઉકેલોનો માત્ર આ એક એકરૂપ વર્ગ છે. આ કિસ્સામાં ઉકેલ તમામ સંભવિત કેસોની તપાસ કરીને મેળવી શકાયો હોત, પરંતુ મોટા મોડ્યુલી માટે વ્યવસ્થિત અલ્ગોરિધમ્સની જરૂર પડશે અને આ આગામી વિભાગમાં આપવામાં આવશે. એકરૂપ વર્ગોનું ગુણાકાર અને 25નું તત્વ અને −2નું તત્વ પસંદ કરીને અને તેમનું ગુણાકાર (25) (−2) = −50 એકરૂપ વર્ગમાં છે તેનું નિરીક્ષણ કરીને મેળવી શકાય છે. આમ, તા. સરવાળાને સમાન રીતે વ્યાખ્યાયિત કરવામાં આવે છે. દસ એકરૂપતા વર્ગો, એકરૂપતા વર્ગોના ઉમેરા અને ગુણાકારની આ કામગીરીઓ સાથે મળીને પૂર્ણાંકો મોડ્યુલો 10, એટલે કે પૂર્ણાંકોની વીંટી બનાવે છે. સંપૂર્ણ અવશેષ સિસ્ટમ મોડ્યુલો 10 એ સમૂહ {10, −9,2,13,24, −15,26,37,8,9} હોઈ શકે છે જ્યાં દરેક પૂર્ણાંક અલગ એકરૂપ વર્ગ મોડ્યુલો 10 માં હોય છે. અનન્ય લઘુત્તમ અવશેષ સિસ્ટમ મોડ્યુલો 10 એ {0,1,2,., 9} છે. રિડ્યુસ્ડ રેસિડ્યુ સિસ્ટમ મોડ્યુલો 10 {1,3,7,9} હોઈ શકે છે. આ સંખ્યાઓ દ્વારા રજૂ થયેલ કોઈપણ બે એકરૂપ વર્ગોનું ગુણાકાર ફરીથી આ ચાર એકરૂપ વર્ગમાંથી એક છે. આ સૂચવે છે કે આ ચાર એકરૂપ વર્ગો એક જૂથ બનાવે છે, આ કિસ્સામાં ક્રમ ચારનું ચક્રીય જૂથ, જેમાં 3 અથવા 7 (ગુણાકાર) જનરેટર તરીકે હોય છે. રજૂ થયેલ એકરૂપ વર્ગ રિંગના એકમોનું જૂથ બનાવે છે. આ એકરૂપતા વર્ગો ચોક્કસપણે એવા વર્ગો છે જે મોડ્યુલર ગુણાકાર વ્યુત્ક્રમ ધરાવે છે. કમ્પ્યુટેશન એક્સટેન્ડેડ યુક્લિડિયન અલ્ગોરિધમ વિસ્તૃત યુક્લિડિયન અલ્ગોરિધમનો ઉપયોગ કરીને મોડ્યુલોના મોડ્યુલર મલ્ટિપ્લિકેટિવ ઇન્વર્સને શોધી શકાય છે. યુક્લિડિયન અલ્ગોરિધમ બે પૂર્ણાંકોના સૌથી મોટા સામાન્ય ભાજક (જી. સી. ડી.) નક્કી કરે છે, જેમ કે અને. જો મલ્ટિપ્લિકેટિવ ઇન્વર્સ મોડ્યુલો હોય, તો આ જીસીડી 1 હોવો જોઈએ. અલ્ગોરિધમ દ્વારા ઉત્પાદિત કેટલાક સમીકરણોમાંથી છેલ્લું આ જીસીડી માટે ઉકેલી શકાય છે. પછી, "બેક સબસ્ટિટ્યુશન" નામની પદ્ધતિનો ઉપયોગ કરીને, મૂળ પરિમાણો અને આ જી. સી. ડી. ને જોડતી અભિવ્યક્તિ મેળવી શકાય છે. બીજા શબ્દોમાં કહીએ તો, પૂર્ણાંકો અને બેઝઆઉટની ઓળખને સંતોષવા માટે શોધી શકાય છે, ફરીથી લખાયેલ, આ તે છે, તેથી, એક મોડ્યુલર ગુણાકાર વ્યુત્ક્રમની ગણતરી કરવામાં આવી છે. અલ્ગોરિધમનો વધુ કાર્યક્ષમ સંસ્કરણ વિસ્તૃત યુક્લિડિયન અલ્ગોરિધમ છે, જે સહાયક સમીકરણોનો ઉપયોગ કરીને, અલ્ગોરિધમમાંથી પસાર થતા બે પાસને ઘટાડે છે (પાછળના વિકલ્પને વિપરીત રીતે અલ્ગોરિધમમાંથી પસાર થતો હોવાનું વિચારી શકાય છે). મોટા ઓ સંકેતલિપીમાં, આ અલ્ગોરિધમ સમયસર ચાલે છે, એમ ધારીને, અને તેના વૈકલ્પિક, ઘાતાંક કરતાં ખૂબ જ ઝડપી અને સામાન્ય રીતે વધુ કાર્યક્ષમ માનવામાં આવે છે. યુલરના પ્રમેયનો ઉપયોગ વિસ્તૃત યુક્લિડિયન અલ્ગોરિધમનો વિકલ્પ તરીકે, યુલરના પ્રમેયનો ઉપયોગ મોડ્યુલર ઇન્વર્સની ગણતરી કરવા માટે થઈ શકે છે. યુલરના પ્રમેય અનુસાર, જો સહમૌલિક છે, એટલે કે, તો યુલરનું ટોશિયન્ટ કાર્ય ક્યાં છે. આ એ હકીકત પરથી અનુસરે છે કે જે ગુણાકાર જૂથ × સાથે સંબંધિત છે જો અને માત્ર જો સહમૌલિક હોય તો. તેથી, મોડ્યુલર મલ્ટિપ્લિકેટિવ ઇન્વર્સ સીધો મળી શકે છેઃ ખાસ કિસ્સામાં જ્યાં પ્રાઇમ છે, અને મોડ્યુલર ઇન્વર્સ દ્વારા આપવામાં આવે છે આ પદ્ધતિ સામાન્ય રીતે વિસ્તૃત યુક્લિડિયન અલ્ગોરિધમ કરતાં ધીમી હોય છે, પરંતુ કેટલીકવાર જ્યારે મોડ્યુલર એક્સ્પોનેન્શિયેશન માટે અમલીકરણ પહેલેથી જ ઉપલબ્ધ હોય ત્યારે તેનો ઉપયોગ થાય છે. આ પદ્ધતિના કેટલાક ગેરફાયદાઓમાં નીચેનાનો સમાવેશ થાય છેઃ મૂલ્ય જાણવું આવશ્યક છે અને સૌથી કાર્યક્ષમ જાણીતી ગણતરી માટે ફેક્ટરાઇઝેશન જરૂરી છે. ફેક્ટરાઇઝેશનને વ્યાપક રીતે ગણતરીની દ્રષ્ટિએ મુશ્કેલ સમસ્યા માનવામાં આવે છે. જો કે, જ્યારે તેનું મુખ્ય ગુણાંકકરણ જાણીતું હોય ત્યારે ગણતરી કરવી સરળ છે. ઘાતાંકની સંબંધિત કિંમત. જો કે તેને મોડ્યુલર એક્સ્પોનેન્શિયેશનનો ઉપયોગ કરીને વધુ અસરકારક રીતે અમલમાં મૂકી શકાય છે, જ્યારે મોટા મૂલ્યો સામેલ હોય ત્યારે આની ગણતરી મોન્ટગોમેરી રિડક્શન પદ્ધતિ સાથે સૌથી વધુ અસરકારક રીતે કરવામાં આવે છે, તે પદ્ધતિ, પોતે, મોડ્યુલર ઇન્વર્સ મોડની જરૂર પડે છે, જે પ્રથમ સ્થાને ગણતરી કરવાની હતી. મોન્ટગોમેરી પદ્ધતિ વિના, પ્રમાણભૂત દ્વિસંગી ઘાતાંક, જેને દરેક તબક્કે વિભાજન મોડની જરૂર હોય છે, તે મોટી હોય ત્યારે ધીમી કામગીરી છે. આ તકનીકનો એક નોંધપાત્ર ફાયદો એ છે કે ત્યાં કોઈ શરતી શાખાઓ નથી જે મૂલ્ય પર આધાર રાખે છે, અને આમ મૂલ્ય, જે જાહેર-કી ગુપ્તલેખનમાં એક મહત્વપૂર્ણ રહસ્ય હોઈ શકે છે, તેને બાજુ-ચેનલ હુમલાઓથી સુરક્ષિત કરી શકાય છે. આ કારણોસર, કર્વ 25519 નું પ્રમાણભૂત અમલીકરણ આ તકનીકનો ઉપયોગ ઇન્વર્સની ગણતરી કરવા માટે કરે છે. બહુવિધ વ્યુત્ક્રમ યુક્લિડિયન અલ્ગોરિધમનો એક જ આહ્વાન અને વધારાના ઇનપુટ દીઠ ત્રણ ગુણાકાર સાથે બહુવિધ સંખ્યાઓના વ્યુત્ક્રમની ગણતરી કરવી શક્ય છે. મૂળભૂત વિચાર એ છે કે બધાની પેદાશ બનાવવી, તેને ઉલટાવી દો, પછી બધા દ્વારા ગુણાકાર કરો જેથી માત્ર ઇચ્છિત જ રહે. વધુ સ્પષ્ટ રીતે, અલ્ગોરિધમ છે (બધા અંકગણિત દ્વારા કરવામાં આવેલ મોડ્યુલો): બધા માટે ઉપસર્ગ ઉત્પાદનોની ગણતરી કરો. કોઈપણ ઉપલબ્ધ અલ્ગોરિધમનો ઉપયોગ કરીને ગણતરી કરો. નીચેથી 2 સુધી, અને ની ગણતરી કરો. છેવટે, તા. સમાંતર કમ્પ્યુટિંગનો ઉપયોગ કરવા માટે રેખીય રીતે કરવાને બદલે વૃક્ષની રચનામાં ગુણાકાર કરવો શક્ય છે. એપ્લિકેશન્સ મોડ્યુલર મલ્ટિપ્લિકેટિવ ઇન્વર્સ શોધવામાં એલ્ગોરિધમ્સમાં ઘણી એપ્લિકેશનો છે જે મોડ્યુલર અંકગણિતના સિદ્ધાંત પર આધાર રાખે છે. દાખલા તરીકે, ક્રિપ્ટોગ્રાફીમાં મોડ્યુલર અંકગણિતનો ઉપયોગ કેટલીક કામગીરીઓને વધુ ઝડપથી અને ઓછી સંગ્રહ જરૂરિયાતો સાથે હાથ ધરવાની મંજૂરી આપે છે, જ્યારે અન્ય કામગીરીઓ વધુ મુશ્કેલ બની જાય છે. આ બંને સુવિધાઓનો લાભ લેવા માટે ઉપયોગ કરી શકાય છે. ખાસ કરીને, આરએસએ અલ્ગોરિધમમાં, સંદેશને એન્ક્રિપ્ટ અને ડિક્રિપ્ટ કરવો એ સંખ્યાઓની જોડીનો ઉપયોગ કરીને કરવામાં આવે છે જે કાળજીપૂર્વક પસંદ કરેલા મોડ્યુલસના સંદર્ભમાં ગુણાકાર વ્યુત્ક્રમ હોય છે. આમાંથી એક નંબર જાહેર કરવામાં આવે છે અને તેનો ઉપયોગ ઝડપી એન્ક્રિપ્શન પ્રક્રિયામાં થઈ શકે છે, જ્યારે અન્ય, જે ડિક્રિપ્શન પ્રક્રિયામાં વપરાય છે, તેને છુપાવી રાખવામાં આવે છે. જાહેર નંબરમાંથી છુપાયેલા નંબરને નક્કી કરવાનું ગણતરીત્મક રીતે અવ્યવહારુ માનવામાં આવે છે અને આ તે છે જે ગોપનીયતા સુનિશ્ચિત કરવા માટે સિસ્ટમને કાર્ય કરે છે. એક અલગ સંદર્ભમાં અન્ય ઉદાહરણ તરીકે, કોમ્પ્યુટર વિજ્ઞાનમાં ચોક્કસ વિભાજન સમસ્યાને ધ્યાનમાં લો જ્યાં તમારી પાસે વિચિત્ર શબ્દ-કદની સંખ્યાઓની સૂચિ છે જે દરેક દ્વારા વિભાજીત થાય છે અને તમે તે બધાને વિભાજીત કરવા માંગો છો. એક ઉકેલ નીચે મુજબ છેઃ ગણતરી કરવા માટે વિસ્તૃત યુક્લિડિયન અલ્ગોરિધમનો ઉપયોગ કરો, જેનો મોડ્યુલર ગુણાકાર વ્યસ્ત છે, જ્યાં શબ્દમાં બિટ્સની સંખ્યા છે. આ ઇન્વર્સ અસ્તિત્વમાં રહેશે કારણ કે સંખ્યાઓ વિચિત્ર છે અને મોડ્યુલસમાં કોઈ વિચિત્ર પરિબળો નથી. સૂચિમાં દરેક સંખ્યા માટે, તેને ગુણાકાર કરો અને પરિણામનો સૌથી ઓછો નોંધપાત્ર શબ્દ લો. ઘણા મશીનો પર, ખાસ કરીને વિભાજન માટે હાર્ડવેર સપોર્ટ વિનાના મશીનો પર, વિભાજન એ ગુણાકાર કરતાં ધીમી કામગીરી છે, તેથી આ અભિગમ નોંધપાત્ર ઝડપ મેળવી શકે છે. પ્રથમ પગલું પ્રમાણમાં ધીમું છે પરંતુ માત્ર એક જ વાર કરવાની જરૂર છે. મોડ્યુલર મલ્ટિપ્લિકેટિવ ઇન્વર્સનો ઉપયોગ રેખીય એકરૂપતાની પદ્ધતિનો ઉકેલ મેળવવા માટે થાય છે જેની ખાતરી ચાઇનીઝ રિમેઇન્ડર પ્રમેય દ્વારા આપવામાં આવે છે. ઉદાહરણ તરીકે, સિસ્ટમ ષ્ણ 4 (મોડ 5) ષ્ણ 4 (મોડ 7) ષ્ણ 6 (મોડ 11) સામાન્ય ઉકેલો ધરાવે છે કારણ કે 5,7 અને 11 જોડી મુજબ સહમૌલિક છે. ઉકેલ = (7 × 11) × 4 + (5 × 11) × 4 + (5 × 7) × 6 દ્વારા આપવામાં આવે છે જ્યાં = 3 એ 7 × 11 (મોડ 5) નો મોડ્યુલર ગુણાકાર વ્યસ્ત છે, = 6 એ 5 × 11 (મોડ 7) નો મોડ્યુલર ગુણાકાર વ્યસ્ત છે અને = 6 એ 5 × 7 (મોડ 11) નો મોડ્યુલર ગુણાકાર વ્યસ્ત છે. આમ, = 3 × (7 × 11) × 4 + 6 × (5 × 11) × 4 + 6 × (5 × 7) × 6 = 3504 અને તેના અનન્ય ઘટાડેલા સ્વરૂપમાં ષ્ણ 3504 ષ્ણ 39 (મોડ 385) 385 થી 5,7 અને 11 નું એલસીએમ છે. ઉપરાંત, ક્લૂસ્ટરમેન સરવાળાની વ્યાખ્યામાં મોડ્યુલર મલ્ટિપ્લિકેટિવ ઇન્વર્સ મુખ્યત્વે જોવા મળે છે. આ પણ જુઓ-ઇન્વર્સિવ કોન્ગ્રુએન્શિયલ જનરેટર-એક સ્યુડો-રેન્ડમ નંબર જનરેટર જે મોડ્યુલર મલ્ટિપ્લિકેટિવ ઇન્વર્સનો ઉપયોગ કરે છે તર્કસંગત પુનર્નિર્માણ (ગણિત) નોંધો સંદર્ભો બાહ્ય કડીઓ ગુવેરા વાસ્કેઝ, ફર્નાન્ડો યુક્લિડના એલ્ગોરિધમ મોડ્યુલર અંકગણિત દ્વિસંગી કામગીરીનો ઉપયોગ કરીને મોડ્યુલો મલ્ટિપ્લિકેટિવ ઇન્વર્સને હલ કરવાનું ઉકેલાયેલ ઉદાહરણ પૂરું પાડે છે.