Länkar

http://www.interactivecode.com/programming-coding-1/implementing-quadratic-sieve-3805/ http://xvid.se/~xun/001692.html http://www.nada.kth.se/~joel/qs_lecture.pdf http://www.math.uiuc.edu/~landquis/quadsieve.pdf http://www.mersennewiki.org/index.php/P-1_Factorization_Method

Pollard's rho algoritm

Om talet som går in i algoritmen är ett primtal kommer det returneras som en faktor. Funktionen vi använder för att titta om ett tal är ett primtal kan även säga om talet sannolikt är ett primtal.

Vi kan alltså inte testa större tal för att den sannolikhetsfunktionen blir fel

Det är även möjligt att vår vektor som innehåller faktorerna genererar fel, då den endast innehåller unsigned long ints, så faktorerna kan bli större än det som får plats i den

Det visade sig vara vektorn, det ser vi nu när vi ignorerar de faktorer som inte får plats i vår vektor

Förbättringar

• Ändra på hur många iterationer primtalsfunktioen kör för att kolla om något är ett primtal
• Om vi inte får fram ett "fail" från pollards algoritm så kan vi testa ändra på funktionen
• För att öka hastigheten kan man testa cachea faktoriseringar
• Få std::vector att fungera

GMP

Det visade sig att jag använt c-versione av gmp, tydligen finns det en c++ version också, då man använder mpz_class istället för mpz_t.

mpz_t går tex inte att stoppa in i en vektor, det går fint med mpz_class.

Jag vet INTE hur man gör alla operationer som man kan göra på em mpz_t på em mpz_class, det verkar nästan som att man måste konvertera den till en mpz_t varje gång, vilket känns otympligt

För tillfället så använder jag mpz_t överallt förutom när jag stoppar in faktorerna i vektorn för utskrift, då gör jag om dem till mpz_class. Jag tror det fungerar tillräckligt bra, då det som max finns 100 faktorer på ett 100 bitars tal. Så maximalt kommer vi kasta om mpz_t till mpz_class 50*100=5000 gånger, det känns inte som så mycket overhead