Byla vydána nová stabilní verze 6.7 webového prohlížeče Vivaldi (Wikipedie). Postavena je na Chromiu 124. Přehled novinek i s náhledy v příspěvku na blogu. Vypíchnout lze Spořič paměti (Memory Saver) automaticky hibernující karty, které nebyly nějakou dobu používány nebo vylepšené Odběry (Feed Reader).
OpenJS Foundation, oficiální projekt konsorcia Linux Foundation, oznámila vydání verze 22 otevřeného multiplatformního prostředí pro vývoj a běh síťových aplikací napsaných v JavaScriptu Node.js (Wikipedie). V říjnu se verze 22 stane novou aktivní LTS verzí. Podpora je plánována do dubna 2027.
Byla vydána verze 8.2 open source virtualizační platformy Proxmox VE (Proxmox Virtual Environment, Wikipedie) založené na Debianu. Přehled novinek v poznámkách k vydání a v informačním videu. Zdůrazněn je průvodce migrací hostů z VMware ESXi do Proxmoxu.
R (Wikipedie), programovací jazyk a prostředí určené pro statistickou analýzu dat a jejich grafické zobrazení, bylo vydáno ve verzi 4.4.0. Její kódové jméno je Puppy Cup.
IBM kupuje společnost HashiCorp (Terraform, Packer, Vault, Boundary, Consul, Nomad, Waypoint, Vagrant, …) za 6,4 miliardy dolarů, tj. 35 dolarů za akcii.
Byl vydán TrueNAS SCALE 24.04 “Dragonfish”. Přehled novinek této open source storage platformy postavené na Debianu v poznámkách k vydání.
Oznámeny byly nové Raspberry Pi Compute Module 4S. Vedle původní 1 GB varianty jsou nově k dispozici také varianty s 2 GB, 4 GB a 8 GB paměti. Compute Modules 4S mají na rozdíl od Compute Module 4 tvar a velikost Compute Module 3+ a předchozích. Lze tak provést snadný upgrade.
Po roce vývoje od vydání verze 1.24.0 byla vydána nová stabilní verze 1.26.0 webového serveru a reverzní proxy nginx (Wikipedie). Nová verze přináší řadu novinek. Podrobný přehled v souboru CHANGES-1.26.
Byla vydána nová verze 6.2 živé linuxové distribuce Tails (The Amnesic Incognito Live System), jež klade důraz na ochranu soukromí uživatelů a anonymitu. Přehled změn v příslušném seznamu. Tor Browser byl povýšen na verzi 13.0.14.
Byla vydána nová verze 30.0.0 frameworku pro vývoj multiplatformních desktopových aplikací pomocí JavaScriptu, HTML a CSS Electron (Wikipedie, GitHub). Chromium bylo aktualizováno na verzi 124.0.6367.49, V8 na verzi 12.4 a Node.js na verzi 20.11.1. Electron byl původně vyvíjen pro editor Atom pod názvem Atom Shell. Dnes je na Electronu postavena celá řada dalších aplikací.
Programming stuff. And stuff.
Na notebooku (Core i5-2520M) s obyčeným pythoním gmpy (wrapper GMP) dostávám 170794 GCD za sekundu na 1024-4096 bit RSA modulech. Lenstra testoval 4.7 miliona 1024-bit modulů a 6.4 modulů celkově. V mé denně updatované databázi se nachází 1424938 unikátních RSA modulů, které se dělí podle velikosti modulu následovně (pár ostatních s jinými velikosti vynechávám):
rsa_bits | count
----------+--------
4096 | 22367
1024 | 491356
2048 | 908103
Nejjednodušší je prostě udělat GCD každého modulu s každým jiným, což dává složitost O(N2). Rychlost operace GCD se schová do nějaké konstanty, protože velikost modulů je shora omezena. Pro uvedený notebook by to znamenalo 4.1 let na otestování na 4.7M modulů nebo 7.6 let pro otestování 6.4M modulů.
Místo testování každého modulu s každým, budeme testovat jenom ty se stejným modulem, protože moduly s různě velkými moduly téměř jistě nebudou sdílet prvočíslo. Kvůli kvadratické složitosti to dost pomůže proti "triviálnímu" algoritmu. Třeba pro otestování všech klíčů z mé DB by časy byly:
rsa_bits | čas
----------+--------
4096 | 50 min
1024 | 17 dní
2048 | 56 dní
Místo testovaní všech klíčů se můžeme spokojit třeba s nalezením jenom P=50% z nich. Tím by šlo algoritmus ještě více urychlit. Podle výsledků Lenstru je 0.2% klíčů sdílejích prvočísla. Oříšek je zde v tom, že existuje 1995 skupin, které navíc nejsou uniformně rozloženy. Když si trocha zjednodušíme předpoklady, šlo by se dopočítat k očekávanému počtu testů.
Např. jaký je očekáváný počet GCD testů, pokud budeme předpokládat že slabé klíče jsou uniformně rozloženy v těch 1995 skupinách? Kolik by to bylo, kdybychom předpokládali existenci jenom jedné skupiny? Kdyby se to někomu chtělo spočítat, ocenil bych to, teď si mi to už počítat nechce . Ten případ s jednou skupinou by měl být celkem snadno spočítatelný.
Možná existují další algebraické triky jak ještě víc omezit počet modulů k testování. Při kvadratické náročnosti vzhledem k počtu modulů by to mohlo ještě značně urychlit. Možná když budu mít chvíli času, tak si osvěžím z Koblitze jestli to lze algebraicky znásilnit ještě víc. Ale neodmítnu jestli se někdo podělí o nápad
Vychází z algoritmu, který publikoval Dan Bernstein v Journal of Algorithms. Je založen na triku jak naráz spočítat GCD modulu N1 se všema ostatníma:
gcd(N1,N2…Nm) = gcd(N1, (N1*N2*…*Nm mod N12)/N1)
Z odhadů je vidět, že i s takto jednoduchými algoritmy to lze na nějakém mírně lepším clusteru nebo FPGA "vydrtit" v celkem rozumném čase. Používat GPU na GCD jsem taky nezkoušel. S lineárním algoritmem to dá běžné PC za pár hodin.
Tiskni Sdílej:
Jinak NSD se snad povinně učí na středních školách a většina ostatních věcí stejně byla uvedena jen jako fakt („že lineární algoritmus existuje atp.“), takže čtenář ani nemá co se snažit pochopit.Ano, kdyz to dostanou takto naservirovano (vsechno jiz pochopeno je jednoduche). NSD se sice uci, ale zvlastni je, ze kazdemu z cca 10-15 lidi jsem to musel vysvetlovat osobne jak to funguje, i kdyz je to trivialni (proste si nedocvakly ty dva-tri fakty). Proto jsem psal ten clanek. Tvrzeni "ctenar ani nema co pochopit" je asi jako dostat reseni na instanci NP-uplneho problemu a reknout "vzdyt to je jednoduche" kvuli tomu ze reseni je zverejneno a nerict nic o narocnosti nalezani reseni. BTW zpusobu pro GCD je spousta. Tim Euklidovym byste daleko nedosel. Samotny Bernstein je v zasade "mega-GCD-na-steroidech". Ale to nema cenu vysvetlovat, viz paper: http://cr.yp.to/lineartime/dcba-20040404.pdf Preji vesele a stastne grcani pri cteni. Taky nebudu vykladat jake triky jsem skutecne pouzil, nebo nedejboze davat sem kod pro script kiddies (napr. kazdemu algebraikovi musi prijit ta dlouha GCD rovnice podivna, jsou tam zbytecne veci navic). Tudiz evidentne algebraik nejste. Stejne ste IMHO jenom stoural. Hadat se nechci, jenom jsem uvedl nazor autora (vidite ted, jaka je to dementni argumentace?) Omluva prijde az od vas uvidim implementaci toho Bernsteinova algoritmu. Pak taky muzete napsat stokrat lepsi clanek o te implementaci. There's no royal road to crypto.
Nechce sa vam vyskusat O(n*log n) algoritmus zalozeny na tom, ze gcd(a,b,c,d) = gcd(gcd(a,b), gcd(c,d)) ? S ohladom na jednoduchost by v realite mohol dosahovat celkom dobre vysledky. Obvzlast ak sa berie do uvahy postupne zjednodusovanie vypoctu gcd vo vrstvach log n.
Implementacia v pythone asi nejak takto (pripadne pridat nejake optimalizacie ako lepsiu kniznicu pre gcd (ak je) a pod.):
from fractions import gcd def wgcd(d, u): if u - d == 1: return a[d] elif u - d == 2: return gcd(a[d], a[d+1]) else: return gcd(wgcd(d, d + (u - d)/2), wgcd(d + (u - d)/2, u)) a = [17*(x*2) for x in range(150000)] print(wgcd(0, len(a)))
Hm, ked tak rozmyslam, tak ta zlozitost sa pravdepodobne zmesti aj do O(n).
Konecne ta gcd rovnica z blogu zacina davat zmysel. Akosi som za gcd(N1,N2…Nm) povazoval gcd(N1,N2,N3 .. Nm) a nie gcd N1 s produktom N2 .. Nm. Vdaka za objasnenie.