Čínská společnost Tencent uvolnila svůj AI model HunyuanWorld-Voyager pro generování videí 3D světů z jednoho obrázku a určené trajektorie kamery. Licence ale nedovoluje jeho používání na území Evropské unie, Spojeného království a Jižní Koreje.
Blender Studio se spojilo s kapelou OK Go a výsledkem je videoklip k písni Impulse Purchase. Stejně jako samotný 3D software Blender je i ve videoklipu použitý animovaný chlápek open source. Kdokoli si jej může stáhnout a upravovat.
Zig Software Foundation stojící za programovacím jazykem Zig publikovala finanční zprávu za rok 2024. Současně s prosbou o finanční příspěvek.
Na čem pracují vývojáři webového prohlížeče Ladybird (GitHub)? Byl publikován přehled vývoje za srpen (YouTube). Vypíchnuta je podpora Tabulek Google, implementace Gamepad API a Cookie Store API nebo také podpora WebGL na Linuxu.
openSUSE Leap 16, včetně Leap Micra 6.2+, nově nabízí 24 měsíců podpory pro každé vydání. To je dva roky aktualizací a stability, což z něj činí nejdéle podporovanou komunitní distribuci vůbec. Leap se tak stává ideální platformou pro všechny, kdo hledají moderní, stabilní a dlouhodobě podporovanou komunitní Linux distribuci.
Národní úřad pro kybernetickou a informační bezpečnost (NÚKIB) vydal dne 3. 9. 2025 VAROVÁNÍ před hrozbou v oblasti kybernetické bezpečnosti spočívající v předávání systémových a uživatelských dat do Čínské lidové republiky a ve vzdálené správě technických aktiv vykonávané z území Čínské lidové republiky. Varováním se musí zabývat povinné osoby podle zákona o kybernetické bezpečnosti.
Americká internetová společnost Google nemusí prodat svůj prohlížeč Chrome ani operační systém Android. Rozhodl o tom soud ve Washingtonu, který tak zamítl požadavek amerického ministerstva spravedlnosti. Soud ale firmě nařídil sdílet data s jinými podniky v zájmu posílení konkurence v oblasti internetového vyhledávání. Zároveň Googlu zakázal uzavírat dohody s výrobci mobilních a dalších zařízení, které by znemožňovaly
… více »Prvního září ozbrojení policisté zatkli na na londýnském letišti Heathrow scénáristu a režiséra Grahama Linehana, známého především komediálními seriály Ajťáci, Otec Ted nebo Black Books. Během výslechu měl 57letý Graham nebezpečně zvýšený krevní tlak až na samou hranici mrtvice a proto byl z policejní stanice převezen do nemocnice. Důvodem zatčení bylo údajné podněcování násilí v jeho 'vtipných' příspěvcích na sociální síti
… více »Studentská dílna Macgyver zve na další Virtuální Bastlírnu - pravidelné online setkání všech, kdo mají blízko k bastlení, elektronice, IT, vědě a technice. Letní prázdniny jsou za námi a je čas probrat novinky, které se přes srpen nahromadily. Tentokrát jich je více než 50! Těšit se můžete mimo jiné na:
Hardware – Bus Pirate na ESP32, reverse engineering Raspberry Pi, pseudo-ZX-80 na RISC-V, PicoCalc, organizéry na nářadí z pěny nebo … více »Google Chrome 140 byl prohlášen za stabilní. Nejnovější stabilní verze 140.0.7339.80 přináší řadu novinek z hlediska uživatelů i vývojářů. Podrobný přehled v poznámkách k vydání. Opraveno bylo 6 bezpečnostních chyb. Vylepšeny byly také nástroje pro vývojáře.
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.