Losowe pytanie od SQuAD:

Kiedy odkryto, że liczby pierwsze mogą być stosowane do tworzenia algorytmów kryptografii klucza publicznego?

Odpowiedź:

lata 70.

Pobrane zdania :

1. Jednak ta wizja została rozbita w 1970 roku, kiedy to został publicznie ogłosił, że liczby pierwsze mogą być wykorzystane jako podstawa do tworzenia algorytmów kryptograficznych kluczowych publicznych.
2. Liczby pierwsze są używane w kilku procedurach w technologii informacyjnej, takich jak kryptografia z kluczem publicznym, która wykorzystuje właściwości, takie jak trudność wliczania dużych liczb do ich czynników pierwszych.
3. Opracowano algorytmy znacznie wydajniejsze niż dzielenie próbne do testowania pierwszości dużych liczb.
4. Kilka algorytmów kryptograficznych z kluczem publicznym, takich jak RSA i wymiana kluczy Diffie-Hellman, opiera się na dużych liczbach pierwszych (na przykład 512-bitowe liczby pierwsze są często używane dla RSA, a 1024-bitowe liczby pierwsze są typowe dla Diffie-Hellmana). .
5. Liczby pierwsze są również używane w tablicach mieszających i generatorach liczb pseudolosowych.
6. Niektóre z tych liczb pierwszych zostały znalezione przy użyciu obliczeń rozproszonych.
7. Przez długi czas teoria liczb w ogólności, a badanie liczb pierwszych w szczególności, była postrzegana jako kanoniczny przykład czystej matematyki, bez zastosowań poza własnym interesem badania tego tematu, z wyjątkiem użycia liczb pierwszych zęby kół zębatych, aby równomiernie rozprowadzać zużycie.
8. Algorytmy deterministyczne pozwalają stwierdzić, czy dana liczba jest liczbą pierwszą, czy nie.
9. Wyrażenie „wszystkie możliwe algorytmy” obejmuje nie tylko algorytmy znane dzisiaj, ale każdy algorytm, który może zostać odkryty w przyszłości.
10. Na przykład dzielenie próbne jest algorytmem deterministycznym, ponieważ jeśli zostanie wykonane poprawnie, zawsze zidentyfikuje liczbę pierwszą jako pierwszą, a liczbę złożoną jako złożoną.
11. Sformułowany jako problem decyzyjny, jest to problem decydowania, czy dane wejściowe mają współczynnik mniejszy niż k. Nie jest znany żaden wydajny algorytm faktoryzacji liczb całkowitych, a fakt ten stanowi podstawę kilku nowoczesnych systemów kryptograficznych, takich jak algorytm RSA.
12. Zanim rozpoczęły się faktyczne badania, wprost poświęcone złożoności problemów algorytmicznych, różni badacze położyli liczne podwaliny.
13. Ta zasada lokalno-globalna ponownie podkreśla znaczenie liczb pierwszych w teorii liczb.
14. Algorytmy probabilistyczne są zwykle szybsze, ale nie dowodzą całkowicie, że liczba jest liczbą pierwszą.
15. Jednak najbardziej znany algorytm kwantowy dla tego problemu, algorytm Shora, działa w czasie wielomianowym.
16. Sito Eratostenesa, przypisywane Eratostenesowi, jest prostą metodą obliczania liczb pierwszych, chociaż duże liczby pierwsze znalezione dzisiaj w komputerach nie są generowane w ten sposób.
17. Problem jest uważany za z natury trudny, jeśli jego rozwiązanie wymaga znacznych zasobów, niezależnie od zastosowanego algorytmu.
18. Algorytmy wykorzystujące losowe bity nazywane są algorytmami randomizowanymi.
19. Uważa się, że jeśli problem można rozwiązać za pomocą algorytmu, istnieje maszyna Turinga, która go rozwiązuje.
20. Jednak liczby Carmichaela są znacznie rzadsze niż liczby pierwsze, więc ten test może być przydatny do celów praktycznych.
21. Na przykład lista liczb pierwszych Derricka Normana Lehmera do 10.006721, przedrukowana dopiero w 1956 roku, zaczynała się od 1 jako pierwszej liczby pierwszej.
22. Teza Cobhama mówi, że problem można rozwiązać za pomocą możliwej do zrealizowania ilości zasobów, jeśli dopuszcza się wielomianowy algorytm czasu.
23. Euclid pokazał również, jak skonstruować liczbę doskonałą z liczby pierwszej Mersenne'a.
24. Od stycznia 2016 [aktualizacja] największa znana liczba pierwsza ma 22 338 618 cyfr dziesiętnych.
25. Takie pytania były bodźcem do rozwoju różnych działów teorii liczb, skupiających się na analitycznych lub algebraicznych aspektach liczb.