Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #33565

Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128

Show all headers | View raw

W dniu czwartek, 12 grudnia 2019 14:09:22 UTC+1 użytkownik fir napisał:
> W dniu środa, 11 grudnia 2019 03:09:16 UTC+1 użytkownik osobliwy nick napisał:
> > > z tego co napisalem wynika ze moze to byc w granicach 0.5 do kliku mikrosekund, ile to bedzie zalezy od szczegolow a gadanie z kims takim jak kolega ktory nawet nei umie scisle wypowiedziec co to ma scisle liczyc jest bardzo nieprzyjemne
> > 
> > Ma to być algorytm szyfrujący. Operacje, które zadałem są, według moich przewidywań, średnim przypadkiem, który będzie trzeba obliczać. Wykonanie takich obliczeń jest równoznaczne zaszyfrowaniu 2^n * 1/20 bitów (bo trzeba wykonać 20 rund złożonych z identycznego rodzaju obliczeń), w zależności od tego jak dobierzemy n. Nie może być ono jednak za małe, bo obniży to bezpieczeństwo algorytmu. Jeśli 2^n=128, tak jak to określiłem w pierwszym poście, to oznacza, że algorytm będzie działał na blokach 128-bitowych i każdemu takiemu blokowi przypisze inny 128-bitowy, pseudolosowy blok. Szyfry 128-bitowe są takim standardem dzisiaj. Więc, jeśli czas pracy będzie niezadowalający, to może się okazać, że algorytm wielkiej kariery nie zrobi.
> > 
> > Tak jak pisałem, niedoścignionym ideałem, powszechnie dzisiaj stosowanym jest AES, który potrafi szyfrować, jak pisze wikipedia:
> > 
> > On Intel Core i3/i5/i7 and AMD Ryzen CPUs supporting AES-NI instruction set extensions, throughput can be multiple GB/s (even over 10 GB/s).
> > 
> > Czyli nawet 10 GB/s. Przy 166 mikrodekundach mój algorytm byłby w stanie zaszyfrować:
> > 
> 
> 10 GB/s ? moze oni licza to dla jakichs 32 rdzeniowych procesorow wtedy moze - nie wiem jak wydajne sa te instrukcje aes-ni ale 10 GB/s to raczej dla wielu procesorow na raz a i tak to wychodziloby kilka/kilkanascie cykli na zaszyfrowanie inta czyli bardzo malo.. mz idzie to wytlumaczyc tylko tym ze to sa dane dla wielu rdzeni 
> 
> > 1000000/166*128/20*1/2^20= 0.037 MB/s
> > 
> 
> 
> kolega jest chyab niezle pijany...
> pisalem wyzej ze jedna taka iteracja na incie (4 bajty) moze zjac gdzies w granicach 10 ns (powiedzmy, plus minus, byc moze jest to zbytni pesymizm moze zajelo by tylko 3 ns) sto zajmie wiec w okolicach 1 mikrosekundy, na sekunde wiec wyjdzie to 1M intow czyli 4 MB (na rdzen)
> 
> (byc moze jest to zbyt pesymistyczne ale chodzilo mi o zarysowanie rzedu wielkosci, jesli wziac optymistycznie ze to bedzie ze 3 razy szybsze i masz 32 rdzenie to wyjdzie 12*32 = 384 MB/s, a jesli sa te specjalne instrukcje przyspieszajace to kilka razy to moze byc kilka razy wiecej ale i tak z tym 10 GBs tu wydaje sie przesada, chyab ze to na GPU)
> 
> (jesli chodzi tylko o wywolywane tych iteracji, nie wiem czego ten algorytm wymaga i jest to za nudne dla mnie odrywac sie od ciekawszych rzeczy i tym zajmowac, sory)
> 
> ciezko sie z kolega rozmawia bo kolega ma kalasyczny syndropm nooba czyli wyglaszanie jako pewniki zbioru zalozen ktore kolega uwaza za wazne a ktore widac ze sa mozna watpliwe lub ewidentnie falszywe
> 
> > To mizernie, ale jeszcze pewnie gdzieś na pograniczu praktycznych zastosowań.
> > 
> > > wpieniajace jet tez to ze kolega sugeruje jakoby to bylo wazne pytanie a jest glupkowate i przez to traci czas ludziom
> > 
> > Ważne dla kogo? Dla mnie jest ważne. Dla ludzi zajmujących się problemem Collatza i kryptografią to pewnie też ważny temat badań. Apple zgłosiło na przykład wniosek patentowy na funkcję hashującą opartą o tego rodzaju funkcje (odrzucony):
> > 
> > https://patents.google.com/patent/US20130108038A1/en
> > 
> > Ktoś opublikował inną funkcję hashującą, korzystającą z tych ciągów (swoją drogą oceniam ją bardzo pozytywnie, myślę, że ma potencjał):
> > 
> > https://arxiv.org/pdf/1801.05079.pdf
> > 
> > Jest też generator liczb (pseudo)losowych bazujący na ciągach Collatza:
> > 
> > https://link.springer.com/article/10.1007/s41870-019-00307-9
> > 
> > Jest praca dotycząca szyfrowania obrazów, przy użyciu ciągów Collatza (na moje oko jednak dosyć naiwna i elementarna, więc raczej chleba z tej mąki nie będzie):
> > 
> > https://www.mdpi.com/1099-4300/20/12/901
> > 
> > Jest oto dosyć niszowa dziedzina matematyki teoretycznej, zaś od niedawna co niektórzy zaczęli dostrzegać w trudnościach związanych z hipotezą Collatza potencjał kryptograficzny. Nikt nie zaproponował jednak jak dotąd funkcji szyfrującej opartej o te ciągi, choć myślę, że jest tylko kwestią czasu, gdy to się stanie (wydaje się to jeszcze poza zasięgiem środowiska naukowego albo poza polem zainteresowań, większość mimo wszystko porywa się na słynną hipotezę lub twierdzenia poboczne, mające przybliżyć nas do jej rozwiązania). Dla kogoś z boku może i nie jest to ważny temat. Ale myślę, że takie Apple z pocałowaniem ręki przyjęłoby kogoś, kto sformułowałby dla nich taki algorytm i są ludzie oraz firmy, które po prostu nad tym pracują. Inna sprawa, że jest to po prostu wyabstrahowana część problemu i algorytmu, która sama w sobie może się wydawać nieinteresująca. Jednocześnie nie chcę publikować algorytmu ot tak w internecie, dopóki nie ocenię jego potencjału i nie podejmę decyzji, co z nim zrobić.
> > 
> > > jak jest kolega przy kasie to niech kolega zaplaci komus 200 zlotych i takie cos mozna napisac i przetestowac spoojnei w ciaggu kilku godzin i znajdzie sie napewno tlum chetnych
> > 
> > Współpracowałem już z programistami w różnych, prywatnych celach. Raz zleciłem napisanie programu związanego z rozwiązaniem pewnej hipotezy pobocznej związanej z hipotezą Collatza, innym razem pracowałem z pewnym programistą nad strategiami i algorytmami do gry na giełdzie. 200 zł to nie jest dla mnie problem i pewnie prędzej, czy później podejmę z kimś doraźną współpracę, żeby zrobić kompleksowe testy, w tym testy Dieharda, nie tylko pod kątem prędkości działania algorytmu. Tym bardziej, że chciałbym skomercjalizować temat, jeśli dobrze mi się wydaje, że jest coś wart. Ale, żeby udać się np. do jakiegoś funduszu zalążkowego, centrum transferu technologii, na uczelnię, czy skontaktować się z jakąś spółką technologiczną typu IBM, trzeba wiedzieć choć trochę na czym się stoi (stąd współpraca odpłatna i wstępne napisane kodu oraz testy są nieuniknione, wiem o tym). Zanim to jednak zrobię chciałem się choć wstępnie zorientować na co się nastawiać.

do tego oczywiscie powiedzialbym cos wiecej gdybym sie tym ineteresowal ale nei znam sie na szyfrowaniu i nei interesuje sie tym..umiem z grubsza iszaciowac ile cos moze zajac na cpu ale
to tez wymaga ode mnei wiedzy o co dokladie chodzi - a poztym podejrzewam ze cale to pytanie jest niewiele warte

kolega powinien zrozumeic ze jak to dobrze napisac to zajmie to tyle samo jak innym ludziom ktorzy to dobrze napisali 

oczywiscie jak nad czyms popracowac i czlowiek jest dobry to mzoe wymyslec jakis inny algorytm ale to wymaga sporo roboty i raczej ta optymalizacja bedzie wlasnie na poziomie matematyki czy budowania jakichs ciekawych konstrukcji w kodzie a nie na poziomie asemblera

Back to pl.comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Ile zajmie komputerowi mnożenie liczb rzędu 2^128 osobliwy.nick@gmail.com - 2019-12-03 15:19 -0800
  Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 "Radoslaw Szwed" <radekszwed@pochta.fm> - 2019-12-04 10:41 +0100
    Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 "Radoslaw Szwed" <radekszwed@pochta.fm> - 2019-12-04 11:55 +0100
      Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 osobliwy.nick@gmail.com - 2019-12-04 03:43 -0800
        Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 Piotr Chamera <piotr_chamera@poczta.onet.pl> - 2019-12-04 13:25 +0100
          Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 osobliwy.nick@gmail.com - 2019-12-04 04:46 -0800
  Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 Piotr Chamera <piotr_chamera@poczta.onet.pl> - 2019-12-04 13:02 +0100
    Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 osobliwy.nick@gmail.com - 2019-12-04 04:55 -0800
      Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 fir <profesor.fir@gmail.com> - 2019-12-04 16:19 -0800
        Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 osobliwy.nick@gmail.com - 2019-12-04 18:11 -0800
          Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 osobliwy.nick@gmail.com - 2019-12-04 18:12 -0800
          Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 fir <profesor.fir@gmail.com> - 2019-12-05 01:17 -0800
            Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 osobliwy.nick@gmail.com - 2019-12-05 12:18 -0800
              Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 fir <profesor.fir@gmail.com> - 2019-12-07 13:17 -0800
                Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 osobliwy nick <osobliwy.nick@gmail.com> - 2019-12-10 18:09 -0800
                Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 fir <profesor.fir@gmail.com> - 2019-12-12 05:09 -0800
                Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 fir <profesor.fir@gmail.com> - 2019-12-12 05:16 -0800
                Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 osobliwy nick <osobliwy.nick@gmail.com> - 2019-12-12 21:42 -0800
                Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 Piotr Chamera <piotr_chamera@poczta.onet.pl> - 2019-12-13 08:34 +0100
                Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 osobliwy nick <osobliwy.nick@gmail.com> - 2019-12-13 16:59 -0800
                Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 fir <profesor.fir@gmail.com> - 2019-12-13 06:17 -0800
                Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 osobliwy nick <osobliwy.nick@gmail.com> - 2019-12-13 16:56 -0800
                Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 fir <profesor.fir@gmail.com> - 2019-12-14 03:14 -0800
              Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 fir <profesor.fir@gmail.com> - 2019-12-07 13:22 -0800
  Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 "Radoslaw Szwed" <radekszwed@pochta.fm> - 2019-12-10 10:29 +0100
    Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 osobliwy nick <osobliwy.nick@gmail.com> - 2019-12-10 18:24 -0800
  Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 osobliwy nick <osobliwy.nick@gmail.com> - 2019-12-11 21:15 -0800
  Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 osobliwy nick <osobliwy.nick@gmail.com> - 2020-05-25 12:55 -0700
    Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 fir <profesor.fir@gmail.com> - 2020-05-26 01:35 -0700
      Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 osobliwy nick <osobliwy.nick@gmail.com> - 2020-05-27 12:12 -0700
        Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 fir <profesor.fir@gmail.com> - 2020-05-27 13:58 -0700
          Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 fir <profesor.fir@gmail.com> - 2020-05-27 14:03 -0700

csiph-web