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

Το γνωρίζατε ότι η ασφάλειά σας στο Διαδίκτυο βασίζεται στη μαγεία των πρώτων αριθμών; Αυτοί οι ιδιαίτεροι αριθμοί χρησιμοποιούνται στην κρυπτογράφηση δημοσίου κλειδιού, τόσο στον αλγόριθμο 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

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s