Από το ΒΗΜΑ, Ημ. Έκδοσης 25-08-2002

Μια νίκη της επιστήμης των υπολογιστών
* Το μήνυμα για τους έλληνες επιστήμονες είναι σαφές: είναι πραγματοποιήσιμη και στη χώρα μας
η ποιοτικά υψηλή βασική έρευνα, αρκεί να υπάρχει ενθάρρυνση και αγάπη για αυτήν

Π. ΣΠΥΡΑΚΗΣ

Τρεις ινδοί επιστήμονες της Πληροφορικής έλυσαν ένα θεμελιώδες πρόβλημα του κλάδου επινοώντας μια μέθοδο με την οποία ένας υπολογιστής μπορεί, γρήγορα και χωρίς αβεβαιότητα, να διαπιστώσει αν ένας αριθμός είναι πρώτος, δηλαδή αν διαιρείται ακριβώς μόνο από τον εαυτό του και τη μονάδα.

Οι πρώτοι αριθμοί απασχόλησαν από την αρχαιότητα τους έλληνες και κινέζους μαθηματικούς. Το «κόσκινο» του Ερατοσθένη (240 π.Χ.) είναι η αρχαιότερη μέθοδος ελέγχου αν ένας αριθμός είναι πρώτος. Ωστόσο, ο χρόνος υπολογισμού της μεθόδου την καθιστά απαγορευτική για πολύ μεγάλους αριθμούς.

Οι πρώτοι αριθμοί έχουν κρίσιμο ρόλο στη σύγχρονη κρυπτογραφία. Επομένως, η επινόηση γρήγορων μεθόδων για έλεγχο του κατά πόσον ένας αριθμός είναι πρώτος είναι ιδιαίτερα σημαντική. Ως τώρα οι γνωστές γρήγορες μέθοδοι (αλγόριθμοι) για το πρόβλημα αυτό είχαν την ατέλεια να αποδέχονται μια μικρή πιθανότητα λάθους απαντήσεως (ή μη απαντήσεως).

Ο νέος αλγόριθμος, των Manindra Agrawal, Neeraj Kayal και Nitin Saxena, επιστημόνων του Ινδικού Ινστιτούτου Τεχνολογίας της Κανπούρ, εγγυάται μια γρήγορη και ορθή απάντηση. Αν και η εργασία τους δεν έχει ακόμη επίσημα δημοσιευθεί, έχει ήδη ελεγχθεί από κορυφαίους επιστήμονες και είναι έγκυρα ορθή.

Το αποτέλεσμα της έρευνας των τριών ινδών ειδικών της Πληροφορικής είναι ίσως η πιο εντυπωσιακή νίκη της Επιστήμης Υπολογιστών της τελευταίας δεκαετίας όσον αφορά τη θεμελίωσή της.

Ο αλγόριθμος αυτός είναι κομψός, πρωτότυπος και εύκολα ελέγξιμος.

Ας σημειωθεί εδώ ότι ο έλεγχος του αν ένας αριθμός είναι πρώτος είναι απαραίτητο συστατικό μέρος της ευρύτατα χρησιμοποιούμενης μεθόδου κρυπτογραφίας RSA, που χρησιμοποιείται για την ασφάλεια ηλεκτρονικών συναλλαγών στο Διαδίκτυο.

Η ασφάλεια της μεθόδου RSA εξαρτάται από τη δυσκολία της εύρεσης πρώτων παραγόντων ενός αριθμού. Η νέα μέθοδος των τριών Ινδών, κατ' αρχήν, δεν φαίνεται να επιλύει αυτό το πρόβλημα (της παραγοντοποίησης) και έτσι η αξία της μεθόδου RSA είναι ακόμη αρκετά μεγάλη. Το επίτευγμα των ινδών επιστημόνων έχει μείζονα σημασία και για τον λόγο ότι έλαβε χώρα στην Ινδία και όχι στις «μητροπόλεις» της σύγχρονης τεχνολογίας. Το μήνυμα για τους έλληνες επιστήμονες είναι σαφές: είναι πραγματοποιήσιμη και στη χώρα μας η ποιοτικά υψηλή βασική έρευνα, αρκεί να υπάρχει ενθάρρυνση και αγάπη για αυτήν.

Είναι σημαντικό να τονισθεί το ότι το αποτέλεσμα αυτό επινοήθηκε από επιστήμονες της Πληροφορικής, και όχι από «καθαρούς» μαθηματικούς. Αλήθεια, πόση σημασία δίνει η κλασική εκπαίδευση των μαθηματικών στην Ελλάδα στα θέματα αποτελεσματικού υπολογισμού; Νομίζω ελάχιστη. Οι περισσότεροι μαθηματικοί της χώρας μας αγνοούν όχι μόνο τη σημασία των κλάσεων πολυπλοκότητας Ρ (πολυωνυμικού χρόνου) και ΝΡ (μη ντετερμινιστικού πολυωνυμικού χρόνου) αλλά και τη θεμελιώδη σημασία της Μηχανής του Τόring ως γενικού θεωρητικού προτύπου του υπολογισμού και του τι είναι δυνατόν να υπολογισθεί.

Το γεγονός ότι το επίτευγμα των τριών Ινδών έγινε σε ερευνητικό ινστιτούτο τεχνολογίας είναι ένα άλλο μήνυμα, που ίσως προκαλέσει περαιτέρω προβληματισμό (το ΙΙΤΚ της Κανπούρ είναι κάτι σαν Πολυτεχνείο - Ινστιτούτο Ερευνας, και άρχισε χωρίς προπτυχιακές σπουδές, με απευθείας προγράμματα PhD και MSc και έρευνα!). Ιστορικά, το ΙΙΤΚ έγινε με κρατική παρέμβαση το 1959, με 100 μεταπτυχιακούς φοιτητές και μικρό αριθμό καθηγητών. Από την αρχή της δημιουργίας του το ΙΙΤΚ έθεσε ως στόχο την αριστεία στην έρευνα.

Η πρόκληση που απευθύνω στους ερευνητές του ινστιτούτου που διευθύνω (ΕΑΙΤΥ) αλλά και σε όλους τους επιστήμονες Πληροφορικής εδώ, είναι με απλά λόγια: να τους μοιάσουμε! Στο πλαίσιο τέτοιων οραμάτων, ας τονισθεί ότι η συστηματική ενασχόληση με θεμελιώδη ζητήματα βασικής έρευνας στην Πληροφορική (αλλά και σε κάθε άλλον κλάδο) έχει «προστιθέμενη αξία», μεσοπρόθεσμα, για τη χώρα, ίσως πολύ μεγαλύτερη από τη γνωστή καθημερινότητα της τροποποίησης εφαρμογών.

Σημ.: Η εργασία των τριών Ινδών είναι προσπελάσιμη στην ιστοσελίδα του Τμήματος Πληροφορικής του ΙΙΤΚ ( www.cse.iitk.ac.in ).

Ο κ. Παύλος Σπυράκης είναι καθηγητής της Πληροφορικής στο Πανεπιστήμιο Πατρών και διευθυντής του Ερευνητικού Ακαδημαϊκού Ινστιτούτου Τεχνολογίας Υπολογιστών (ΕΑΙΤΥ) του υπ. Παιδείας. Είναι ένας από τους δύο αντιπροέδρους της Ευρωπαϊκής Ενωσης Επιστημόνων Θεωρητικής Πληροφορικής (EATCS) και διακεκριμένος επισκέπτης επιστήμων του Max Planck Informatik.