Kā Fermat testu izpildīt pirms 3 minūtēm

Fermat tests ir balstīts uz skaitļu teorijas rezultātu, kas pazīstams kā Fermata mazā teorēma.

Saskaņā ar Fermata mazo teorēmu, ja n ir galvenais skaitlis un d ir jebkurš pozitīvs vesels skaitlis, kas ir mazāks par n , tad d, kas paaugstināts līdz n-tājai jaudai, ir vienāds ar d modulo n .

Ja diviem skaitļiem ir vienāds atlikums, dalot tos ar n, tie tiek uzskatīti par vienādiem modulo n . d modulo n ir vienkārši skaitļa d atlikums, dalot to ar n .

Piemēram, 34 ir vienāds ar 16 (modulo 3) kā

34 modulo 3 = 1 un 16 modulo 3 = 1.

Fermat tests priekšroka

  1. Norādītajam skaitlim n izvēlieties nejaušu pozitīvu skaitli d tā, lai d < ; n.
  2. Aprēķiniet (d ^ n) modulo n .
  3. d modulo n vienmēr būs d, jo mēs vienmēr izvēlamies d, kas atbilst nosacījumam d < ; n.
  4. Ja (d ^ n) moduļa n rezultāts nav vienāds ar d , tad d noteikti nav galvenais.
  5. Ja (d ^ n) moduļa n rezultāts ir vienāds ar d , tad ir lielas izredzes, ka n ir galvenā.
  6. Izvēlieties vēl vienu nejaušu d, kas atbilst nosacījumam d < n, un atkārtojiet iepriekš minētās darbības.

Piezīme . Šīs ziņas piemēri izmanto Swift 4.1

Mums ir nepieciešama funkcija, lai aprēķinātu skaitļa eksponenciālo moduli citam skaitlim.

Vērtību aprēķināšanai mēs izmantojam modulāru eksponenci, ja eksponents ir lielāks par 1, jo tas ļauj mums veikt skaitļošanu, vienlaikus strādājot tikai ar skaitļiem, kas ir mazāki par n ( modulo iepriekš minētajā funkcijā).

Fermat tests nejauši izvēlas skaitli d starp 1 un n-1 ( skaitlis - 1 iepriekš minētajā funkcijā) ieskaitot. Mērķis ir pārbaudīt, vai atlikušais d n n-tās jaudas modulo n ir vienāds ar d.

Fermat tests tiek veikts norādītajam skaitam. Ja skaitlis neiztur Fermat testu, mēs esam pārliecināti, ka tas nav galvenais. Ja skaitlis iztur Fermat testu, tas netiek garantēts kā galvenais. Mēs cenšamies samazināt kļūdu iespējamību mūsu pirmatnības pārbaudē, veicot testu pietiekami daudz reizes.

Izmēģinot arvien vairāk d vērtību (nejaušs pozitīvs skaitlis no 1 līdz n-1), mēs varam palielināt savu pārliecību par rezultātu.