potęgowanie modularne

Rok temu na łamach bloga pokazywałem przykładowe rozwiązania zadań z matury próbnej 2022 z informatyki. Postanowiłem też i w tym roku, z okazji nadchodzącego maja, rozwiązać próbną wersję z egzaminu z punktu widzenia osoby na co dzień pracującej jako programista.

Wiemy już: czym są liczby pierwsze, jak sprawdzać, czy liczba jest pierwsza, jak w najprostszy sposób znajdować je, a także poznaliśmy teorię stojącą za znajdowaniem dużych liczb pierwszych. Przejdźmy zatem do praktyki. Czas napisać algorytm, który w krótkim czasie pozwoli nam znaleźć bardzo duże liczby pierwsze, tak jak to się robi w codziennych zastosowaniach.