Byla vydána nová verze 4.5 (𝕏, Bluesky) multiplatformního open source herního enginu Godot (Wikipedie, GitHub). Přehled novinek i s náhledy v příspěvku na blogu.
Byla vydána verze 3.0 (Mastodon) nástroje pro záznam a sdílení terminálových sezení asciinema (GitHub). S novou verzí formátu záznamu asciicast v3, podporou live streamingu a především kompletním přepisem z Pythonu do Rustu.
Canonical oznámil, že bude podporovat a distribuovat toolkit NVIDIA CUDA (Wikipedie) v Ubuntu.
Tržní hodnota americké společnosti Alphabet, která je majitelem internetového vyhledávače Google, dnes poprvé překonala hranici tří bilionů dolarů (62,1 bilionu Kč). Alphabet se připojil k malé skupině společností, které tuto hranici pokořily. Jsou mezi nimi zatím americké firmy Nvidia, Microsoft a Apple.
Spojené státy a Čína dosáhly dohody ohledně pokračování populární čínské platformy pro sdílení krátkých videí TikTok v USA. V příspěvku na síti Truth Social to dnes naznačil americký prezident Donald Trump. Dosažení rámcové dohody o TikToku vzápětí oznámil americký ministr financí Scott Bessent, který v Madridu jedná s čínskými představiteli o vzájemných obchodních vztazích mezi USA a Čínou. Bessentova slova později potvrdila také čínská strana.
MKVToolNix, tj. sada nástrojů pro práci s formátem (medialnym kontajnerom) Matroska, byl vydán ve verzi 95.0. Podpora přehrávání formátu Matroska míří do Firefoxu [Bug 1422891, Technický popis]. Přehrávání lze již testovat ve Firefoxu Nightly.
Spolek OpenAlt zve příznivce otevřených řešení a přístupu na 211. sraz, který proběhne v pátek 19. září od 18:00 ve Studentském klubu U Kachničky na Fakultě informačních technologií Vysokého učení technického na adrese Božetěchova 2/1. Na srazu proběhne přednáška Jiřího Eischmanna o nové verzi prostředí GNOME 49. Nemáte-li možnost se zúčastnit osobně, přednáškový blok bude opět streamován živě na server VHSky.cz a následně i zpřístupněn záznam.
Microsoft se vyhnul pokutě od Evropské komise za zneužívání svého dominantního postavení na trhu v souvislosti s aplikací Teams. S komisí se dohodl na závazcích, které slíbil splnit. Unijní exekutivě se nelíbilo, že firma svazuje svůj nástroj pro chatování a videohovory Teams se sadou kancelářských programů Office. Microsoft nyní slíbil jasné oddělení aplikace od kancelářských nástrojů, jako jsou Word, Excel a Outlook. Na Microsoft si
… více »Samba (Wikipedie), svobodná implementace SMB a Active Directory, byla vydána ve verzi 4.23.0. Počínaje verzí Samba 4.23 jsou unixová rozšíření SMB3 ve výchozím nastavení povolena. Přidána byla podpora SMB3 přes QUIC. Nová utilita smb_prometheus_endpoint exportuje metriky ve formátu Prometheus.
Správcovský tým repozitáře F-Droid pro Android sdílí doporučení, jak řešit žádosti o odstranění nelegálního obsahu. Základem je mít nastavené formální procesy, vyhrazenou e-mailovou adresu a být transparentní. Zdůrazňují také důležitost volby jurisdikce (F-Droid je v Nizozemsku).
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.