എ.കെ.എസ്. അഭാജ്യതാപരിശോധന
ഒരേ സമയം സാമാന്യവും, ബഹുപദസങ്കീർണ്ണതയുള്ളതും, സുനിശ്ചിതവും, നിബന്ധനകളില്ലാത്തതുമായ അഭാജ്യതാപരിശോധനയ്ക്കുള്ള ആദ്യത്തെ അൽഗൊരിതമാണ് എ.കെ.എസ്. അഭാജ്യതാപരിശോധന അഥവാ അഗർവാൾ-കയാൽ-സക്സേന അഭാജ്യതാപരിശോധന. ഐ.ഐ.ടി. കാൻപൂരിലെ കമ്പ്യൂട്ടർ സയൻസ് പ്രൊഫസറായ മനീന്ദ്ര അഗർവാളും വിദ്യാർത്ഥികളായിരുന്ന നിതിൻ കയാൽ, നീരജ് സക്സേന എന്നിവരും ചേർന്ന് 2002-ലാണ് ഈ അൽഗൊരിതം കണ്ടുപിടിച്ചത്. സംഖ്യാസിദ്ധാന്തത്തിലെതന്നെ ഒരു സുപ്രധാന കണ്ടുപിടിത്തമായി എണ്ണപ്പെടുന്ന ഇതിന്റെ പേരിൽ ഉപജ്ഞാതാക്കൾക്ക് 2006-ലെ ഗീദൽ പുരസ്കാരം, ഫുൾകേഴ്സൺ പുരസ്കാരം എന്നിവയുൾപ്പെടെയുള്ള പുരസ്കാരങ്ങൾ ലഭിച്ചു.
പ്രാധാന്യം
തിരുത്തുകഒരേ സമയം നാല് ഗുണങ്ങളുള്ള ആദ്യത്തെ അഭാജ്യതാപരിശോധനാ അൽഗൊരിതമാണ് എന്നതാണ് എ.കെ.എസ് അൽഗൊരിതത്തിന്റെ പ്രാധാന്യം. നാലിൽ മൂന്ന് ഗുണങ്ങളുള്ള അൽഗൊരിതങ്ങൾ മുമ്പ് കണ്ടുപിടിക്കപ്പെട്ടിട്ടുണ്ടായിരുന്നെങ്കിലും ഇത്തരത്തിൽ പൂർണ്ണത കൈവരിക്കാനായത് എ.കെ.എസിനാണ്
- സാമാന്യത : എ.കെ.എസ്. അൽഗൊരിതത്തിന് ഏതൊരു സംഖ്യയും ഭാജ്യമോ അഭാജ്യമോ എന്ന് നിർണ്ണയിക്കാനാകും. മെഴ്സെൻ സംഖ്യകൾ, ഫെർമാ സംഖ്യകൾ എന്നിങ്ങനെ സവിശേഷ സംഖ്യകളുടെ അഭാജ്യത മാത്രം നിർണ്ണയിക്കാനാകുന്നതും മറ്റ് ഗുണങ്ങളുള്ളതുമായ അൽഗൊരിതങ്ങൾ മുമ്പേ നിലവിലുണ്ടായിരുന്നു
- ബഹുപദസങ്കീർണ്ണത : അൽഗൊരിതത്തിന്റെ ഗണനപരമായ സങ്കീർണ്ണത ബഹുപദമാണ്. അതായത്, അൽഗൊരിതം ഏതൊരു സംഖ്യയുടെയും അഭാജ്യത നിർണ്ണയിക്കാനെടുക്കുന്ന കൂടിയ സമയം സംഖ്യയിലെ അക്കങ്ങളുടെ എണ്ണത്തിന്റെ ഒരു പ്രത്യേക ബഹുപദത്തിൽ കുറവാണ്. ഇറാതോസ്തനീസിന്റെ അരിപ്പ മുതൽ എലിപ്റ്റിക് കർവ് അഭാജ്യതാപരിശോധന വരെയുള്ള അൽഗൊരിതങ്ങൾ ചില പ്രത്യേക സംഖ്യകളുടെ കാര്യത്തിലെങ്കിലും ഈ ഗുണമില്ലാത്തവയാണ്.
- സുനിശ്ചിതത്വം : ഏത് സംഖ്യയും അഭാജ്യമാണോ എന്ന് എ.കെ.എസ് അൽഗൊരിതത്തിന് പൂർണ്ണമായ ഉറപ്പോടെ നിർണ്ണയിക്കാൻ സാധിക്കും. മില്ലർ-റാബിൻ അഭാജ്യതാപരിശോധന ഉൾപ്പെടെ randomness ഉപയോഗിക്കുന്ന അൽഗൊരിതങ്ങൾ ബഹുപദസങ്കീർണ്ണതയുള്ളതാണെങ്കിലും ചില സംഖ്യകളുടെ അഭാജ്യത തെറ്റായി നിർണ്ണയിക്കാൻ സാധ്യതയുണ്ട്
- ഇതുവരെ തെളിയിക്കപ്പെട്ടിട്ടില്ലാത്ത ഒരു സിദ്ധാന്തത്തെയും അൽഗൊരിതം ആശ്രയിക്കുന്നില്ല. മില്ലർ പരിശോധന മറ്റ് മൂന്ന് ഗുണങ്ങളുള്ളതാണെങ്കിലും അത് ശരിയാണെന്ന് തെളിയിക്കുന്നത് ഇതുവരെ തെളിയിക്കപ്പെട്ടിട്ടില്ലാത്ത റീമാൻ പരികല്പന ശരിയെന്ന് കരുതിക്കൊണ്ടാണ്.
സങ്കീർണ്ണത
തിരുത്തുകഅൽഗൊരിതത്തിന്റെ ആദ്യരൂപത്തിന്റെ സങ്കീർണ്ണത Õ ആയിരുന്നു (ഇവിടെ n അഭാജ്യമാണോ എന്ന് പരിശോധിക്കേണ്ട സംഖ്യയാണ്). ഈ സങ്കീർണ്ണത മെച്ചപ്പെടുത്താൻ ഏറെ ശ്രമങ്ങളുണ്ടായി. 2005-ൽ കാൾ പോമെറൻസ്, ഹെൻഡ്രിക് ലെന്സ്ട്ര ജൂനിയർ എന്നിവർ ചേർന്ന് അൽഗൊരിതത്തിന് Õ സങ്കീർണ്ണതയുള്ള ഒരു രൂപം കണ്ടെത്തി.
