Jarek Duda

astroboy, zmiana podstawy jest równoważna z liniowym przeskalowaniem wykładnika. Z adiabatą można się też spotkać np. w mechanice klasycznej Arnolda - jest to ogólnie proces na tyle powolny że odwracalny. Co do grup Galois, to myślałem że masz na myśli opis płaszczyzn Riemanna, ale tutaj mamy rzeczywisty wielomian (bez pierwiastków). Flaku, oczywiście jest nieskończenie więcej rodzajów wzrostów niż wielomianowy i eksponencjalny (jak exp(x/ln(x)) między nimi), jednak różnica między tymi dwoma jest tą kluczową tutaj.

Po pierwsze, specjalnie napisałem "typu" ext(wielkość problemu) na pytanie co to znaczy wykładniczy wzrost - oczywiście liniowo skalując wykładnik pozostajemy w wykładniczym wzroście. Co do Shora to też jestem sceptyczny - gdzieś tam się udało zfaktoryzować 15 ... gdzieś tam koło 200 ... w eksperymentach dedykowanych żeby dokładnie daną faktoryzację pokazać ... Co do adiabaty, to jasne historycznie kojarzy się np. z cyklem Carnota ... jednak np. od nawiązanego twierdzenia adiabatycznego (1928, Born & Fock), wkroczyła ona do mechaniki kwantowej (i jak dla mnie słusznie), prowadząc do tak nazywanych dzisiaj komputerów: http://en.wikipedia.org/wiki/Adiabatic_quantum_computation Co do "prostych Hamiltonianów" to oczywiście chodzi o idealizację, które jest podstawą mechaniki kwantowej i takowych komputerów. Osobiście wierzę że jest to efektywna reprezentacja jakiejś głębszej dynamiki, np. jak kropelkach Coudera: Nie wiem co tu mają do rzeczy grupy Galois, ale transformację 3SAT do globalnej minimalizacji nieujemnego wielomianu podałem w celu pokazania problemu tego typu podejść: wykładniczy wzrost ilości lokalnych minimów.

Wykładniczo oznacza że wzrost jest typu exp(wielkośc problemu). Podczas gdy jeśli P!=NP, na standardowych komputerach koszt rozwiązywania trudnych problemów rośnie zawsze wykładniczo z wielkością, nadzieją komputerów kwantowych jest wielomianowy wzrost - np. koszt faktoryzacji rosnący wielomianowo z ilością cyfr (Shor). Natomiast adiabatyczne komputery kwantowe działają na innej zasadzie niż te "standardowe QC" pozwalające na algorytm Shora - one szukają minimum Hamiltonianu w sposób adiabatyczny - czyli zaczynamy od prostego Hamiltonianu dla którego łatwo mu znaleźć minimum, i powoli przełączamy do Hamiltonianu naszego problemu - zakładając że cały czas pozostajemy w jakimś minimum: http://en.wikipedia.org/wiki/Adiabatic_theorem ... ale to ostateczne minimum wcale nie musi być tym globalnym ... i dodatkowo termodynamika wszystko psuje. NP trudny problem możemy łatwo zamienić na globalną minimalizację. Np. 3SAT to pytanie czy dana koniugacja alternatyw trójek może być prawdziwa. Alternatywę dwóch zmiennych: x OR y można zamienić na zerowanie nieujemnego wielomianu: ((x-1)^2+y^2)((x-1)^2+(y-1)^2)(x^2+(y-1)^2) analogicznie dla trójek mamy wielomian stopnia 14 (można zmniejszyć do 10). Sumując takie wielomiany dla poszczególnych trójek, oryginalny problem 3SAT jest równoważny z znalezieniem globalnego minimum tego wielomianu. Czyli jeśli miałby tylko wielomianowo wiele lokalnych minimów, w czasie wielomianowym moglibyśmy przeszukać wszystkie, czyli P=NP ... co sugeruje że dla trudnych problemów ilość minimów rośnie wykładniczo - a więc i odległości energetyczne między nimi maleją wykładniczo, czyli dla takiego komputera adiabatycznego musielibyśmy obniżać temperaturę jak exp(- wielkość problemu).

Te 20 lat brzmią dość optymistycznie ... co do D-Wave, to sprowadza się tutaj problem do szukania minimum Hamiltonianu (Shor jest bardziej wyrafinowany), do którego próbujemy zejść w sposób adiabatyczny. Tylko że wymaga to żeby istniało pojedyncze globalne minimum energetyczne, które jest odseparowane od reszty - co dla trudnych problemów po prostu nie jest prawdą - mają one wykładniczo wiele lokalnych minimów, czyli układ czysto termicznie nie jest w stanie ich odróżnić, szczególnie że ewolucja nie jest idealnie adiabatyczna. Chyba największy sukces D-Wave to aktualnie liczba Ramseya R(3,3): http://physicsworld.com/cws/article/news/2013/sep/27/has-a-quantum-computer-solved-the-party-problem ... którą zwykły komputer jest w stanie znaleźć w ułamek sekundy ...

Miałem na myśli długości cykli wybierane lokalnie w sposób pseudolosowy - że np. klucz wraz z ostatnim zdekodowanym blokiem decydują czy dla kolejnego bloku należy użyć np. 13 czy 14 cykli ... Problem w tym że aktualnie np. AES to wykonanie w ściśle określonej kolejności niezwykle prostych operacji: XOR i permutacji - to by było wręcz dziwne gdyby tam nie zostały jakieś głębsze zależności, np. jakiś daleko nietrywialny niezmiennik, do którego wyszukiwania mogą istnieć wyspecjalizowane superkomputery ... Jak w sztuczkach z liczbami czy kartami że wykonujesz kilka prostych operacji a na końcu okazuje się że dostajesz trywialny wynik... Jeśli chcemy być pewni że tam nie ma backdoorów, trzeba zaburzyć ten idealny porządek, np. - pseudolosowo zaburzać idealny schemat wykonywania tych prostych operacji (np. na podstawie klucza i ostatniego zdekodowanego bloku), - pseudolosowo na podstawie klucza wybierać parametry używane przez koder, jak wybór S-box w pewnej sporej rodzinie dobrze zachowujących się (ilość możliwości musi być duża), - wstawić jakąś bardzo nieliniową operację w środek, - ... ?

Praktycznie cała kryptografia symetryczna, łącznie z AES, opiera się na permutacjach i XORach wykonanych w konkretnej kolejności (stała ilości cyklów) - budowaniu na tyle skomplikowanej łamigłówki logicznej, że już na pewno nikt jej nie powinien sprytniej rozwiązać ... Jeśli chcemy się rzeczywiście zabezpieczyć przed istnieniem trików do obchodzenia, przed wbudowywaniem backdoorów ... trzeba w końcu wyjść poza stałe schematy na prosto odwracalnych operacjach! Np. samo uzmiennienie ilości cykli, jak że jest wykonywane 13 lub 14 cykli w zależności od klucza i aktualnych danych - niesłychanie utrudniłoby by próby odwracania tej łamigłówki. Natomiast dodanie w środku czegoś mocno nieliniowego-chaotycznego, praktycznie z automatu by uniemożliwiło wszelkie takie próby. Np. wrzucić do środka asymetryczny system liczbowy stablicowany na niewielkim przedziale - dostajemy coś jakby "permutację z pamięcią" używającą losową ilość bitów na krok ...

To że formalizm Lagranżowski - którego używamy we wszystkich skalach: od kwantowej teorii pola do ogólnej teorii względności, mówi że fizyka już znalazła czterowymiarowe rozwiązanie (np. trajektorię, historię konfiguracji pola, kształt czasoprzestrzeni) optymalizujące działanie to nie moje wywody tylko jest znane od ponad dwóch stuleci ... ( http://en.wikipedia.org/wiki/Lagrangian_mechanics#Lagrangian_and_action ) Pytanie jak przetłumaczyć problemy algorytmiczne na minimalizację działania i podstawić fizyce - żeby się okazywało że ona już rozwiązała nasz problem (np. uzgadniając pętlę przyczynową) ... ?

Rzeczywiście budowanie standardowych komputerów asynchronicznych przysparza wiele problemów z synchronizowaniem np. pętli ... to o czym mówię nie ma takich pętli: podstawowy układ składa się z kilku warstw bramek logicznych - bez pętli, znalezienie rozwiązania oznacza ustabilizowanie prądów. Dodatkowa zewnętrzna pętla jest tylko żeby ustawić stabilizację na szukane rozwiązania naszego problemu - w celu minimalizacji energii ta rzeka elektronów powinna przejść do stabilnego przepływu - rozwiązać nasz problem szukając wśród ciągłych wartości między 0 i 1. A może zamiast takiego ciągłego szukania minimum energetycznego, moglibyśmy wykorzystać to że mechanika Lagranżowska już znalazła trajektorie (historie konfiguracji pola) minimalizujące działanie ... pytanie jak zamienić problem algorytmiczny na minimalizację działania. Teoretycznie można by bardzo prosto - wystarczyłoby tą pętlę zamknąć nie przestrzennie tylko czasowo - gdyby dało się przesłać wyjście w przeszłość, tak żeby ten układ korzystał z niego na wejściu - wtedy w celu minimalizacji działania, fizyka powinna od razu wybrać wejście dające zgodną pętlę przyczynową - rozwiązując nasz problem. No ale przecież nie da się przesyłać informacji wstecz w czasie ... no ale zarówno mechanika Lagranżowska jak i unitarna mechanika kwantowa są czasowo/CPT symetryczne - nie rozróżniają przeszłości i przyszłości. Więc i są potwierdzone "kwantowe" doświadczenia jak Wheelera, w którym późniejszy wybór ma wpływ na interpretację tego co działo się wcześniej ( http://en.wikipedia.org/wiki/Wheeler%27s_delayed_choice_experiment ) ... albo delayed choice quantum erasure, dla którego np. obrót polaryzatora na jednej drodze optycznej zmienia statystykę na drugiej, czyli wydaje się że zmieniając długości dróg optycznych moglibyśmy wpływać na przeszłą statystykę: http://www.thescienceforum.com/physics/27354-controlled-delayed-quantum-erasure-where-causality.html Osobiście na mechanikę kwantową, jej nieintuicyjność, patrzę jako na rezultat tego że nie żyjemy w "ewoluującym 3D" jak podpowiada nasza intuicja, tylko w prawdziwej "czterowymiarowej czasoprzestrzeni", Einsteinowskim Block Universe - taka czterowymiarowa galareta: teraźniejszość jest rezultatem minimalizacji naprężenia/działania z obu stron. Asymetria jest na poziomie statystyki/termodynamiki - nie ma na nią miejsca w fundamentalnych równaniach, tylko jest rezultatem konkretnego rozwiązania w którym żyjemy - konkretnie bliskości Wielkiego Wybuchu, w którym wszystko było praktycznie w tym samym miejscu, czyli miało małą entropię, więc i wytworzyło jej gradient w który teraz żyjemy: drugą zasadę termodynamiki. Tutaj jest wytłumaczenie siły algorytmu Shora z tej perspektywy - kluczowe jest że komputer kwantowy potrafi "zamocować" przestrzeń rozwiązań nie tylko z przeszłości (inicjalizacja) ale i z przyszłości (pomiary):

Trudne problemy algorytmiczne od zawsze próbujemy atakować pozostając w dyskretnym świecie zerojedynek - uciąglenie problemu, wyjście poza 0/1 np. w takim "asynchronicznym komputerze pętlowym" jest właśnie przejściem do innego królestwa matematyki/fizyki, gdzie może (ale nie musi) istnieć szybszy sposób - to jest ciężkie zadanie, ale myślę że warto je eksplorować. Szczególnie że fizyka jest idealna właśnie w ciągłych problemach jak np. minimalizacja energii - działanie takiego komputera zdecydowanie zależałoby od użytej elektroniki, pośrednich zachowań bramek, ale może istnieje też taka w której by działał ... np. błyskawicznie znajdujący klucz kryptograficzny dla zaszyfrowanej wiadomości ... ? Zresztą taki adiabatyczny komputer kwantowy jak D-Wave też polega na ciągłej ewolucji pomiędzy klasycznymi 0 i 1 ... Skoro fizyka jest idealna w minimalizacji energii, może da się skonstruować ciągły potencjał którego (globalna!) minimalizacja rozwiązywałaby nasz problem? I owszem ... Problemy NP-zupełne możemy sprowadzić do 3SAT, czyli pytanie o istnienia wartościowań zmiennych, takich że wszystkie alternatywy trójek (x lub y lub z, gdzie dodatkowo zmienne mogą być zanegowane) są spełnione. Zauważmy że (x lub y) możemy sprowadzić do minimalizacji wielomianu 6 stopnia: ((x-1)^2+y^2)((x-1)^2+(y-1)^2)(x^2+(y-1)^2) Analogicznie dla alternatywy trójki zmiennych mamy wielomian 14 stopnia (można zredukować przynajmniej do 8). Sumujemy takie nieujemne wielomiany dla wszystkich trójek z 3SAT i rozwiązanie problemu jest równoważne ze znalezieniem zera - globalnego minimum wielomianu. Oryginalny problem wychodzi poza 0,1 do ciągłych wartości pomiędzy - mamy tu zupełnie inne narzędzia ciągłej optymalizacji globalnej. Ta transformacja jest trochę zbyt wysoko wymiarowa żeby bezpośrednio podstawić fizyce, ale może istnieją inne sprowadzenia problemów algorytmicznych do bezpośrednio dostępnych fizyce (jak komputery kwantowe czy asynchroniczny komputer pętlowy) ... ?

Równie dobrze możemy powiedzieć że komputery mechaniczne są lepsze ... np. wiele problemów dalej lepiej analizować w tunelu aerodynamicznym niż porównywalnie dokładnie liczyć z Naviera-Stokesa ... Nic dziwnego że fizyka pozwala szybciej bezpośrednio liczyć jej własne problemy (np. dalej nie potrafimy satysfakcjonująco policzyć co się dzieje w pojedynczym protonie, co dla fizyki jest trywialne), pytanie czy możemy to zastosować do pożytecznych problemów algorytmicznych jak np. obiecywany algorytm Shora ... którego raczej nie uruchomimy na adiabatycznym komputerze kwantowym ... http://physics.stackexchange.com/questions/10496/what-can-the-d-wave-quantum-computer-do Ale ogólnie wierzę że warto szukać alternatywnych podejść "podstawienia" fizyce, idealnej w rozwiązywaniu swojej teoriopolowej mechaniki Lagranżowskiej, trudnych problemów algorytmicznych do rozwiązania - na przykład myślałem o asynchronicznym komputerze z pętlą: Weźmy jakiś problem NP-trudny, czyli szybko możemy stwierdzić czy dane wejście jest satysfakcjonujące, ale sęk w tym że jest wykładniczo wiele różnych możliwych wejść, np. mamy zaszyfrowaną wiadomość ale rozszyfrowanie tylko z poprawnym kluczem nas satysfakcjonuje - dla innych kluczy dostajemy praktycznie biały szum. Ten weryfikator stwierdzający poprawność wejścia może być zrealizowany przez kilka warstw podstawowych bramek (bez pętli, np. przez sprowadzenie do 3SAT) - załóżmy że mamy układ elektroniczny (bez zegara!) który w taki sposób sprawdza czy dane wejście jest poprawne. Połączmy go w pętlę w ten sposób: - Jeśli wejście poprawne zwróć wejście, w przeciwnym razie zwróć wejście+1 - Podaj wyjście na wejście Czyli z zegarem taki układ sprawdzałby po kolei wszystkie możliwości aż do stabilizacji w jakimś satysfakcjonującym (załóżmy że istnieje). Ale co gdy nie ma zegara? Mamy czystą hydrodynamikę elektronów, które płyną przez pętlę i żeby zminimalizować energię powinny szukać stacjonarnego przepływu - naszego rozwiązania ... pytanie czy mogą to zrobić szybciej niż z zegarem ??? czy np. rzeka optymalizuje przepływ badając kolejne możliwości, czy może płynnie przechodzi do optymalnego przepływu ...

Na OTW możemy patrzeć jako szereg poprawek do grawitacji Newtonowskiej, jednak eksperymentalnie (szczególnie przez Gravity Probe B ) zostało potwierdzone tylko do powiedzmy drugiej - tzw. grawitomagnetyzmu (GEM): http://en.wikipedia.org/wiki/Gravitoelectromagnetism Bezpośrednie sprawdzenie kolejnej poprawki jest już raczej praktycznie zupełnie niewykonalne - dalej mamy tylko ekstrapolację z wiary w estetykę Einsteina... Na przykład samo GEM, wprowadzone w 1893 przez Heavisida, też już może funkcjonować jako samodzielne rozszerzenie grawitacji Newtona do teorii Lorentzowsko nieimienniczej - i to dużo prostsze: nie wymaga zakrzywiania czasoprzestrzeni (tylko samej przestrzeni: podrozmaitości stałego czasu), a więc i jest dużo mniej kontrowersyjne: nie trzeba hipotetycznych dodatkowych wymiarów, nie ma wormholi, nie ma osobliwości wychodzących poza stosowalność teorii jak w centrum czarnej dziury gdzie czasoprzestrzeń przestaje być rozmaitością ... W każdym razie uważam że jeszcze za mało wiemy żeby ekstrapolować silne wnioski na temat kosmologii ...

Kosmiczna próżnia nie jest taka pusta - jest tam np. pełno protonów ... granica GZK na produkcję pionów (które często dalej rozpadają się do pozytonów) jest dość wysoka (z 10^7 razy większa energia niż w LHC): http://en.wikipedia.org/wiki/Greisen%E2%80%93Zatsepin%E2%80%93Kuzmin_limit ale wcześniej chyba powinniśmy też oczekiwać bezpośredniej produkcji par pozyton-elektron np. w obecności protonów? http://en.wikipedia.org/wiki/Pair_production Z jednej strony są to energie cząstek o kilka rzędów wielkości większe niż dostępne np. w LHC, więc chyba powinniśmy być ostrożni z ekstrapolacjami ... z drugiej nie rozumiemy ich pochodzenia i ogólnie jest jeszcze sporo rzeczy szczególnie w astrofizyce czy kosmologii których obecnie za bardzo nie rozumiemy - myślę że jeszcze należy być bardzo ostrożnym z silnymi wnioskami jak pochodzenie z hipotetycznej ciemnej materii ... której jakoś nie widać w bezpośrednich eksperymentach ...

Rzeczywiście nadmiar wysokoenergetycznych pozytonów to ciekawa obserwacja, kolejne przypomnienie że nasze zrozumienie wszechświata nie jest takie pełne jak by się nam wydawało ... ale zupełnie nie widzę związku z hipotetyczną ciemną materią?? Pewnie to jest dobre wytłumaczenie do zdobywania grantów, ale dlaczego chociażby teoretycznie ciemna materia miałaby się przyczyniać do produkcji wysokoenergetycznych pozytonów? Jeśli jednak się rozpada to powinniśmy też widzieć jakiś charakterystyczny pik w gammach ... dalej temperatura powinna wpływać na rozpad, skoro niby oddziałuje grawitacyjnie to powinna się koncentrować w gwiazdach, czyli już może mieć istotny wpływ na modele gwiazdowe ... Ja bym tam raczej szukał wytłumaczenia w innym fakcie którego nie bardzo rozumiemy: ultra-wysoko-energetycznym promieniowaniu kosmicznym http://en.wikipedia....ergy_cosmic_ray które też powinno produkować wysokoenergetyczne pary elektron-pozyton ...

Myślałem że takie ładowanie ma dość niską efektywność, ale ponoć dochodzi do 90% http://en.wikipedia....uctive_charging http://batteryuniver...g_without_wires jednak mam wrażenie że powszechne przesyłanie dużych mocy w ten sposób nie wpłynie pozytywnie na już niemały i dalej rosnący poziom szumu elektromagnetycznego - utrudni komunikację wewnątrz miast, ale i może mieć inne trudne do wytropienia efekty uboczne, na przykład podejrzewa się go jako jeden z powodów wymierania pszczół ... http://en.wikipedia.org/wiki/Colony_collapse_disorder#Electromagnetic_radiation

Whow, to może już za parę lat uda się obliczyć że 15 to 3 razy 5 także nawet nie wiedząc tego

No tak, skoro roboty zastępują ludzi w różnych dziedzinach życia, mogą też zastąpić biedne dzieci żeby już nie musiały się męczyć na lekcjach

Tutaj akurat nie ma problemu - fotony, czyli nośniki pola elektromagnetycznego, jak najbardziej niosą też pęd. Stąd też na przykład pomysł żagli słonecznych, w których odbijające się fotony ze słońca nadają statkowi pęd ... albo można by bezpośrednio napędzać statek laserem ("fotonowy silnik odrzutowy") ... problem w tym że raczej sensownej efektywności tak nie osiągniemy ... Fale radiowe też niosą pewien pęd: http://en.wikipedia....iation_pressure Pytanie czy ilościowo to tym razem może mieć sens ...?

Chodzi o zwykłą inwersję obsadzeń - że z jakichś powodów np. któryś stan wzbudzony jest bardziej obsadzony niż podstawowy, czyli w tej definicji w każdym laserze mamy "ujemną temperaturę". Ciekawe jest że tym razem dzieje się to z powodów entropijnych. http://en.wikipedia.org/wiki/Negative_temperature

Miałem podobny pomysł z licencją na zabijanie (się) ze 3 lata temu - żeby koszty przerzucić na dłuższe okresy, dzięki czemu łatwiej powinno być rzucić, trudniej zacząć, dzięki licencjom byłaby lepsza kontrola i opieka zdrowotna z akcyzy ... http://www.racjonalista.pl/forum.php/s,208181 Potem zostały zaostrzone przepisy ... ale mam wrażenie że parę miesięcy później już przestały być przestrzegane - od wielu knajp należy trzymać się z daleka dla swojego zdrowia.

160MHz i 8MB rzeczywiście brzmi ograniczająco dla solidnej korekcji trudnych kanałów: BSC (czy AWGN - z dodatkową "soft information") ... ale dla Erasure do radzenia sobie ze zgubionymi pakietami jest zdecydowanie wystarczające. Dodatkowo może używać zasobów sprzętu którego jest częścią - wysyłać mu trudniejsze przypadki, tak że o przepustowości decyduje też główny procesor i wybrany przez użytkownika poziom jego wykorzystania. Nie mówię że jest proste, tylko że jednak może być bardziej optymalnie - że płacimy za zaniedbywanie podstawowej dziedziny dzisiejszego światu informacji: (niekwantowej!) teorii informacji. Na przykład: jakie są ograniczenia dla hashowania? Podczas gdy używa się przynajmniej kilkanaście bitów na element, kilka miesięcy temu okazało się że do rozróżniania elementów wystarczy ok. 2.33 bita/element (slajdy i źródła: http://dl.dropbox.com/u/12405967/hashsem.pdf ).

Przemek, masz dużo racji - rzeczywiście porządna korekcja jest dość kosztowna - dopiero w WiMaxie włączają współczesne metody: Turbo Codes i Low Density Parity Check (w dość oszczędnych wersjach) ... jednak gdy mówimy o utracie pakietów to jest najprostszy możliwy scenariusz do korekcji: Erasure z regularnie rozmieszczonymi uszkodzeniami - do tego od dawna istnieją szybkie prawie optymalne metody jak LT Codes ( http://en.wikipedia...._transform_code ) ... ... a jak chcielibyśmy nie wyrzucać uszkodzonych pakietów tylko wycisnąć z nich ile się da, trzeba jednak solidną korekcję - myślę że tutaj lepiej niż TC i LDPC pasują Correction Trees (podobne do splotowych, ale po kilku istotnych ulepszeniach) - dla małych szumów korekcja jest pełna i praktycznie darmo (a dla dużych, obciążając procesor można wyciągnąć więcej niż z pozostałych: https://dl.dropbox.c.../comaprison.jpg ). Kolejną sprawą jest nie wysyłanie ponownie całych pakietów, tylko w razie potrzeby dodatkowych bloków "bitów parzystości" - wstępnie przesyłasz wiadomość (np. 10 bloków) plus powiedzmy jeden taki blok dodatkowej redundancji ... a jeśli w danym czasie nie dostaniesz potwierdzenia rekonstrukcji, przesyłasz dodatkowy (inny) itd...

@Skotos, Piszesz o rozwoju sprzętu (kanału informacyjnego), natomiast tutaj twierdzą że już samą wymianą protokołu (obsługi danego kanału) poprawiają transmisję o rzędy wielkości - nie ma problemu zrobić blisko optimum, co oznacza że poprzednie rozwiązania były koszmarnym marnotrawstwem z perspektywy teorii informacji ... co zdążyło przestać mnie dziwić.

@jotunn, Wymiana na IPv6 to trochę bardziej skomplikowana konsekwencja kilku dekad rozwoju, wzrostu rozmiarów sieci ... natomiast Wi-Fi jest czymś w miarę świeżym - przynajmniej od strony protokołu można by zrobić raz a porządnie, tyle że - telekomunikacją zajmują się głównie inżynierzy - z względnie przeciętnym podłożem matematycznym ... zrobi rzetelnie żeby działało, ale optymalność jest zwykle dość odległym kryterium, - teoria informacji jest strasznie zaniedbaną dziedziną, - istotne może być też że jak w "spisku żarówkowym", opłaca się robić a nie zrobić - producenci my na tych wymianach sprzętu niemało zarabiają ...

Dla mnie to jest raczej kolejna nauczka jak kiepskie są podstawowe używane algorytmy, szczególnie w teorii informacji - nakazywanie ponownego przesyłania zagubionych pakietów jest żałośnie prymitywnym rozwiązaniem. Zamiast tego można praktycznie darmo dołożyć korekcję błędów, która i tak tam powinna być tam włączona - zgubienie pakietu jest dosłownie najprostszym możliwym scenariuszem uszkodzenia: w przeciwieństwie do standardowego Binary Symmetric Channel w którym nie znamy pozycji uszkodzeń, tym razem wiemy które bity należy odtworzyć (Erasure Channel) i do tego są one równomiernie rozłożone - w tym scenariuszu bardzo łatwo podejść dowolnie blisko granicy Shannona, czyli w naszym przypadku: używamy praktycznie wszystkich nieuszkodzonych bitów. Jeśli wiemy że 5% pakietów jest średnio uszkodzonych, przesyłanie powiedzmy 1.06 bitów/oryginalny bit spokojnie wystarczy żeby odtwarzać oryginalną wiadomość z tych które dotrą. Na przykład dzielimy wiadomość na bloki n bitowe i wysyłamy w n pakietach, z których k-ty jest zbudowany z k-tych bitów oraz dodatkowy (lub kilka) pakiet tej samej długości - zawierający po 1 bicie kontrolnym na blok. Po utracie ostatniego pakietu nic się nie dzieje, natomiast gdy jest to jeden z wcześniejszych, przeglądając drzewo możliwości prawie na pewno uda nam się odtworzyć oryginalną wiadomość: http://arxiv.org/pdf/1204.5317 Ale największym marnotrawstwem jest tutaj używanie sumy kontrolnej na cały pakiet, czyli mimo że po uszkodzeniu pojedynczego bitu pakiet dalej zawiera prawie całą informację, w tym podejściu idzie on śmietnik - wrzucenie korekcji błędów zamiast pojedynczej weryfikacji, jak rozsmarowanie sumy kontrolnej jednorodnie na cały pakiet, powoduje że z uszkodzonego odzyskujemy prawie całą informację. Z kwantowej teorii informacji - która prawdopodobnie nigdy nie znajdzie prawdziwego zastosowania, mamy w Polsce dziesiątki światowej sławy specjalistów ... natomiast z tej praktycznej: klasycznej, która jest podstawą całego przesyłania/zapisywania informacji, pomimo szkół/wydziałów telekomunikacji, na przykład gdy szukałem recenzentów do pierwszego doktoratu (z asymetrycznych systemów liczbowych - prostszej alternatywy kodowania arytmetycznego), okazało się że straszna bida ... Ta sytuacja jest dla mnie jednym z symboli kryzysu w nauce - zamiast pracy nad tym co ważne, nauka stała się jakimś ślepym pędem za publikacjami z tego co modne ... rezultat: zajmuję się klasyczną teorią informacji od kilku lat i gdzie nie spojrzę to widzę podstawowe braki koncepcyjne ... tyle że nikogo to nie interesuje.

Rzeczywiście gąbka w Keccaku zawiera nieliniowość: http://keccak.noekeo...cs_summary.html A[x,y] = B[x,y] xor ((not B[x+1,y]) and B[x+2,y]), forall (x,y) in (0…4,0…4) jednego "and"a - cała reszta to xory i permutacje. Nie mówię że wiem jak to zrobić, tylko że nie jestem przekonany że tym razem już nie istnieje skrótowy sposób na rozwiązanie takiej łamigłówki logicznej. Piszesz że są "dowody kryptoodporności" - proszę przybliż jak chciałbyś dowodzić nieistnienie takich algorytmów? Podpowiem że jest to bardzo zbliżony problem do dowodzenia że P!=NP. Chyba jedyny prawdziwy dowód bezpieczeństwa o jakim słyszałem to dla "one-time pad": xorujesz z jednorazowym kluczem - cała reszta to raczej zbiór heurez i wiary w autorytety ... jasne (znanych!) "szkolnych błędów" pewnie nie ma, ale skąd mamy wiedzieć że np. nie jest tak że jeden z autorytetów już znalazł bardzo subtelne obejście i właśnie dlatego tak forsuje? W żadnym razie nie chodzi mi o to żeby snuć teorie spiskowe, tylko zwrócić uwagę że jednak istnieją nawet bardziej nieprzewidywalne-bezpieczne podstawowe bloczki których moglibyśmy użyć niż nawet wspaniały pojedynczy "bitand" ... Wspomniałeś składanie w korekcji błędów - rzeczywiście w początkach telekomunikacji konkatenacji używało się dla dużych szumów ( http://en.wikipedia....orrection_codes ), ale podczas gdy jednym kodem bardzo trudno podejść do granicy Shannona, po złożeniu dwóch odlatujesz od niej w kosmos ... konkatenacja szybko odeszła do lamusa gdy tylko pojawiły się porządne "jednofazowe" metody: Turbo Codes, Low Density Parity Check (a teraz właśnie dołącza do nich Correction Trees: http://arxiv.org/pdf/1204.5317 ).