Η ομορφιά στην αναζήτηση πρώτων αριθμών!

ΑΕΙ, Γενικά Leave a comment

Το γνωρίζατε ότι η ασφάλειά σας στο Διαδίκτυο βασίζεται στη μαγεία των πρώτων αριθμών; Αυτοί οι ιδιαίτεροι αριθμοί χρησιμοποιούνται στην κρυπτογράφηση δημοσίου κλειδιού, τόσο στον αλγόριθμο RSA όσο και στην μελέτη  Ελλειπτικών Καμπύλων. Τα  παραπάνω μας επιτρέπουν να δημιουργούμε γρίφους, οι  οποίοι είναι εύκολο να λυθούν εάν γνωρίζουμε ένα «μυστικό», αλλά εξαιρετικά δύσκολο εάν αυτό το «μυστικό», είναι άγνωστο σε εμάς. Ουσιαστικά, δημιουργούμε ένα ιδιωτικό κλειδί (private key) και ένα δημόσιο κλειδί (public key), ώστε όταν υπογράφουμε (ή κρυπτογραφούμε) κάτι με το ιδιωτικό κλειδί, να μπορούμε να αποδείξουμε ότι το υπογράψαμε με το δημόσιο κλειδί.

Η μαγεία έγκειται στα πεπερασμένα σώματα, όπου μπορούμε να εφαρμόσουμε μαθηματικές πράξεις σε τιμές χρησιμοποιώντας το υπόλοιπο (modulo) ενός πρώτου αριθμού (mod p). Και, έτσι, ισχύουν τα παρακάτω [δείτε εδώ ένα παράδειγμα]:

{a\;(\bmod\; p)*b\;(\bmod\; p)=ab\;(\bmod\; p)}\\ {a\;(\bmod\; p)+b\;(\bmod\; p)=(a+b)\;(\bmod\;p)}\\ {a\;(\bmod\; p)-b\;(\bmod\; p)=(a-b)\;(\bmod\;p)}

όπου (mod p) είναι το υπόλοιπο ακέραιας διαίρεσης. Για την πράξη (mod p) ισχύουν οι ιδιότητες [δείτε εδώ]:

Προσεταιριστική ιδιότητα:

{a+(b+c)\;(\bmod\; p)=(a+b)+c\;(\bmod\; p)}\\ {(a*(b*c))\;(\bmod\; p)=((a*b)*c)\;(\bmod\; p)}

Αντιμεταθετική ιδιότητα:

{(a+b)\;(\bmod\; p)=(b+a)\;(\bmod\; p)}\\ {(a*b)\;(\bmod\; p)=(b*a)\;(\bmod\; p)}

Επομένως, το ερώτημα που τίθεται είναι, πώς μπορούμε να αναζητήσουμε πρώτους αριθμούς; Ένας από τους πιο αποδοτικούς τρόπους για να βρούμε όλους τους πρώτους αριθμούς μέχρι μία ορισμένη τιμή είναι η μέθοδος του κοσκίνου – γνωστή και ως κόσκινο του Ερατοσθένη. Στη μέθοδο αυτή, παρατάσσουμε όλους τους αριθμούς από το 2 και μετά, και στη συνέχεια απορρίπτουμε τα πολλαπλάσια του 2, του 3, του 4, του 5 και ούτω καθεξής, έως ότου μας μείνουν οι πρώτοι αριθμοί:

File:Sieve of Eratosthenes animation.gif
Πηγή: Wikimedia Commons

Ας δούμε τώρα ένα αποδοτικό κόσκινο γραμμένο σε Python. Θα ξεκινήσουμε με μία ακολουθία περιττών αριθμών (αφού μπορούμε αυτόματα να απορρίψουμε τους άρτιους) και έπειτα θα ακολουθήσουμε την ίδια πορεία όπως προηγουμένως:

import sys

test=1000

if (len(sys.argv)>1):
test=int(sys.argv[1])

def sieve_for_primes_to(n):
  size = n//2
  sieve = [1]*size
  limit = int(n**0.5)
  for i in range(1,limit):
    if sieve[i]:
      val = 2*i+1
      tmp = ((size-1) - i)//val 
      sieve[i+val::val] = [0]*tmp
  return [2] + [i*2+1 for i, v in enumerate(sieve) if v and i>0]

print sieve_for_primes_to(test)
Μπορείτε να δείτε το πως τρέχει ο κώδικας εδώ

Αυτό λειτουργεί, γιατί ξεκινάμε με όλους τους περιττούς αριθμούς. Εάν έχουμε τους αριθμούς μέχρι το 100, τότε θα μείνουμε με 50 περιττούς αριθμούς. Ξεκινάμε λοιπόν, με την ακολουθία των περιττών αριθμών, ως εξής:

3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 .. 99

Στην πρώτη εκτέλεση του βρόχου, το i ισούται με 1, οπότε κάθε φορά θα προσπερνάμε 3 αριθμούς και θα τους μαρκάρουμε ως μη-πρώτους:

3 5 7 -9- 11 13 -15- 17 19 -21- 23 25 -27- 29 31 -33- 35 .. 97 99

Έτσι, απορρίπτουμε όλους τους αριθμούς που διαιρούνται με το 3. Στη επόμενη εκτέλεση του βρόχου, θα προσπερνάμε 5 αριθμούς, ξεκινώντας από το 5 (οπότε θα απορρίπτουμε όλους τους αριθμόυς που διαιρούνται με το 5):

3 5 7 X 11 13 -X- 17 19 X 23 -25- X 29 31 X -35- .. 97 X

Στην επόμενη εκτέλεση του βρόχου, θα προσπερνάμε 7 αριθμούς, ξεκινώντας από το 7:

3 5 7 X 11 13 X 17 19 X 23 X X 29 31 X X .. 97 99

Στην επόμενη εκτέλεση του βρόχου, θα προσπερνάμε 9 αριθμούς, ξεκινώντας από το 9:

3 5 7 X 11 13 X 17 19 X 23 X X 29 31 X X .. 97 99

Στο τέλος, σταματάμε στο 19, και με βήμα 19, και προσθέτουμε το 2 στους πρώτους αριθμούς που βρήκαμε:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

Το μαρκάρισμα των αριθμών ακολουθεί την παρακάτω διαδικασία:

[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35 .. ]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0]
[1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0]
[1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0]
[1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0]
[1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0]
[1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0]
[1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0]

Συμπεράσματα

Και το ρητορικό ερώτημα που τίθεται, είναι μαγικοί οι πρώτοι αριθμοί;

Γράφει ο: Prof Bill Buchanan OBE, Professor of Cryptography

Μετάφραση-Επιμέλεια: Χρήστος Λοΐζος,  Χρήστος Κατσανδρής

Πηγή: medium.com

Leave a Reply