Οδηγός Μελέτης - Εισαγωγή στον Προγραμματισμό

Α15.17 · Παραγοντοποίηση ημιπρώτων (factor)

Εργασία 1 (2024-25), Άσκηση 3 (Bonus) · Δυσκολία ★★★ · programming · Κεφάλαια: 15, 16, 2

Παραγοντοποίηση (factor - Bonus 50 Μονάδες)

Αυτή η άσκηση είναι Bonus, δηλαδή η λύση της δεν είναι απαραίτητη για να πάρει κάποιος/α όλες τις μονάδες της Εργασίας 1. Οι μονάδες από την όποια υποβολή για αυτήν την άσκηση θα προστεθούν στον τελικό σας βαθμό του μαθήματος που περιλαμβάνει τις ασκήσεις.

Κάθε μη πρώτος (σύνθετος/composite) αριθμός μπορεί να γραφτεί σαν γινόμενο δύο ή περισσότερων πρώτων αριθμών. Επομένως η παραγοντοποίηση (factorization) ενός φυσικού αριθμού n είναι το πρόβλημα της εύρεσης των πρώτων παραγόντων που το γινόμενό τους μας δίνει το n. Για παράδειγμα, η παραγοντοποίηση του αριθμού \(42\) είναι \(2\cdot 3 \cdot 7\). Συγκεκριμένα, σε αυτήν την άσκηση θα ασχοληθούμε με την παραγοντοποίηση μιας συγκεκριμένης κατηγορίας σύνθετων αριθμών, τους ημιπρώτους (semiprimes).

Ορισμός 6. Ένας φυσικός αριθμός λέγεται ημιπρώτος (semiprime), όταν είναι το γινόμενο ακριβώς δύο πρώτων αριθμών. Για παράδειγμα, ο αριθμός \(46\) είναι semiprime (\(2\cdot 23\)) όπως και ο αριθμός \(9\) (\(3\cdot 3\)). Αντίθετα, ο αριθμός \(42\) δεν είναι semiprime.

Το πρόβλημα φαίνεται απλό, αλλά κανείς δεν έχει βρει μέχρι στιγμής αποδοτική λύση, και σε αυτό στηρίζεται η ασφάλεια του RSA. Σε αυτήν την άσκηση λοιπόν, καλείστε να γράψετε ένα αποδοτικό πρόγραμμα το οποίο να παραγοντοποιεί ημιπρώτους (semiprimes).

Τεχνικές Προδιαγραφές

• Repository Name: progintro/hw1-<YourUsername>
• C Filepath: factor/src/factor.c
• Το πρόγραμμά θα πρέπει να παίρνει ένα όρισμα από την γραμμή εντολών στην μορφή ./factor semiprime, με το πρώτο (semiprime) να είναι ο ημιπρώτος που θέλουμε να παραγοντοποιήσουμε. Αν το πρόγραμμα εκτελεστεί με ορίσματα που δεν ακολουθούν τις παραπάνω προδιαγραφές, πρέπει να εκτυπώσει αντίστοιχο μήνυμα όπως στα παρακάτω παραδείγματα και να επιστρέφει με κωδικό εξόδου (exit code) 1.
• Όλοι οι δεκαδικοί ακέραιοι που θα δοθούν στο πρόγραμμά σας θα είναι ημιπρώτοι και στο εύρος: \([0, 2^{127}]\). Για οποιαδήποτε άλλη είσοδο, το πρόγραμμά σας πρέπει να τερματίζει με κωδικό εξόδου 1.
• Το αρχείο C που θα υποβληθεί πρέπει να μεταγλωττίζεται χωρίς ειδοποιήσεις για λάθη και με κωδικό επιστροφής (exit code) που να είναι 0. Συγκεκριμένα, το αρχείο σας πρέπει να μπορεί να μεταγλωττιστεί επιτυχώς με την ακόλουθη εντολή σε ένα από τα μηχανήματα του εργαστηρίου (linuxXY.di.uoa.gr): gcc -O3 -Wall -Wextra -Werror -o factor factor.c -lm
• Μορφοποίηση: το αρχείο που θα υποβληθεί πρέπει να έχει μορφοποίηση σύμφωνη με το C/C++ στυλ της Google. Για να μορφοποιήσετε το αρχείο σας, μπορείτε να τρέξετε την ακόλουθη εντολή: clang-format -i -style=Google factor.c σε έναν υπολογιστή εργαστηρίου. Μη μορφοποιημένα προγράμματα δεν θα εξεταστούν.
• README Filepath: factor/README.md
• Ένα αρχείο που να περιέχει ένα στοιχείο εισόδου και ένα εξόδου *διαφορετικά* από αυτά της εκφώνησης. Συγκεκριμένα προτείνουμε να βάλετε έναν συνδυασμό που θεωρείται ότι είναι δύσκολος να γίνει σωστός κατά την υλοποίηση.
  • input Filepath: factor/test/input.txt
  • output Filepath: factor/test/output.txt

  Για παράδειγμα, το περιεχόμενο του input.txt αρχείου μπορεί να είναι: “93” και του αντίστοιχου output.txt: “3 31”. Προσοχή: αυτό το παράδειγμα δεν θα γίνει δεκτό από την άσκηση επειδή αυτό το input-output ζευγάρι υπάρχει ήδη παρακάτω, επομένως πρέπει να διαλέξετε κάποιο άλλο.

• Πρέπει να ολοκληρώνει την εκτέλεση μέσα σε: 10 δευτερόλεπτα.
• Δεν επιτρέπεται χρήση προϋπολογισμένων αποτελεσμάτων. Το πρόγραμμά σας πρέπει να υπολογίζει το αποτέλεσμα χωρίς “πρότερη γνώση”, δηλαδή χωρίς να έχετε ήδη κωδικοποιήσει παραγοντοποιήσεις ημιπρώτων που έχετε βρει από προηγούμενους υπολογισμούς σας μέσα στον κώδικα.
• Καθώς αυτή η εργασία είναι Bonus, θα ελέγξουμε και ποιοτικά χαρακτηριστικά της υποβολής. Μια ιδιαίτερα δυσνόητη ή μη διαχειρίσιμη λύση (π.χ., 6 nested if-else, 35 μεταβλητές στην ίδια συνάρτηση κτλ) θα οδηγήσει σε αφαίρεση μονάδων κατά την κρίση του εξεταστή.

Παρακάτω παραθέτουμε την αλληλεπίδραση με μια ενδεικτική λύση:

$ ./factor
Usage: ./factor <semiprime>
$ echo $?
1
$ ./factor 93
Factors: 3 31
$ echo $?
0
$ ./factor 9827348119
Factors: 613 16031563
$ # level: very hard
$ ./factor 2524891914334062643
Factors: 1175747593 2147477851
$ # level: extremely hard
$ ./factor 809724910412139638697047
Factors: 783108713587 1033987869581
$ # level: this is impossible
$ ./factor 66162145239900452012870189875803961
Factors: 206547667773749927 320323855277677343

Στο αρχείο README.md πρέπει να προσθέσετε οποιεσδήποτε παρατηρήσεις κάνατε κατά την διεκπεραίωση της άσκησης. Ο κώδικας απαιτείται να είναι καλά τεκμηριωμένος με σχόλια καθώς αυτό θα είναι μέρος της βαθμολόγησης. Οι 10 γρηγορότερες λύσεις θα μοιραστούν ένα bonus (extra) 500 μονάδων κατανεμημένων αναλογικά με τον παράγοντα \(\frac{1}{T}\) (μέχρι το max: 200 μονάδες ανά υποβολή), όπου \(T\) είναι ο συνολικός χρόνος που απαιτεί ο αλγόριθμος της υλοποίησης για να παραγοντοποιήσει όλους τους ακεραίους που του δόθηκαν. Αν δούμε μια ιδιαίτερα ενδιαφέρουσα/αποδοτική λύση, θα ζητήσουμε μια παρουσίαση από το παιδί που την υλοποίησε.

Υπόδειξη

Αριθμοί έως \(2^{127}\) δεν χωρούν σε long long: χρειάζεστε ακέραιο 128 bits (π.χ. την επέκταση __int128 του gcc) και δική σας μετατροπή από/προς δεκαδικό string, αφού η printf/strtoll δεν τον υποστηρίζουν. Η δοκιμαστική διαίρεση έως \(\sqrt{n}\) αρκεί για τα πρώτα παραδείγματα αλλά όχι για τα «very hard» και πάνω· ψάξτε πιθανοτικούς αλγορίθμους όπως τον Pollard’s rho σε συνδυασμό με έλεγχο πρώτων Miller-Rabin, και προσέξτε την υπερχείλιση στον πολλαπλασιασμό modulo.

Αριθμός στον οδηγό: Α15.17 (στο κεφάλαιο) · Μόνιμο αναγνωριστικό: hw-2024-hw1-factor · Σύνδεσμος: https://progintro.github.io/study/questions/homework/hw-2024-hw1-factor.html · Markdown (GitHub)