Hur primtalsfaktoriserar man stora tal snabbt?

t.ex. 2116

2116= 2 * 1058 = 2*2*529 = ?

529 är inte delbart med 3 eftersom siffersumman inte är delbar med tre
och det är inte delbart med 5 som är det sista primtalet man kan kolla delbarhet snabbt med.

Hur avgör jag om 529 är ett primtal?
Hur tar jag snabbt reda på dess delare?

Snabbt, menar du med huvudräkning eller papper och penna typ?

Har du bara en kvantdator så kan du lösa det på polynomiell tid

Men antagligen vill du inte faktorisera något tal med riktigt så många värdesiffror att det spelar roll. Erasthostenes såll är väl så basic det blir.

Ja, vorde det omständigt och onödigt att prova liggandestolen med dem första primtalen?

WA räcker till mina behov.
http://www.wolframalpha.com/input/?i...91398765432179

Utan dator?

Pröva med alla primtal mellan 2 och sqrt(529)

blir mycket testande

Så det finns inget bättre än att bara köra med en massa liggande stolen då

Det gör man inte. Om någon sådan algoritm funnes så hade RSA och dylika krypton fallerat direkt.

Man kan välja, vad man provar. 529 slutar till 9.
då ska du prova sådana som slutar med 3.
13 och 23.
17 är nästa. Sedan är bara 19 kvar. Fyra gånger i sämsta fall.