liczba n musi spełniać równanie
2n mod n = 2,
gdzie mod oznacza operator dzielenia modulo, czyli resztę z dzielenia całkowitego.
Uwaga: Starożytny chiński sposób bywa zawodny, istnieją liczby, które spełniają to równanie, a nie są pierwsze; natomiast jeśli równanie nie zachodzi, to n jest na pewno złożona.
Chłopcy postanowili przetestować chińską metodą kolejne liczby n>=2, przeprowadzając
obliczenia tylko na takich liczbach, które można reprezentować bez znaku na 8 bitach. co
znaczy, że na każdym etapie obliczeń stosowali tylko liczby całkowite z zakresu od 0 do 255.
Bajtek obliczał potęgi 2n dla kolejnych wartości n i dla obliczonej wartości wyznaczał resztę
z dzielenia przez n.
Bituś skorzystał z praw arytmetyki modularnej. W każdym z kolejnych kroków obliczania
potęgi, wynik iloczynu brał modulo n. Na przykład dla n=3 obliczenia wykonywał następująco:
Który z nich mógł przetestować pierwszość liczb w większym zakresie?
Podaj możliwie największą wartość n, dla której możliwe było przeprowadzenie testu pierwszości metodą każdego z chłopców.
W obliczeniach Bajtka nmax = ................
W obliczeniach Bitusia nmax = ...............
poleca:
Studentnews.pl