← Lekcje
Python · lekcja 21

Pierwsze i złożone

Liczby pierwsze, część 1 z 3

  1. Liczba złożona, liczba pierwsza i dziwny przypadek liczby 1
  2. Podstawowe twierdzenie arytmetyki i rozkład na czynniki pierwsze
  3. Rodziny liczb pierwszych: bliźniacze, czworacze, liczby Mersenne'a
  4. Po co informatyce liczby pierwsze? Szyfrowanie i anagramy

Podręcznik „Informatyka na czasie 2”: s. 117–120. Dziś bez pisania kodu.

Rozgrzewka · 3 minuty

Co zostało z programu Zamiana?

Wracamy do programu, który zamieniał liczbę dziesiętną na dwójkową.

  1. Ile wynosi 123 // 2, a ile 123 % 2? Co liczy każdy z tych dwóch operatorów?
  2. Program zapisywał kolejne reszty z dzielenia do listy. Jaki numer ma pierwsze miejsce w liście?
  3. Dlaczego na końcu program wypisywał zawartość listy od tyłu, a nie od początku?
podręcznik Informatyka na czasie 2, s. 111–115 (7.4 Program zamieniający liczbę dziesiętną na binarną)
Część 1 · Dwie rodziny liczb

Liczby złożone i liczby pierwsze

Liczby złożone to dodatnie liczby naturalne, które można przedstawić w postaci iloczynu liczb naturalnych mniejszych od nich: 9 = 3 · 3, 10 = 2 · 5, 120 = 2 · 3 · 4 · 5, 1115 = 3 · 5 · 7 · 11.

Liczba pierwsza to liczba większa od 1, która jest podzielna wyłącznie przez 1 i przez samą siebie. To jak paczka cukierków: 12 cukierków rozdacie po równo między 2, 3, 4 albo 6 osób, a 13 cukierków po równo tylko wtedy, gdy osoba jest jedna albo jest ich trzynaście. Dlatego 12 jest złożona, a 13 pierwsza.

Liczba 1 jest wyjątkowa. Przez setki lat uważano ją za liczbę pierwszą. Dziś przyjmuje się, że nie jest ani pierwsza, ani złożona.

Podręcznik Informatyka na czasie 2, s. 117 (8.1 Liczby złożone i liczby pierwsze, pojęcia z marginesu: liczby złożone, liczba pierwsza, ramka „Warto wiedzieć” o liczbie 1)
Część 1 · Ile ich jest?

Dwadzieścia pięć liczb do stu

Wśród liczb mniejszych od 100 jest dwadzieścia pięć liczb pierwszych: 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.

Liczby pierwsze mniejsze od 100 (pomarańczowe tło): jest ich 25 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
Podręcznik Informatyka na czasie 2, s. 117 (8.1 Liczby złożone i liczby pierwsze, rys. 8.1 Liczby złożone i liczby pierwsze mniejsze niż 100)
Część 2 · Rozkład na czynniki

Każda liczba z liczb pierwszych

Podstawowe twierdzenie arytmetyki mówi: każda liczba naturalna większa od 1 jest albo liczbą pierwszą, albo iloczynem liczb pierwszych. Ten iloczyn nazywamy rozkładem na czynniki pierwsze i każda liczba ma tylko jeden własny rozkład. Dzielimy liczbę przez najmniejszą liczbę pierwszą, która ją dzieli, i powtarzamy to z wynikiem, aż zostanie 1.

36 18 9 3 1 2 2 3 3 36 = 2 · 2 · 3 · 3 87 29 1 3 29 87 = 3 · 29 186 93 31 1 2 3 31 186 = 2 · 3 · 31

Nazwijmy to po imieniu. Po każdym dzieleniu zostaje mniejsza liczba i dokładnie to samo zadanie: rozłóż ją na czynniki. Takie mniejsze zadanie tej samej postaci nazywamy podproblemem, a metodę „wykonaj jeden krok, a z resztą zrób to samo” nazywamy rekurencją. Kończy się ona wtedy, gdy zostaje 1, bo tu nie ma już czego dzielić.

Podręcznik Informatyka na czasie 2, s. 117 i 120 (8.1 Liczby złożone i liczby pierwsze, podstawowe twierdzenie arytmetyki, pojęcie z marginesu: rozkład na czynniki pierwsze, rys. 8.2 Rozkład liczb 36, 87 i 186 na czynniki pierwsze) · podproblem i rekurencja („jeśli nadal to możliwe, wyróżnij czynność powtarzaną, wykonaj ją, a z resztą zrób to samo”): podstawa programowa informatyki, komentarz ORE 2018 · PP-INF I.3 (zakres podstawowy)
Część 2 · Rodziny liczb pierwszych

Bliźniacze, czworacze i Mersenne'a

Euklides udowodnił w IV wieku przed naszą erą, że liczb pierwszych jest nieskończenie wiele. Do dziś nie znamy wzoru, który dla dowolnej liczby n poda od razu n-tą liczbę pierwszą, więc matematycy opisują je rodzinami.

2 najmniejsza i jedyna parzysta liczba pierwsza 41 43 liczby bliźniacze: ich różnica wynosi 2 11 13 17 19 liczby czworacze: p, p+2, p+6, p+8 31 = 2⁵ − 1 liczby Mersenne'a: liczby postaci 2ⁿ − 1 Każda liczba pierwsza większa od 5 kończy się cyfrą 1, 3, 7 albo 9
Podręcznik Informatyka na czasie 2, s. 118–119 (8.1 Liczby złożone i liczby pierwsze, infografika „Co warto wiedzieć o liczbach pierwszych?”)
Część 2 · Spirala Ulama

Spirala, której nikt nie wyjaśnił

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 wys: 434 Stanisław Ulam, rok 1963 Kolejne liczby naturalne wypisane spiralnie na kwadratowej tablicy. Podpisane są tylko liczby pierwsze, miejsca liczb złożonych zaznaczono kreską. Po naniesieniu bardzo wielu liczb widać linie, na których pierwszych jest więcej niż na innych.

Ulam narysował swoją spiralę, bazgrząc na kartce podczas długiego i bardzo nudnego referatu na konferencji naukowej. Policzył ręcznie kilkaset liczb i wtedy zobaczył ukośne linie. Do dziś nie wyjaśniono, dlaczego liczby pierwsze grupują się właśnie tak.

Podręcznik Informatyka na czasie 2, s. 119 (8.1 Liczby złożone i liczby pierwsze, infografika, blok o spirali Ulama) · okoliczności powstania spirali: en.wikipedia.org/wiki/Ulam_spiral
Część 3 · Zastosowanie

Anagram poznasz po iloczynie

Rozkład liczby na czynniki pierwsze jest jednoznaczny, więc iloczyn liczb pierwszych działa jak odcisk palca zestawu liter. Kolejnym literom alfabetu przypisujemy kolejne liczby pierwsze i mnożymy je w każdym wyrazie. Równe iloczyny znaczą, że wyrazy składają się z tych samych liter, czyli są anagramami.

a = 2, b = 3, c = 5 b a c 3 · 2 · 5 = 30 a b c 2 · 3 · 5 = 30 30 = 30, więc to anagramy
Podręcznik Informatyka na czasie 2, s. 119 (8.1 Liczby złożone i liczby pierwsze, infografika, blok „Jak liczby pierwsze pomagają rozpoznawać anagramy?”, przykład wyrazów „bac” i „abc”)
Część 3 · Szyfrowanie

Łatwo pomnożyć, trudno rozłożyć

Liczbę utworzoną z iloczynu dwóch dużych liczb pierwszych bardzo trudno rozłożyć z powrotem na czynniki w rozsądnym czasie, nawet najszybszym komputerem. To jak rozbicie jajka: wymieszać łatwo, złożyć z powrotem prawie się nie da.

Wykorzystali to twórcy algorytmu RSA (nazwa od nazwisk trzech autorów), którym szyfruje się komunikację w Internecie i w bankowości elektronicznej. Liczby pierwsze używane w tym algorytmie mają nawet 2048 bitów, czyli 2048 cyfr dwójkowych.

Im większa liczba, tym trudniej sprawdzić, czy jest pierwsza. Dla ogromnych liczb stosuje się test Millera-Rabina: Gary Miller stworzył go w 1976 roku, a urodzony we Wrocławiu Michael O. Rabin ulepszył w 1980. Test bywa omylny, ale szansa błędu wynosi około 1 do 10¹². Wersję dla mniejszych liczb napiszemy sami na trzeciej lekcji tego tematu.

Podręcznik Informatyka na czasie 2, s. 118–120 (8.1 Liczby złożone i liczby pierwsze, blok „Liczby pierwsze w kryptografii” i ramka „A to ciekawe” o teście Millera-Rabina)
Ćwiczenie · na kartce · 12 minut

Ćwiczenie: rozłóż i sprawdź

  1. Podpisz kartkę. Rozłóż na czynniki pierwsze liczby 60, 91 i 144: dla każdej zapisz cały łańcuch dzieleń jak w zapisie obok, a pod nim wynik jako iloczyn.
  2. Wypisz wszystkie liczby pierwsze od 40 do 70, potem sprawdź listę z siatką ze slajdu 4.
  3. Napisz jednym zdaniem, dlaczego liczba 1 nie jest liczbą pierwszą.
Zapis, którego używamy:
87 : 3 = 29
29 : 29 = 1
Wynik: 87 = 3 · 29

Kto skończy szybciej: znajdźcie w parze parę liczb bliźniaczych i czwórkę czworaczych spoza tej lekcji.

Dla chętnych (dom): rozłóż na czynniki pierwsze pięć własnych liczb i zapisz całe łańcuchy dzieleń w pliku rozklad_na_czynniki.md.

Dla najszybszych: sito Eratostenesa

Siatka liczb do 100 nie powstała przez sprawdzanie każdej liczby po kolei. Jest szybszy sposób, znany od starożytności i przypisywany Eratostenesowi z Cyreny.

  1. Wypisz liczby od 2 do n.
  2. Weź najmniejszą jeszcze niewykreśloną liczbę: to liczba pierwsza.
  3. Wykreśl wszystkie jej wielokrotności, zaczynając od jej kwadratu.
  4. Powtarzaj kroki 2 i 3, dopóki wybrana liczba nie przekroczy pierwiastka z n. Wszystko, co zostało niewykreślone, to liczby pierwsze.

Spróbuj na kartce dla n = 50: skreśl wielokrotności 2, potem 3, potem 5 i 7. Dalej nie trzeba, bo 7 · 7 = 49, a 11 · 11 to już więcej niż 50. Sita nie ma w podręczniku, mam je z pl.wikipedia.org/wiki/Sito_Eratostenesa.

Podręcznik Informatyka na czasie 2, s. 117 (rys. 8.1) i s. 120 (rys. 8.2, przykład rozkładu liczby 87)
Część 3 · Pytania kontrolne

Cztery pytania na koniec

  1. Czym różni się liczba złożona od liczby pierwszej i w którym z tych dwóch zbiorów jest liczba 1?
  2. Co mówi podstawowe twierdzenie arytmetyki i co znaczy, że rozkład na czynniki pierwsze jest jednoznaczny?
  3. Dlaczego bezpieczeństwo algorytmu RSA opiera się na liczbach pierwszych, a nie na dowolnych dużych liczbach?
  4. Co w rozkładzie liczby na czynniki jest podproblemem i jak nazywa się metoda, która tak działa?
Podręcznik Informatyka na czasie 2, s. 117–120 (8.1 Liczby złożone i liczby pierwsze) · PP-INF I.3 (zakres podstawowy)
Część 3 · Podsumowanie

A jak to wygląda w produkcji?

Na lekcjiW produkcjiStatus
Rozkład liczby na czynniki pierwsze na kartceCała ochrona danych w RSA polega na tym, że dla bardzo dużych liczb nikt nie umie zrobić tego szybko.nadal w użyciu
Liczby pierwsze o długości 2048 bitówCertyfikaty stron internetowych: Let's Encrypt przyjmuje klucze RSA o długości 2048, 3072 albo 4096 bitów, a obok nich klucze innego rodzaju, ECDSA P-256 i P-384.rozszerzane
Sprawdzanie pierwszości przez dzielenieDla liczb rzędu setek cyfr używa się testu Millera-Rabina, bo dzielenie po kolei trwałoby zbyt długo.zastępowane
Iloczyn liczb pierwszych jako odcisk zestawu literTen sam pomysł, czyli krótki odcisk zamiast całych danych, stosuje się przy porównywaniu plików i sprawdzaniu haseł.nadal w użyciu
Wiersze 1 i 3: podręcznik Informatyka na czasie 2, s. 118–120 · długości kluczy: letsencrypt.org/docs/integration-guide (sekcja o rodzajach kluczy)