Steve Jobs a superpočítač Cray-1 budou vyobrazeny na pamětních jednodolarových mincích vyražených v příštím roce v rámci série Americká inovace. Série má 57 mincí, tj. 57 inovací. Poslední 4 mince budou vyraženy v roce 2032.
Byl zveřejněn průběžně aktualizovaný program konference OpenAlt 2025 o otevřeném softwaru a datech, IT bezpečnosti, DIY a IoT. Konference proběhne o víkendu 1. a 2. listopadu v prostorách FIT VUT v Brně. Vstup je zdarma.
Senát včera opětovně nepřijal návrh ústavního zákona, který měl do Listiny základních práv a svobod zakotvit právo občanů platit v hotovosti nebo být off-line. Návrh předložila skupina senátorů již v roce 2023. Senát dnes návrh neschválil, ale ani nezamítl. Pokud by ho přijal, dostala by ho k projednání Sněmovna a vyjádřila by se k němu vláda.
V programovacím jazyce Go naprogramovaná webová aplikace pro spolupráci na zdrojových kódech pomocí gitu Forgejo byla vydána ve verzi 13.0 (Mastodon). Forgejo je fork Gitei.
Společnost Eclypsium se na svém blogu rozepsala o bezpečnostním problému počítačů Framework. Jedná se o zranitelnost v UEFI umožňující útočníkům obejít Secure Boot.
Editor kódů Zed (Wikipedie) po macOS a Linuxu s verzí 0.208.4 už běží také ve Windows.
Apple dnes představil 14palcový MacBook Pro, iPad Pro a Apple Vision Pro s novým čipem M5.
Debian pro mobilní zařízení Mobian (Wikipedie) byl vydán ve verzi 13 Trixie. Nová stabilní verze je k dispozici pro PINE64 PinePhone, PinePhone Pro a PineTab, Purism Librem 5, Google Pixel 3a a 3a XL, OnePlus 6 a 6T a Xiaomi Pocophone F1.
Operátor O2 představil tarif Datamanie 1200 GB . Nový tarif přináší 1200 GB dat s neomezenou 5G rychlostí, a také možnost neomezeného volání do všech sítí za 15 Kč na den. Při roční variantě předplatného zákazníci získají po provedení jednorázové platby celou porci dat najednou a mohou je bezstarostně čerpat kdykoli během roku. Do 13. listopadu jej O2 nabízí za zvýhodněných 2 988 Kč. Při průměrné spotřebě tak 100 GB dat vychází na 249 Kč měsíčně.
Byly publikovány informace o útoku na zařízení s Androidem pojmenovaném Pixnapping Attack (CVE-2025-48561). Aplikace může číst citlivá data zobrazovaná jinou aplikací. V demonstračním videu aplikace čte 2FA kódy z Google Authenticatoru.
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.