Как да стартирате теста на Ферма за първичност за по-малко от 3 минути

Тестът на Ферма се основава на резултат от теорията на числата, известна като малката теорема на Ферма.

Според малката теорема на Ферма, ако n е просто число и d е всяко положително цяло число, по-малко от n , тогава d, повдигнато до n-та степен, е конгруентно на d по модул n .

Ако две числа имат еднакъв остатък, когато се делят на n, тогава се казва, че са сходни по модул n . d по модул n е просто остатъкът от число d, когато се дели на n .

Например, 34 съответства на 16 (по модул 3) като

34 по модул 3 = 1 и 16 по модул 3 = 1.

Тест на Ферма за първичност

  1. За дадено число n изберете случайно положително число d такова, че d < ; н.
  2. Изчислете (d ^ n) по модул n .
  3. d по модул n винаги ще бъде d, тъй като винаги избираме d, което отговаря на условието d < ; н.
  4. Ако резултатът от (d ^ n) по модул n не е равен на d , тогава d със сигурност не е прост.
  5. Ако резултатът от (d ^ n) по модул n е равен на d , тогава шансовете са големи, че n е просто.
  6. Изберете друг произволен d, който отговаря на условието d < n, и повторете горните стъпки.

Забележка : Примерите в тази публикация използват Swift 4.1

Нуждаем се от функция за изчисляване на експоненциалното число на модул по друго число.

Използваме модулна степенуване за изчисляване на стойности, когато степента е по-голяма от 1, тъй като това ни позволява да извършваме изчисления, докато се занимаваме само с числа по-малки от n (по модул в горната функция)

Тестът на Ферма избира произволно число d между 1 и n-1 ( число - 1 в горната функция) включително. Целта е да се провери дали остатъкът по модул n от n-та степен на d е равен на d.

Тестът на Ферма се изпълнява за посочения брой. Ако даден номер не успее на теста на Ферма, ние сме сигурни, че той не е основен. Ако число премине теста на Ферма, не е гарантирано, че е първостепенно. Опитваме се да намалим вероятността от грешка в нашия тест за първичност, като стартираме теста достатъчно пъти.

Опитвайки все повече и повече стойности на d (произволно положително число между 1 и n-1), можем да увеличим доверието си в резултата.