Saturday, May 26, 2007

Mastered the Art: Factoring Largest Special Hard-to-Factor Number


Χρειάστηκαν 11 μήνες και η συνεργασία 3 διεθνών ιδρυμάτων (Ecole Polytechnique Federale de Lausanne - EPFL, the University of Bonn, NTT- Japan), κατάφεραν όμως τελικά να αναλύσουν σε γινόμενο πρώτων παραγόντων έναν αριθμό με 307 ψηφία.
Πρόκειται για τον (21039-1), και αυτό που αυξάνει περισσότερο την δυσκολία είναι ότι βρίσκεται πολύ κοντά σε δύναμη του 2.

Η παραγοντοποίηση έγινε δυνατή χάρη σε ένα κόσκινο, ή αλλιώς τον αλγόριθμο special number field sieve (SNFS), ο οποίος αναπτύχθηκε το 1988, εδώ το επίσημο site, εδώ η σχετική καταχώρηση στην wikipedeia - ευτυχώς για όλους μας, η ομορφιά των Μαθηματικών βρίσκεται στα ίδια τα Μαθηματικά και όχι σε περιγραφές/περιλήψεις.



Βέβαια για όσους χρειάζονται και εφαρμοσμένη αξία υπάρχει και μάλιστα για έναν τομέα που θεωρείται προτεραιότητας: information security. Στην εποχή λοιπόν που τόσα πολλά εξαρτώνται από την καλά κρυπτογραφημένη πληροφορία, φαίνεται μια πιθανή ρωγμή - κυρίως όσον αφορά τεχνικές που βασίζονται σε 1024-bit encryption και ειδικά τον αλγόριθμο RSA
(όπου για την κρυπτογράφηση χρησιμοποιείται ένας μεγάλος σύνθετος αριθμός, γινόμενο δυο μεγάλων πρώτων με περίπου 150 ψηφία ο καθένας).

Φυσικά με τόσο μεγάλο "εφαρμοσμένο" ενδιαφέρον, η ρωγμή ήδη πιστεύω να έχει καλυφτεί ή τέλος πάντων να έχουν ξεκινήσει την σχετική σοβαρή μελέτη.



*O τίτλος στα πλαίσια του "τα μαθηματικά και η μουσική είναι κοντινοί συγγενείς",
Μastered the Αrt by Greyboy, Nicola Conte remix.


4 comments:

ovi said...

Αυτό μάλλον είναι συνέχεια προηγουμένου ...comment!!! ‘ξαναπερνάς από εδώ’, εγώ λυπάμαι που για λίγο άφησα την ...κατασκήνωση που είχα κάνει εδώ!!! Πολλά φιλιά!!!

Citronella said...

Αυτό που εύχομαι βασικά είναι..να λείπεις για καλό σκοπό, και το μπλογκ εδώ είναι:))
Πολύ χάρηκα Θάνο, και τα καλύτερα θα 'ρθουν! Φιλιά, καλό σ-κ!

guitarlikas said...

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

Citronella said...

Με μεγάλη μου χαρά, έτσι κι αλλιώς από καιρό ήθελα να γράψω για σχετικά θεματάκια:))

Όσο για τα κόσκινα, έτσι ακριβώς είναι, στο τέλος θα μας πουν το οποιος δεν θέλει να ζυμώσει δέκα μέρες κοσκινίζει;Ρ

 

Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 2.5 License.