Pollard's kangaroo algorithm
કોમ્પ્યુટેશનલ નંબર થિયરી અને કોમ્પ્યુટેશનલ બીજગણિતમાં, પોલાર્ડનું કાંગારૂ અલ્ગોરિધમ (પોલાર્ડનું લેમ્બડા અલ્ગોરિધમ પણ, નીચે નામ આપવું જુઓ) એ અલગ લઘુગણક સમસ્યાને ઉકેલવા માટેનું એક અલ્ગોરિધમ છે. આ અલ્ગોરિધમ 1978 માં સંખ્યા સિદ્ધાંતવાદી જ્હોન એમ. પોલાર્ડ દ્વારા રજૂ કરવામાં આવ્યું હતું, જે સમાન સમસ્યાને ઉકેલવા માટે તેમના વધુ જાણીતા પોલાર્ડના રો અલ્ગોરિધમ તરીકે સમાન પેપરમાં રજૂ કરવામાં આવ્યું હતું. પોલાર્ડે એકમોના ગુણાકાર જૂથ મોડ્યુલો એ પ્રાઇમ પી માં સ્વતંત્ર લઘુગણક સમસ્યા માટે તેમના અલ્ગોરિધમનો ઉપયોગ વર્ણવ્યો હોવા છતાં, તે હકીકતમાં એક સામાન્ય સ્વતંત્ર લઘુગણક અલ્ગોરિધમ છે-તે કોઈપણ મર્યાદિત ચક્રીય જૂથમાં કામ કરશે. અલ્ગોરિધમ ધારો કે તે ક્રમનું મર્યાદિત ચક્રીય જૂથ છે જે તત્વ દ્વારા ઉત્પન્ન થાય છે, અને આપણે આધાર પર તત્વનું અલગ લઘુગણક શોધવાનો પ્રયાસ કરીએ છીએ. બીજા શબ્દોમાં કહીએ તો, એક એવી વસ્તુની શોધ કરે છે. લેમ્બડા અલ્ગોરિધમ અમુક અંતરાલમાં શોધવાની મંજૂરી આપે છે. અને સુયોજિત કરીને સંભવિત લઘુગણકની સંપૂર્ણ શ્રેણી શોધી શકાય છે. 1. સરેરાશના હકારાત્મક પૂર્ણાંકોનો સમૂહ પસંદ કરો અને સ્યુડોરાન્ડમ નકશાને વ્યાખ્યાયિત કરો. 2. પૂર્ણાંક પસંદ કરો અને 3 મુજબ જૂથ તત્વોના ક્રમની ગણતરી કરો. ગણતરી કરો કેઃ 4. નીચેના અનુસાર જૂથ તત્વોના બીજા ક્રમની ગણતરી શરૂ કરો અને નીચેના અનુસાર પૂર્ણાંકોની અનુરૂપ શ્રેણીની ગણતરી કરો. તેનું ધ્યાન રાખોઃ 5. શરતોની ગણતરી કરવાનું બંધ કરો અને જ્યારે નીચેની શરતોમાંથી કોઈ એક પૂરી થાયઃ A) કેટલાક માટે. જો ક્રમ અને "અથડામણ" આ રીતે થાય, તો આપણી પાસે છેઃ છે અને તેથી આપણે પૂર્ણ કરી લઈએ છીએ. બી). જો આવું થાય, તો એલ્ગોરિધમ શોધવામાં નિષ્ફળ ગયું છે. અને/અથવા ની પસંદગી બદલીને અનુગામી પ્રયાસો કરી શકાય છે. પોલાર્ડની જટિલતા એ ધારણા પર આધારિત સંભવિત દલીલનો ઉપયોગ કરીને અલ્ગોરિધમનો સમય જટિલતા આપે છે જે બનાવટી રીતે કાર્ય કરે છે. બિટ્સનો ઉપયોગ કરીને રજૂ કરી શકાય છે, તેથી આ સમસ્યાના કદમાં ઘાતાંકીય છે (જોકે હજુ પણ તુચ્છ બ્રુટ-ફોર્સ અલ્ગોરિધમ પર નોંધપાત્ર સુધારો છે જે સમય લે છે). સબએક્સપોનેન્શિયલ ટાઇમ ડિસ્ક્રીટ લઘુગણક અલ્ગોરિધમના ઉદાહરણ માટે, અનુક્રમણિકા કલન અલ્ગોરિધમ જુઓ. નામકરણ અલ્ગોરિધમ બે નામોથી જાણીતું છે. પ્રથમ "પોલાર્ડનું કાંગારૂ અલ્ગોરિધમ" છે. આ નામ એલ્ગોરિધમ પ્રસ્તુત કરતા પેપરમાં ઉપયોગમાં લેવાતી સામ્યતાનો સંદર્ભ છે, જ્યાં એલ્ગોરિધમને જંગલી કાંગારૂને ફસાવવા માટે કાબૂમાં રાખેલા કાંગારૂનો ઉપયોગ કરવાના સંદર્ભમાં સમજાવવામાં આવે છે. પોલાર્ડે સમજાવ્યું છે કે આ સામ્યતા આરએસએ પબ્લિક કી ક્રિપ્ટોસિસ્ટમના પ્રદર્શન તરીકે સાયન્ટિફિક અમેરિકનના સમાન અંકમાં પ્રકાશિત થયેલા "રસપ્રદ" લેખથી પ્રેરિત હતી. આ લેખમાં એક પ્રયોગનું વર્ણન કરવામાં આવ્યું છે જેમાં કાંગારૂની "વિવિધ ઝડપે ઓક્સિજનના વપરાશની દ્રષ્ટિએ માપવામાં આવતી હલનચલનની ઊર્જાસભર કિંમત, ટ્રેડમિલ પર કાંગારૂ મૂકીને નક્કી કરવામાં આવી હતી". બીજું "પોલાર્ડનું લેમ્બડા અલ્ગોરિધમ" છે. પોલાર્ડના અન્ય અલગ લઘુગણક અલ્ગોરિધમ્સના નામની જેમ, પોલાર્ડના rho અલ્ગોરિધમ, આ નામ અલ્ગોરિધમના વિઝ્યુલાઇઝેશન અને ગ્રીક અક્ષર lambda () વચ્ચેની સમાનતાનો સંદર્ભ આપે છે. લેમ્બડા અક્ષરનો ટૂંકો સ્ટ્રોક ક્રમને અનુરૂપ છે, કારણ કે તે x ની જમણી બાજુએ b સ્થિતિથી શરૂ થાય છે. તદનુસાર, લાંબો સ્ટ્રોક ક્રમને અનુરૂપ હોય છે, જે પ્રથમ ક્રમ સાથે "અથડાય છે" (જેમ કે લેમ્બડાના આંતરછેદના સ્ટ્રોક) અને પછી તેને અનુસરે છે. પોલાર્ડે "કાંગારૂ અલ્ગોરિધમ" નામ માટે પસંદગી વ્યક્ત કરી છે, કારણ કે આ તેમના રો અલ્ગોરિધમની કેટલીક સમાંતર આવૃત્તિઓ સાથે મૂંઝવણને ટાળે છે, જેને "લેમ્બડા અલ્ગોરિધમ્સ" પણ કહેવામાં આવે છે. ડાયન્કિનની કાર્ડ યુક્તિ ક્રુસ્કલ કાઉન્ટ રેઈન્બો ટેબલ સંદર્ભો પણ જુઓ વધુ વાંચન સંખ્યા સૈદ્ધાંતિક અલ્ગોરિધમ્સ કમ્પ્યુટર બીજગણિત લઘુગણક