Overleg:Getallenlichamenzeef

Fout in complexiteit?

De formule voor complexiteit in het huidige artikel:

$O\left(\mathrm {e} ^{c\,(\log {n})^{1/3}(\log {\log {n}})^{2/3}}\right)\!,$

gaat niet hard met n omhoog (is zelfs sublineair). De Engelstalige WP geeft:

$O\left(\mathrm {e} ^{(c+o(1))\,(\log {n})^{1/3}(\log {\log {n}})^{2/3}}\right)\!,$

met

$c\approx \left({\sqrt[{3}]{\frac {64}{9}}}\right)\approx 1.923$

waarin o(1) misschien onbelangrijk is?

Verder is de betekenis van n absoluut onduidelijk in dit artikel.

Zijn er experts in de zaal?--P.wormer (overleg) 1 mrt 2016 16:48 (CET)

Vervolg

Een vooraanstaand expert in getallentheorie, H.W. Lenstra, gaf in 1995 (Nieuwe Wiskrant) dezelfde formule voor de complexiteit voor de getallenlichamenzeef als in de Nederlandse WP. Lenstra schreef verder:

"Als n maar 190 cijfers heeft is het goed voorstelbaar dat men een getal van die grootte met bestaande technische en algoritmische middelen kan ontbinden. [...] Wie getallen van meer dan zo'n 200 cijfers wil ontbinden kan er alleen maar op hopen dat iemand een snellere methode bedenkt."

Ik ben in de war gebracht door deze opmerkingen en heb daarom de formule voor complexiteit in een JavaScript script gezet. Ik schrijf het te ontbinden getal n als n = 10^n_digits−1 en loop over n_digits met stappen van 10.

var nDigits, lnn, lnln, complexity;
var LN10 = Math.log(10);                       // natuurlijke logaritme
for (nDigits = 160; nDigits <= 220; nDigits += 10) {
    lnn        = (nDigits - 1) * LN10;        //lnn = log(10^{nDigits-1}) = log(n)
    lnln       = Math.log(lnn);
    complexity = Math.exp(1.923 * Math.pow(lnn, 1/3) * Math.pow(lnln, 2/3));
    complexity = complexity.toExponential(1);
    console.log('number of digits: ' + nDigits +  ' complexity: ' + complexity );
}

Volgens dit script is de complexiteit van de ontbinding van een getal van 190 cijfers 1.2e+21 en voor 200 cijfers is het 3.6e+21, een factor 3 groter. Ik zou denken dat computers nu wel meer dan 3 keer meer vermogen hebben dan in 1995. Dus als in 1995 een getal van 190 cijfers met enige moeite te ontbinden was, moet een getal van 200 cijfers nu zeker te ontbinden zijn, zonder dat nieuwe methodes nodig zijn.

Kortom, ik denk dat er iets niet deugt aan mijn script of aan de Lenstra/NL-WP formule. Of misschien interpreteer ik de complexiteitsformule te naïef? Wie helpt mij (en andere WP lezers van dit artikel) uit de brand? --P.wormer (overleg) 2 mrt 2016 18:12 (CET)

Ik geloof nu dat de formule correct is, de betrouwbare site MathWorld geeft hem ook. Meer dan 10 jaar geleden had Slashdot een discussie over precies mijn probleem, zie hier. Daar is toen geen echt antwoord uitgekomen. De opmerking van H.W. Lenstra – dat een getal van 190 cijfers met moeite te kraken is en een getal van 200 cijfers met geen mogelijkheid – wordt niet gedekt door de de complexiteitsformule. Onbevredigend! --P.wormer (overleg) 4 mrt 2016 20:33 (CET)

Lenstra's opmerking wordt ook niet gedekt door de feiten: recent is een getal van 240 cijfers ontbonden [1]. P.wormer (overleg) 3 dec 2019 18:34 (CET)

Inmiddels heb ik de WP pagina RSA numbers ontdekt en zie dat in 2020 een getal van 250 decimale cijfers ontbonden is met het getallenlichamenzeef algoritme. Volgens deze pagina was Lenstra lid van een team dat in 2009 een getal van 232 decimale cijfers ontbonden heeft. Dus Lenstra was in 1995 (Nieuwe Wiskrant) veel te pessimistisch. Ik vraag me na 8 jaar nog steeds af wat we met bovenstaande complexiteitsformule aan moeten. P.wormer (overleg) 24 jan 2024 14:37 (CET)

Externe links aangepast

Hallo medebewerkers,

Ik heb zojuist 1 externe link(s) gewijzigd op Getallenlichamenzeef. Neem even een moment om mijn bewerking te beoordelen. Als u nog vragen heeft of u de bot bepaalde links of pagina's wilt laten negeren, raadpleeg dan deze eenvoudige FaQ voor meer informatie. Ik heb de volgende wijzigingen aangebracht:

• Archief https://web.archive.org/web/20101117052648/http://scholar.lib.vt.edu/theses/available/etd-32298-93111/unrestricted/etd.pdf toegevoegd aan http://scholar.lib.vt.edu/theses/available/etd-32298-93111/unrestricted/etd.pdf

Zie de FAQ voor problemen met de bot of met het oplossen van URLs.

Groet.—InternetArchiveBot (Fouten melden) 30 apr 2018 00:27 (CEST)