#
# Άσκηση: (προσδιορισμός της άσκησης με αναφορά στην ημερομηνία της διάλεξης όπου ανατέθηκε, ή με άλλη περιγραφή)
#
# Ονόματα φοιτητών: Όνομα και ΑΜ 1, Όνομα και ΑΜ 2, κλπ (στείλτε μόνο μια φορά το αρχείο για κάθε ομάδα)
#
# Περιγράψτε στις επόμενες γραμμές σε ποια μεταβλητή (ή καλώντας ποια συνάρτηση)
# βρίσκει κανείς το αποτέλεσμα του προγράμματός σας.
# Αν πρόκειται για κάτι ποιο σύνθετο, περιγράψτε το επαρκώς.
#
#
#
# Στείλτε το αρχείο αυτό στο email probapp@fourier.math.uoc.gr
# Ως αποστολέας θα πρέπει να φαίνεται το πλήρες σας όνομα και η αποστολή να είναι
# από το Πανεπιστημιακό σας email, αλλιώς δε θα γίνει δεκτό.
#
# Γράψτε το πρόγραμμά σας από δω και κάτω. Αν υπάρχουν συνοδευτικά αρχεία επισυνάψτε τα.
#
#


"""
Γράψτε τις δύο συναρτήσεις που λείπουν ώστε το πρόγραμμά σας
να υπολογίζει την ποσότητα a^k mod m, όπως το περιγράψαμε στο μάθημα.
"""
import time

def modpowertwo(a, r, m):
    """
    Επιστρέφει την ποσότητα a^(2^r) mod m, που πρέπει
    να είναι ένας από τους αριθμούς 0, 1, ..., m-1.
    Ο ακέραιος r πρέπει να είναι μη αρνητικός.
    Ο ακέραιος a είναι ένας από τους 0, 1, ..., m-1.
    Δε χρησιμοποιεί την ύψωση σε δύναμη της python.
    Υπολογίζει το ζητούμενο με r διαδοχικούς τετραγωνισμούς,
    όπως το εξηγήσαμε
    στο μάθημα και όπως φαίνεται στις σημειώσεις.
    """
    result=a
    for i in range(r):
        result *= result
        result = result % m
    return result
    

def modpower(a, k, m):
    """
    Επιστρέφει την ποσότητα a^k mod m, που πρέπει
    να είναι ένας από τους αριθμούς 0, 1, ..., m-1.
    Ο ακέραιος a είναι ένας από τους 0, 1, ..., m-1.
    Ο ακέραιος k είναι μη αρνητικός.
    Καλεί κάποιες φορές την προηγούμενη συνάρτηση modpowertwo
    (το πολύ τόσες φορές όσα τα δυαδικά ψηφία του k) και
    εκτελεί και άλλους τόσους πολλαπλασιασμούς.
    """
    if k==0: return 1
    if k==1: return a
    h = k//2 # υπόλοιπο διαίρεσης δια 2
    x = modpower(a, h, m)
    if k%2==0:
        return (x*x) % m
    else:
        return a * ((x*x) % m) % m
    
# Δοκιμές και συγκρίσεις.
# Μη σβήσετε τίποτα από δω και κάτω (μπορείτε να τα αλλάξετε προσωρινά
# αλλά στο πρόγραμμα που θα υποβάλετε θα πρέπει να είναι μέσα ως έχουν εδώ).
# Οι γραμμές που ακολουθούν δοκιμάζουν τις συναρτήσεις που γράψατε.

base = 5
exponent = 10**7
modulus = 9

start = time.time()
x = modpower(base, exponent, modulus)
end = time.time()
print(f"Η συνάρτησή μας τελείωσε σε {end-start} sec με αποτέλεσμα {x}.")

start = time.time()
y = base**(exponent) % modulus
end = time.time()
print(f"Η συνάρτησή μας τελείωσε σε {end-start} sec με αποτέλεσμα {y}.")