Gruvdrift

Video - Fermat Primality Test

En snabb skiss av hur & varför det fungerar. Skapat av Brit Cruise.

TRANSCRIPT

Vårt mål är att definiera en serie instruktioner som kan bevisa huruvida ett eller flera ingående heltal är komposit - annars identifiera det som prime - med en mycket hög grad av noggrannhet, som vi kan definiera. Och det måste vara effektivt att göra det, vilket betyder att det ska vara snabbt att beräkna på vilken maskin som helst, och även om ingångsstorleken växer - vilket är vårt ingångsnumret n - det borde fortfarande vara snabbt.

Och hittills har vi lärt oss att på den lägsta nivån krävs det ett visst känt mönster som alla primater följer och väldigt få kompositer följer. Men i den tidigare videon visade vi en visuell demonstration av Fermats lilla teorem. Och det ger oss en mycket intressant regel. Med vissa primtal, 'p' och något annat heltal 'a', som är bara mindre än p, vet vi nu att p delar a till kraften p p minus a.

Vi skriver detta som en ^ p = en mod p. Och så ser du det normalt. Nu eftersom a och p delar inga gemensamma faktorer - eftersom p är en primär - kan vi använda avbokningsrätten - och du kommer ibland se detta skrivet som en ^ (p -1) = 1 mod p. Och kom ihåg att vi bara kan göra det för att den största gemensamma divisoren av a och p är lika med 1. Och här har jag just satt upp en demo, så vi kan först först se denna ekvation i aktion och bli bekväm med Det.

Lägg märke till, om jag matar in prime för p, är utmatningen alltid 1, oavsett vilken jag väljer. Om vi ​​matar in ett kompositnummer för P ser vi att det vanligtvis inte är 1. Och när denna ekvation utmatar något som inte är 1, har vi ett kompositvittne. "Det här är nu ett bevis på att den p vi valde inte kan vara förstklassig. Och det är kärnan i detta test. Och innan vi går djupare, låt oss bara gå tillbaka och bygga ramverket för detta test, med det här mönstret visade jag dig bara.

Så vårt test [states] vi är försedda med ett heltal - låt oss kalla det 'p' - som input. Därefter genererar vi ett slumpmässigt heltal, 'a', vilket är mindre än s. Och nu kan vi fråga, "Är den största gemensamma divisoren av a och p 1? "Om inte - om den största gemensamma divisorn av a och p är större än 1, delar de en gemensam faktor, och vi har visat att p är komposit - eftersom en faktor finns.

Och vi kan stanna och avsluta. Och vår algoritm kommer att producera "komposit. 'Men, om' ja 'och vi kan ställa nyckelfrågan, "Gör en till kraften p minus 1 mod p equal 1? "Om inte, vi har ett vittne att p är komposit. Vi kan stanna och säga, "Ja. Var gjort. p är komposit. "Annars, om" ja "- om vår ekvation matar ut 1 - då ska det vara bra, eller hur? Jag har kodat upp denna serie instruktioner och på vänster sida har vi Fermats test, och till höger har jag bara det i befintliga testdelningstest.

Och det är där för att vi vet att testet alltid är korrekt. Och vid första ögonkastet verkar det som om det fungerar.Jag hittade dock ett problem. Jag slår numret 511, och nu säger Fermats test att det är enastående, och testdelningsprovet berättar för mig att det är komposit. 511 verkar prima från testets perspektiv. Men det är inte. Låt oss nu bara återvända till vår ekvation och se vad som hände.

Tja, det här är ett exempel på vad vi kallar en "pseudo-prime". "Det är ett kompositnummer. Men det finns vissa a som vi kan välja att kommer mata ut en 1. Det är felaktigt igen. Så dessa a är som resulterar i ett komposittal - utmatar en 1- vi kan kalla "dårar. "Eftersom de lurar oss på att tänkas numret är förstklassigt. Men märker att om vi väljer olika a, verkar vi hitta många sammansatta vittnen istället för dårar. Så kan vi kanske bara gå tillbaka. Och låt oss tillämpa samma logik som vi använde i delbarhetstestet, där vi bara repeterar experimentet ett par gånger och genererar en ny slumpmässig a varje gång.

Och förhoppningsvis kommer vi inte att välja en dåre varje gång. Nu har det visat sig att antalet dårar måste dela upp den totala storleken hos den grupp vi väljer från. Vilket innebär att hälften av valen eller hälften av elementen i denna pool kan vara dårar. Så, eftersom en väljs slumpmässigt, är chansen att hitta ett sammansatt vittne - vilket är vad vi vill - minst hälften. Efter t iterationer är sannolikheten att inget vittne kommer att hittas med ett sammansatt antal högst 1 / (2 ^ t).

Så efter 20 försök är sannolikheten för att felaktigt utmatas en primär på drygt en miljon. Så det är så vi fortsätter att få riktigt otur i att generera slumpmässiga a. Och varje gång väljer vi en dåre. Om du kan låta det sjunka in, det är verkligen kraftfullt att förstå. Och nu kan vi se vårt test i aktion, med det ökade antalet försök verkar det fungera perfekt.

Och märk att i värsta fall - som vi vet är när vi ger vår algoritm en primär - det kommer att göra maximal mängd arbete. Fermat-testet är mycket effektivare än provdelning - särskilt eftersom antalet steg inte skala med ingången. Och det är en viktig skillnad.

Vi bestämde antalet försök, och det är det. Vi behöver aldrig oroa oss för vår algoritm som driver miljontals och miljoner iterationer som vi gjorde tidigare. Så menar jag, det här är praktiskt tillämpad matte. Vi tar ett mönster som någon upptäckte, och vi sparar en enorm mängd beräkningscykler. Det finns dock en liten fel - eller ett fel - i det här systemet. Kan du hitta den?