clasa a IX-a · Python · Prelucrări ale datelor numerice · lecția 18
Ciurul lui Eratostene și exponențierea rapidă
150 minintensiv · Pythonintensiv
Înainte de lecția asta: IX.5 Divizori, multipli, numere prime, factori primi, IX.6 cmmdc și algoritmul lui Euclid, IX.7 Baze de numerație, IX.8 Subprograme (1): definire, parametri, apel, IX.9 Subprograme (2): variabile locale și globale, funcții predefinite, IX.14 Modelul liniar: listă, stivă, coadă, listă de frecvențe
Ce vei ști după lecție
- Generezi toate numerele prime până la n cu Ciurul lui Eratostene, memorat într-o listă de valori True/False, și explici de ce tăierea pornește de la i · i.
- Compari, cu număr de pași și timp măsurat, ciurul cu testul de primalitate aplicat fiecărui număr (lecția py9-05).
- Calculezi a la puterea b (și a la puterea b modulo m) cu exponențierea rapidă, explicând rolul ridicării la pătrat și legătura cu biții exponentului.
- Aplici cei doi algoritmi într-un sistem RSA simplificat, la codificarea culorilor prin produs de numere prime și la calculul unor coduri de autentificare.
Lecția are și o fișă de lucru, de rezolvat după ce o citești. Mergi la fișă ↓
Clasa a IX-aLecția 18 din 21 · mai sunt 3Urmează: IX.19 · Clasa list, în profunzime, și tablourile din C++Vezi toate lecțiile
Cuprins
- Ciurul lui Eratostene: ideea
- Codul și cele două „de ce” cu i · i
- Ciur sau test de primalitate?
- Exponențierea rapidă
- Puteri modulo m: a ** b % m sau pow(a, b, m)
- Aplicație: un sistem RSA simplificat
- Aplicație: culorile unui tablou, codificate prin produs de prime
- Verifică-te
- Fișa de lucru
- Probleme de lucru
- Temă
- Răspunsuri
Fișiere PDF și de lucru
- Lecția în PDF
versiunea de printat
- Fișa de lucru: Ciurul lui Eratostene și exponențierea rapidă
6 pagini · 150 min
1. Ciurul lui Eratostene: ideea
În lecția py9-05 ai verificat dacă un număr este prim. Dacă îți trebuie toate primele până la n (de exemplu, ca să alegi coduri, chei sau identificatori), nu mai testezi fiecare număr: le scrii pe toate și tai multiplii.
Reprezentarea datelor: o listă e cu n + 1 valori, în care indicele este numărul, iar valoarea spune dacă numărul este (încă) candidat la prim: e[7] == True înseamnă „7 n-a fost tăiat”.
- Inițializare: toate valorile
True, apoie[0] = e[1] = False. - Eliminare: iei pe rând
i = 2, 3, 4, …. Dacăin-a fost tăiat, este prim, și îi tai toți multiplii. - Lista finală: indicii rămași
Truesunt exact numerele prime.
Evoluția pentru n = 30 (am afișat doar numerele tăiate pentru prima dată la fiecare etapă):
| Etapa | Ce se taie nou | Rămân (după etapă) |
|---|---|---|
i = 2 |
4, 6, 8, …, 30 (14 numere) | 2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29 |
i = 3 |
9, 15, 21, 27 | 2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29 |
i = 5 |
25 | 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 |
La i = 4 nu se întâmplă nimic (4 e deja tăiat), iar la i = 6 ciurul se oprește, pentru că 6 · 6 = 36 > 30.
De ce rămân doar prime? Un număr compus x are un divizor prim p < x. Când ciurul ajunge la p, îl taie pe x ca multiplu al lui p. Un număr prim nu are divizori mai mici (în afară de 1), deci nu îl taie nimeni.
2. Codul și cele două „de ce” cu i · i
def ciur(n):
e = [True] * (n + 1) # e[k] spune dacă k este prim
e[0] = e[1] = False
i = 2
while i * i <= n:
if e[i]: # i a rămas netăiat, deci e prim
for j in range(i * i, n + 1, i):
e[j] = False # tai multiplii lui i
i += 1
return e
e = ciur(50)
prime = [k for k in range(len(e)) if e[k]] # k din 0..50, păstrat dacă e[k] este True (vezi py9-13, §4)
print(prime) # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
print(sum(ciur(100))) # 25: True contează ca 1, deci sunt 25 de prime ≤ 100De ce tăierea pornește de la i · i , nu de la 2 · i? Multiplii mai mici ai lui i, adică 2i, 3i, …, (i − 1)i, au un factor mai mic decât i și au fost deja tăiați la o etapă anterioară. Exemplu: la i = 5, numerele 10, 15, 20 au fost tăiate de 2 sau de 3; primul multiplu „nou” este 25.
De ce bucla exterioară se oprește când i · i > n? Pentru că un i mai mare ar începe tăierea de la i · i > n, deci n-ar mai tăia nimic. Altfel spus: orice compus x ≤ n are un factor prim cel mult √x ≤ √n (aceeași idee ca la divizori, în py9-05).
Pentru n = 10⁶, varianta „i până la n, tăiere de la 2i ” face 2 775 210 atribuiri e[j] = False, iar varianta de mai sus 2 122 048; ambele găsesc aceleași 78 498 de prime. Economia e mică (cele mai multe tăieri le fac 2 și 3), dar argumentul cu i · i este cel care justifică oprirea la √n.
3. Ciur sau test de primalitate?
Varianta „din py9-05”: pentru fiecare x de la 2 la n apelezi o funcție prim(x) care caută un divizor până la √x. Am numărat împărțirile, respectiv tăierile, și am măsurat timpul (pe calculatorul de test; la tine valorile vor fi altele, raportul asemănător).
| n | Împărțiri (test pentru fiecare x) | Tăieri (ciur) | Timp test | Timp ciur |
|---|---|---|---|---|
| 10⁵ | 2 745 694 | 193 078 | ≈ 0,2 s | ≈ 0,01 s |
| 10⁶ | 67 740 404 | 2 122 048 | ≈ 6,5 s | ≈ 0,2 s |
Intuitiv: testul face pentru fiecare număr prim până la √x pași, deci cam n · √n în total. Ciurul trece pe la fiecare număr de câteva ori (o dată pentru fiecare factor prim mic), deci face doar ceva mai mult de n pași. Prețul ciurului este memoria: o listă cu n + 1 valori. Pentru n = 10⁶ e în regulă; pentru n = 10¹² nu.
Sfat
Un singur număr mare (ex. 10¹²) → testul până la √n. Multe întrebări până la o limită rezonabilă → ciurul, construit o singură dată; apoi e[x] răspunde instantaneu.
4. Exponențierea rapidă
Calculul clasic al lui aᵇ face b − 1 înmulțiri. Observația cheie: la exponent par, ridici la pătrat.
bpar:aᵇ = (a²)^(b/2)(exponentul se înjumătățește cu o singură înmulțire,a · a);bimpar:aᵇ = a · a^(b−1), iarb − 1este par.
Varianta iterativă parcurge biții exponentului de la dreapta la stânga: a devine pe rând a, a², a⁴, a⁸, …, iar în rezultat intră doar puterile pentru care bitul este 1. Pentru 13 = 1101₂: 3¹³ = 3⁸ · 3⁴ · 3¹.
def putere(a, b):
r = 1
while b > 0:
if b % 2 == 1: # ultimul bit al lui b este 1
r = r * a # puterea curentă intră în rezultat
a = a * a # a, a², a⁴, a⁸, ...
b = b // 2 # trec la bitul următor
return r
print(putere(3, 13), 3 ** 13) # 1594323 1594323b (baza 10) |
b (baza 2) |
a |
r după pas |
|---|---|---|---|
| 13 | 1101 | 3 | 3 |
| 6 | 110 | 9 | 3 |
| 3 | 11 | 81 | 243 |
| 1 | 1 | 6561 | 1594323 |
Numărul de pași = numărul de cifre binare ale lui b (vezi py9-07), adică aproximativ log₂ b.
Exponent b |
Înmulțiri, metoda clasică | Pași (biți), metoda rapidă | Înmulțiri executate de putere |
|---|---|---|---|
| 13 | 12 | 4 | 7 |
| 1 000 | 999 | 10 | 16 |
| 10⁶ | 999 999 | 20 | 27 |
| 10¹⁸ | aproape 10¹⁸ | 60 | 84 |
5. Puteri modulo m: a ** b % m sau pow(a, b, m)
În criptare și autentificare nu interesează numărul uriaș aᵇ, ci doar restul lui la un m. Regula care ne salvează: restul unui produs se poate calcula din resturile factorilor, deci aplici % m după fiecare înmulțire și numerele rămân mici.
def putere_mod(a, b, m):
r = 1
a = a % m
while b > 0:
if b % 2 == 1:
r = r * a % m
a = a * a % m
b = b // 2
return r
M = 1000000007
print(putere_mod(7, 10**6, M), pow(7, 10**6, M), 7 ** 10**6 % M)
# 880007888 880007888 880007888Metodă ( 7 la puterea b , modulo M) |
b = 10⁶ |
b = 10⁷ |
|---|---|---|
buclă clasică cu r = r * a % M |
≈ 0,1 s | ≈ 0,9 s |
7 ** b % M |
≈ 0,2 s | ≈ 7,3 s |
putere_mod(7, b, M) |
sub 0,001 s | sub 0,001 s |
pow(7, b, M) (predefinită) |
sub 0,001 s | sub 0,001 s |
7 ** b % M este lent nu pentru că ** ar fi naiv (Python ridică și el rapid la putere), ci pentru că întâi construiește numărul întreg: pentru b = 10⁶ el are 845 099 de cifre. pow(a, b, m) cu trei argumente face exact ce face putere_mod: exponențiere rapidă cu rest la fiecare pas.
De știut
Ce trebuie să știi să explici: (1) la exponent par se ridică la pătrat, deci exponentul se înjumătățește; (2) numărul de pași crește cu log₂ b, nu cu b; (3) restul se ia după fiecare înmulțire, ca valorile intermediare să rămână mai mici decât m².
Context: autentificarea. Banca și aplicația ta cunosc un secret k. Banca trimite un număr aleator c (provocarea), aplicația răspunde cu pow(c, k, m), iar banca verifică același calcul. Secretul nu circulă niciodată prin rețea, iar calculul durează microsecunde chiar pentru exponenți uriași.
6. Aplicație: un sistem RSA simplificat
RSA folosește exact cei doi algoritmi: numere prime pentru chei și exponențiere rapidă modulo pentru criptare. Iată versiunea „de jucărie”, cu numere mici.
- Alegi două prime (din ciur):
p = 61,q = 53. Calculezin = p · q = 3233șiφ = (p − 1)(q − 1) = 3120. - Alegi
e = 17(prim cu 3120:gcd(17, 3120) = 1, vezi py9-06). Cheia publică este(e, n). - Cauți cheia privată
dastfel încâtd · e % φ == 1. Pentru numere mici, o căutare simplă ajunge. - Criptare:
c = pow(x, e, n). Decriptare:x = pow(c, d, n).
p, q = 61, 53
n, phi = p * q, (p - 1) * (q - 1)
e = 17
d = 1
while d * e % phi != 1:
d += 1
print(n, phi, e, d) # 3233 3120 17 2753
mesaj = "SALUT"
c = [pow(ord(ch), e, n) for ch in mesaj] # codul fiecărei litere, criptat
print(c) # [2680, 2790, 2726, 2310, 2159]
print("".join(chr(pow(x, d, n)) for x in c)) # SALUT
# `for x in c` fără paranteze pătrate: aceeași idee ca la liste, dar `join` consumă elementele pe rândDe ce e greu de spart? Ca să afle d din cheia publică (17, 3233), atacatorul are nevoie de p și q. Pe 3233 îl descompune într-o clipă (py9-05), dar în RSA-ul real n are sute de cifre: înmulțirea e ușoară, descompunerea practic imposibilă.
Atenție — greșeli frecvente
Codul fiecărei litere trebuie să fie mai mic decât n (aici 65–90 < 3233), altfel decriptarea dă alt rest. Criptarea literă cu literă e doar un exercițiu: aceeași literă dă mereu același număr.
7. Aplicație: culorile unui tablou, codificate prin produs de prime
Un muzeu vrea să memoreze ce culori apar într-un tablou printr-un singur număr. Dă fiecărei culori un prim diferit (primele prime din ciur), iar tabloul primește produsul culorilor lui. Decodificarea se face prin împărțiri: culoarea cu primul p apare exact când p divide codul.
culori = ["roșu", "galben", "albastru", "verde", "alb", "negru"]
e = ciur(20)
prime = [k for k in range(len(e)) if e[k]][:len(culori)] # [2, 3, 5, 7, 11, 13]
def codifica(lista):
c = 1
for nume in lista:
c *= prime[culori.index(nume)]
return c
def decodifica(c):
rez = []
for k in range(len(culori)):
if c % prime[k] == 0:
rez.append(culori[k])
c //= prime[k]
return rez
t1 = codifica(["roșu", "albastru", "alb"])
t2 = codifica(["galben", "albastru", "alb", "negru"])
print(t1, decodifica(t1)) # 110 ['roșu', 'albastru', 'alb']
print(t2, decodifica(t2)) # 2145 ['galben', 'albastru', 'alb', 'negru']De ce merge? Descompunerea în factori primi este unică, deci două mulțimi diferite de culori dau mereu produse diferite. Bonus: gcd(110, 2145) = 55 = 5 · 11 dă culorile comune (albastru, alb), iar cel mai mic multiplu comun 4290 dă toate culorile celor două tablouri.
8. Verifică-te
- În ciurul pentru
n = 50, ce număr se taie primul la etapai = 7? Se mai execută etapai = 8? - Ce valoare are
e[1]după ciur și de ce trebuie pusă explicit? - Câți pași face bucla din
putere(a, b)pentrub = 64? Dar pentrub = 63? - Scrie
2²⁰ca produs de pătrate succesive, așa cum îl calculeazăputere. - De ce
pow(a, b, m)este de preferat luia ** b % mcândbeste foarte mare? - În RSA-ul din secțiunea 6, cineva primește numărul
2680. Ce calcul face ca să afle litera, dacă știe cheia privată? - Un tablou are codul
78. Ce culori conține?
Fișa de lucru
Ai citit lecția? Printează fișa sau deschide-o pe ecran și rezolvă exercițiile în ordine.
Fișă de lucru · 6 pagini · 150 min
Ciurul lui Eratostene și exponențierea rapidă
- Urmărești evoluția listei din ciur și a variabilelor din exponențierea rapidă, pas cu pas.
- Repari ciururi și funcții de putere cu greșeli realiste (limite, ordinea instrucțiunilor, împărțire reală).
- Scrii programe care folosesc ciurul construit o singură dată și puterile modulo m în contexte de identificare, criptare și autentificare.
- Argumentezi, cu număr de pași și memorie, când alegi ciurul și când testul de primalitate.
Te-ai blocat la un exercițiu?
Probleme de lucru
Începe cu acestea, în ordine. Problemele se deschid pe pbinfo.ro, unde trimiți soluția și primești punctajul.
- ușoară
eratostene#303
https://www.pbinfo.ro/probleme/303/eratostene
expon#3977
https://www.pbinfo.ro/probleme/3977/expon
Temă
Rezolvă-le singur și bifează ce ai terminat. Bifele rămân salvate în acest browser.
Te-ai blocat la lecția asta?
Scrie-mi ce nu iese și vedem împreună de unde se blochează.
Răspunsuri
49 = 7 · 7. Nu:8 · 8 = 64 > 50, bucla se oprește.False. Inițializarea puneTruepeste tot, iar 1 nu are niciun divizor prim care să-l taie; la fel 0.- 7 pași pentru
64 = 1000000₂(7 biți) și 6 pași pentru63 = 111111₂(6 biți). Deși 63 < 64, la 63 se fac mai multe înmulțiri (12 față de 8), pentru că fiecare bit este 1. 20 = 10100₂, deci2²⁰ = 2¹⁶ · 2⁴;atrece prin2, 2², 2⁴, 2⁸, 2¹⁶.- Pentru că
powia restul după fiecare înmulțire și face doar ~log₂ bpași, pe cânda ** bconstruiește întâi un număr cu milioane de cifre. chr(pow(2680, 2753, 3233)), care dăS.78 = 2 · 3 · 13: roșu, galben, negru.