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

Ферматов тест заснован је на резултату из теорије бројева познате као Ферматова мала теорема.

Према Ферматовој малој теореми, ако је н прост број и д је било који позитивни цели број мањи од н , тада је д подигнут у н- ту степен подударан са д модула н .

Ако два броја имају исти остатак када се поделе са н, тада се каже да су подударни по модулу н . д модуло н је једноставно остатак броја д када се подели са н .

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

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

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

  1. За дати број н одаберите случајни позитиван број д такав да је д < ; н.
  2. Израчунај (д ^ н) по модулу н .
  3. д модуло н ће увек бити д, јер увек бирамо д који задовољава услов д < ; н.
  4. Ако резултат (д ^ н) модула н није једнак д , тада д сигурно није прост.
  5. Ако је резултат (д ^ н) модула н једнак д , онда су велике шансе да је н прост.
  6. Изаберите други случајни д који задовољава услов д < н и поновите горње кораке.

Напомена : Примери у овом посту користе Свифт 4.1

Потребна нам је функција за израчунавање експоненција броја модуло другог броја.

Користимо модуларно потенцирање за израчунавање вредности када је експонент већи од 1, јер нам то омогућава да извршимо израчунавање док се бавимо бројевима мањим од н ( модул у горњој функцији).

Ферматов тест насумично бира број д између 1 и н-1 ( број - 1 у горњој функцији), укључујући. Циљ је да се провери да ли је остатак модула н-те снаге д једнак д.

Фермат тест се изводи за наведени број. Ако број падне на Ферматовом тесту, уверавамо се да није прост. Ако број прође Ферматов тест, није загарантовано да ће бити прост. Покушавамо да смањимо вероватноћу грешке у нашем тесту примарности извођењем теста довољно пута.

Покушавајући све више и више вредности д (случајни позитиван број између 1 и н-1), можемо повећати своје поверење у резултат.