-
21. Data: 2019-12-12 14:16:13
Temat: Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128
Od: fir <p...@g...com>
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
-
22. Data: 2019-12-13 06:42:33
Temat: Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128
Od: osobliwy nick <o...@g...com>
> 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
Nie wiem dokładnie jak działa AES. Tutaj jest popularno-naukowe wyjaśnienie:
https://www.youtube.com/watch?v=O4xNJsjtN6E
nie wiem jednak, czy może być coś warte na poziomie szczegółowości, którego
potrzebujemy. Przeglądałem jakiś czas temu dokumentację AES'a zamieszczoną przez NSA,
ale tylko ją przejrzałem, nie mogę powiedzieć, że wiem dokładnie jak działa ten
algorytm.
Natomiast dobrze udokumentowanym algorytmem jest w wielu aspektach podobny do niego
DES. Łatwo znaleźć informacje co robi DES - to są mniej więcej tego rodzaju
przekształcenia. Nie mam natomiast kompletnie pojęcia, czy mogą być one realizowane
aż tak szybko. Nie umiem też stwierdzić na podstawie notek wikipedii co za procesory
tam były używane. Jak pisze wikipedia:
"W przypadku mikroprocesorów klasy Pentium Pro, szyfrowanie za pomocą AES'a wymaga 18
cykli zegara na każdy bajt, co jest równoznaczne z wydajnością rzędu 11 MB/s dla
procesora 200 MHz. Z kolei na procesorze klasy Pentium M o szybkości 1.7 GHz
wydajność wynosi ok. 60 MB/s.
Na procesorach Intel Core i3/i5/i7, AMD APU a także na procesorach AMD FX
wspierających zestaw instrukcji AES, wydajność może przekroczyć 700 MB/s na każdy
wątek."
Procesor klasy pentium M o szybkości 1,7 GHz, to po prostu procesor 1,7 GHz, ma chyba
jeden rdzeń. Nie wiem, nie znam się na procesorach, wiem tyle, co przeczytałem o tym
procesorze na wikipedii.
> > 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)
166 mikrosekund wziąłem z wyliczeń Piotra Chamera. Z tego co Ty napisałeś wynika zaś,
że można to zrobić 50 razy szybciej. 10 nanosekund dla 64-bitowych liczb na iterację,
dla 128-bitowych - 3 razy wolniej, czyli 30 nanosekund. To daje 128*30=3840
nanosekund na 128 iteracji (czyli 3,84 mikrosekund). Wówczas wychodzi:
1000000/3,84*128/20*1/2^20 = 1,59 MB/s
Nie rozumiem w takim razie tylko skąd taka rozbieżność pomiędzy tym co piszesz Ty, a
tym co policzył Piotra Chamera.
> (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)
No tak, przy 32 rdzeniach wygląda to świetnie. Ale te dane dla AES'a na procesorze
klasy Pentium M o szybkości 1.7 GHz chyba nie dotyczą 32 rdzeni, tylko jednego?
> 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
Chodzi Ci o te szacunki dot. AES'a? Tutaj:
https://crypto.stackexchange.com/questions/52958/is-
there-an-encryption-algorithm-which-is-a-magnitude-f
aster-than-aes-with-wea
ktoś pisze, że:
"A classical table-based AES implementation would achieve about 160 MB/s on my
current computer (a fairly recent MacBook Pro)"
Czyli jeszcze więcej. Może czegoś z tego nie rozumiem. Ile rdzeni ma ten MacBook Pro?
Chyba 6-8? Raczej nie 32.
-
23. Data: 2019-12-13 08:34:34
Temat: Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128
Od: Piotr Chamera <p...@p...onet.pl>
W dniu 2019-12-13 o 06:42, osobliwy nick pisze:
> 166 mikrosekund wziąłem z wyliczeń Piotra Chamera. Z tego co Ty napisałeś wynika
zaś, że można to zrobić 50 razy szybciej. 10 nanosekund dla 64-bitowych liczb na
iterację, dla 128-bitowych - 3 razy wolniej, czyli 30 nanosekund. To daje 128*30=3840
nanosekund na 128 iteracji (czyli 3,84 mikrosekund). Wówczas wychodzi:
>
> 1000000/3,84*128/20*1/2^20 = 1,59 MB/s
>
> Nie rozumiem w takim razie tylko skąd taka rozbieżność pomiędzy tym co piszesz Ty,
a tym co policzył Piotra Chamera.
Muszę się odezwać, bo tu jakieś absurdy wychodzą. Napisałem na szybko
zupełnie niezoptymalizowany program, który policzył przykładowy algorytm
w 166 ms. O czym to świadczy? Tylko o tym, że bez wysiłku można taki
czas uzyskać. Trzeba też wziąć pod uwagę, że jest to program zupełnie
bez ograniczeń na to jak duże są liczby, czy są całkowite itp.
Kolega fir oszacował, że ten sam algorytm można policzyć wielokrotnie
szybciej i to też prawda. Szczególnie jeśli da się ustalić, że wszystko
da się np. policzyć na 128 bitowych liczbach całkowitych bez znaku :)
O ile to będzie szybciej okaże się kiedy ktoś to napisze w konkretnym
języku, skompiluje i uruchomi na konkretnym procesorze (50 razy szybciej
względem mojego przykładu jest jak najbardziej realne :).
-
24. Data: 2019-12-13 15:17:15
Temat: Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128
Od: fir <p...@g...com>
W dniu piątek, 13 grudnia 2019 06:42:35 UTC+1 użytkownik osobliwy nick napisał:
> > 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
>
> Nie wiem dokładnie jak działa AES. Tutaj jest popularno-naukowe wyjaśnienie:
>
> https://www.youtube.com/watch?v=O4xNJsjtN6E
>
> nie wiem jednak, czy może być coś warte na poziomie szczegółowości, którego
potrzebujemy. Przeglądałem jakiś czas temu dokumentację AES'a zamieszczoną przez NSA,
ale tylko ją przejrzałem, nie mogę powiedzieć, że wiem dokładnie jak działa ten
algorytm.
>
> Natomiast dobrze udokumentowanym algorytmem jest w wielu aspektach podobny do niego
DES. Łatwo znaleźć informacje co robi DES - to są mniej więcej tego rodzaju
przekształcenia. Nie mam natomiast kompletnie pojęcia, czy mogą być one realizowane
aż tak szybko. Nie umiem też stwierdzić na podstawie notek wikipedii co za procesory
tam były używane. Jak pisze wikipedia:
>
> "W przypadku mikroprocesorów klasy Pentium Pro, szyfrowanie za pomocą AES'a wymaga
18 cykli zegara na każdy bajt, co jest równoznaczne z wydajnością rzędu 11 MB/s dla
procesora 200 MHz. Z kolei na procesorze klasy Pentium M o szybkości 1.7 GHz
wydajność wynosi ok. 60 MB/s.
>
> Na procesorach Intel Core i3/i5/i7, AMD APU a także na procesorach AMD FX
wspierających zestaw instrukcji AES, wydajność może przekroczyć 700 MB/s na każdy
wątek."
>
> Procesor klasy pentium M o szybkości 1,7 GHz, to po prostu procesor 1,7 GHz, ma
chyba jeden rdzeń. Nie wiem, nie znam się na procesorach, wiem tyle, co przeczytałem
o tym procesorze na wikipedii.
>
> > > 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)
>
> 166 mikrosekund wziąłem z wyliczeń Piotra Chamera. Z tego co Ty napisałeś wynika
zaś, że można to zrobić 50 razy szybciej. 10 nanosekund dla 64-bitowych liczb na
iterację, dla 128-bitowych - 3 razy wolniej, czyli 30 nanosekund. To daje 128*30=3840
nanosekund na 128 iteracji (czyli 3,84 mikrosekund). Wówczas wychodzi:
>
> 1000000/3,84*128/20*1/2^20 = 1,59 MB/s
>
> Nie rozumiem w takim razie tylko skąd taka rozbieżność pomiędzy tym co piszesz Ty,
a tym co policzył Piotra Chamera.
>
> > (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)
>
> No tak, przy 32 rdzeniach wygląda to świetnie. Ale te dane dla AES'a na procesorze
klasy Pentium M o szybkości 1.7 GHz chyba nie dotyczą 32 rdzeni, tylko jednego?
>
> > 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
>
> Chodzi Ci o te szacunki dot. AES'a? Tutaj:
>
> https://crypto.stackexchange.com/questions/52958/is-
there-an-encryption-algorithm-which-is-a-magnitude-f
aster-than-aes-with-wea
>
> ktoś pisze, że:
>
> "A classical table-based AES implementation would achieve about 160 MB/s on my
current computer (a fairly recent MacBook Pro)"
>
> Czyli jeszcze więcej. Może czegoś z tego nie rozumiem. Ile rdzeni ma ten MacBook
Pro? Chyba 6-8? Raczej nie 32.
tlumaczyl;em ci jak to sie szacuje byc zrozumial i nie bil piany na grupie, znasz
chyba jakies elementarne podstawy asemblera?
takie cos
> f(x) = a/2*x + b/2 - gdy x jest nieparzyste
> f(x) = x/2 - gdy x jest parzyste
w asemblerze bedzie wygladalo z grubsza jako
loop:
mov eax, x
jp l2
shr eax, 1
mov x, eax
jmp loop
l2:
mov eax, a
shr eax, 1 ; eax = a/2
mul eax, x ; eax = a/2*x
mov ebx, b
shr ebx, 1
add eax, ebx ; eax = a/2*x + b/2
mov x, eac
jmp loop
choc w praktyce to zapisywanie do x'a byloby pominiete
ile to zajmie liczy sie tak ze mozesz z grubsza zalocyc ze jedno mov zajmuje okolo 1
cykla , shr okolo 2 cykl, mul okolo 2 cykle , skoki okolo 2 cykle (kiedys to bylo
wiecej, zalezy od procka)
ile zajmuje kazda komenda dla konkretnego procesora mozesz sprawdzic tutaj
https://www.agner.org/optimize/instruction_tables.pd
f
patrz na kolumny latency i troughput,
troughput to jest wydajnosc gdy poszzegolne komendy nie blokuja sie za bardzo tj gdy
np kolejna nie musi czekac na wynik poprzednie, latency to jest ta
bardziej pesymistyczna wartosc gdy komendy od siebie zaleza
ja patrzylem dla skylake czyli okolo strony 240
zrozum podstawy i przestaniesz bic piane,
pytanie jest zasadniczo ok ale jako ze malo znasz si ena tym temacie to gdy piszesz
rozne eleboraty to jakby siejesz niekompetencje i to jest troche denerwujace
ile to konkretnie trwa najlepiej nalezy sprawdzi samemu, trzeba to wtedy napsiac w c
lub w asmie i samemu odpalic, komputer umozliwia r obienie doklednych testow i nei ma
z tym problemu... jak masz kilka stowek czy tysiaka do wydania to moge ci potestowac
za kase co tam chcesz i udzilic ci tez konsultacji ale nie pale sie do tego bo jestem
zmeczony leniwy i nie mam wprawy w zalatwianiu formalnosci - z drugiej strony robic
tego za darmo mi sie nie chce bo mam ciekawsze rzezy do roboty. pzdr
-
25. Data: 2019-12-14 01:56:44
Temat: Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128
Od: osobliwy nick <o...@g...com>
> tlumaczyl;em ci jak to sie szacuje byc zrozumial i nie bil piany na grupie
Nie biję piany :)
> znasz chyba jakies elementarne podstawy asemblera?
Nie.
> zrozum podstawy i przestaniesz bic piane
To albo mam zrozumieć podstawy, albo przestać bić pianę. Bez pytań i odpowiedzi o te
podstawy raczej ich nie zrozumiem.
> pytanie jest zasadniczo ok ale jako ze malo znasz si ena tym temacie to gdy piszesz
rozne eleboraty to jakby siejesz niekompetencje i to jest troche denerwujace
Ja próbuję tylko oszacować ten prosty czas, w odpowiedzi na wydawałoby się proste
pytanie. Ale wszystko wskazuje na to, że chyba nie jest ono wcale takie proste i
wszystko rozbija się o niuanse i szczegóły. Tym bardziej dla mnie, skoro jestem dosyć
zielony w temacie programowania i optymalizacji.
> ile to konkretnie trwa najlepiej nalezy sprawdzi samemu, trzeba to wtedy napsiac w
c lub w asmie i samemu odpalic, komputer umozliwia r obienie doklednych testow i nei
ma z tym problemu... jak masz kilka stowek czy tysiaka do wydania to moge ci
potestowac za kase co tam chcesz i udzilic ci tez konsultacji ale nie pale sie do
tego bo jestem zmeczony leniwy i nie mam wprawy w zalatwianiu formalnosci - z
drugiej strony robic tego za darmo mi sie nie chce bo mam ciekawsze rzezy do roboty
Jestem skłonny zapłacić komuś za konkretne testy, ale Twojej wypowiedzi nie traktuję
jako propozycji, tylko danie mi do zrozumienia, że bardziej szczegółowa odpowiedź
wymaga nakładu pracy, której Ci się nie chcę ot tak wykonywać dla jakiegoś anonima z
internetu. Sam napisałeś wielokrotnie, że problem Cię nie interesuje, a moja osoba,
czy też sposób w jaki się wypowiadam Cię denerwuje. Nie podejmę współpracy z kimś kto
traktuje mnie jak natręta, ignoranta i petenta, a rozważany problem przyprawia go już
z góry o migrenę, to na pewno. A i Tobie nie wykonywałoby się zlecenia przyjemnie dla
kogoś takiego :)
Szukam kogoś do współpracy, ale nie na gwałt, a do tego mam jeszcze kilka innych
zagadnień związanych z tym tematem, więc wolałbym, żeby ktoś komu dam do wykonania
podobne zlecenia nie chciał mnie rozszarpać już na wstępie, ledwo po zapoznaniu się z
zadaniem :)
-
26. Data: 2019-12-14 01:59:54
Temat: Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128
Od: osobliwy nick <o...@g...com>
W dniu piątek, 13 grudnia 2019 08:34:44 UTC+1 użytkownik Piotr Chamera napisał:
> W dniu 2019-12-13 o 06:42, osobliwy nick pisze:
> > 166 mikrosekund wziąłem z wyliczeń Piotra Chamera. Z tego co Ty napisałeś wynika
zaś, że można to zrobić 50 razy szybciej. 10 nanosekund dla 64-bitowych liczb na
iterację, dla 128-bitowych - 3 razy wolniej, czyli 30 nanosekund. To daje 128*30=3840
nanosekund na 128 iteracji (czyli 3,84 mikrosekund). Wówczas wychodzi:
> >
> > 1000000/3,84*128/20*1/2^20 = 1,59 MB/s
> >
> > Nie rozumiem w takim razie tylko skąd taka rozbieżność pomiędzy tym co piszesz
Ty, a tym co policzył Piotra Chamera.
>
> Muszę się odezwać, bo tu jakieś absurdy wychodzą. Napisałem na szybko
> zupełnie niezoptymalizowany program, który policzył przykładowy algorytm
> w 166 ms. O czym to świadczy? Tylko o tym, że bez wysiłku można taki
> czas uzyskać. Trzeba też wziąć pod uwagę, że jest to program zupełnie
> bez ograniczeń na to jak duże są liczby, czy są całkowite itp.
>
> Kolega fir oszacował, że ten sam algorytm można policzyć wielokrotnie
> szybciej i to też prawda. Szczególnie jeśli da się ustalić, że wszystko
> da się np. policzyć na 128 bitowych liczbach całkowitych bez znaku :)
> O ile to będzie szybciej okaże się kiedy ktoś to napisze w konkretnym
> języku, skompiluje i uruchomi na konkretnym procesorze (50 razy szybciej
> względem mojego przykładu jest jak najbardziej realne :).
Ok, rozumiem. Nie sądziłem, że rozbieżności w zależności od tego jak napiszemy
program mogą być aż tak duże. Dobrze jednak, że istnieje potencjał na usprawnienie
tego aż o powiedzmy 2 rzędy wielkości. Reszta jest, jak rozumiem, kwestią konkretnych
testów. Będę myślał zatem o takich testach, na razie jednak takie wstępne szacunki mi
wystarczą. Wcześniej mam do rozwiązania jeszcze kilka innych problemów związanych z
algorytmem.
-
27. Data: 2019-12-14 12:14:14
Temat: Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128
Od: fir <p...@g...com>
W dniu sobota, 14 grudnia 2019 01:56:46 UTC+1 użytkownik osobliwy nick napisał:
> > tlumaczyl;em ci jak to sie szacuje byc zrozumial i nie bil piany na grupie
>
> Nie biję piany :)
>
> > znasz chyba jakies elementarne podstawy asemblera?
>
> Nie.
>
> > zrozum podstawy i przestaniesz bic piane
>
> To albo mam zrozumieć podstawy, albo przestać bić pianę. Bez pytań i odpowiedzi o
te podstawy raczej ich nie zrozumiem.
>
> > pytanie jest zasadniczo ok ale jako ze malo znasz si ena tym temacie to gdy
piszesz rozne eleboraty to jakby siejesz niekompetencje i to jest troche denerwujace
>
> Ja próbuję tylko oszacować ten prosty czas, w odpowiedzi na wydawałoby się proste
pytanie. Ale wszystko wskazuje na to, że chyba nie jest ono wcale takie proste i
wszystko rozbija się o niuanse i szczegóły. Tym bardziej dla mnie, skoro jestem dosyć
zielony w temacie programowania i optymalizacji.
>
> > ile to konkretnie trwa najlepiej nalezy sprawdzi samemu, trzeba to wtedy napsiac
w c lub w asmie i samemu odpalic, komputer umozliwia r obienie doklednych testow i
nei ma z tym problemu... jak masz kilka stowek czy tysiaka do wydania to moge ci
potestowac za kase co tam chcesz i udzilic ci tez konsultacji ale nie pale sie do
tego bo jestem zmeczony leniwy i nie mam wprawy w zalatwianiu formalnosci - z
drugiej strony robic tego za darmo mi sie nie chce bo mam ciekawsze rzezy do roboty
>
> Jestem skłonny zapłacić komuś za konkretne testy, ale Twojej wypowiedzi nie
traktuję jako propozycji, tylko danie mi do zrozumienia, że bardziej szczegółowa
odpowiedź wymaga nakładu pracy, której Ci się nie chcę ot tak wykonywać dla jakiegoś
anonima z internetu. Sam napisałeś wielokrotnie, że problem Cię nie interesuje, a
moja osoba, czy też sposób w jaki się wypowiadam Cię denerwuje. Nie podejmę
współpracy z kimś kto traktuje mnie jak natręta, ignoranta i petenta, a rozważany
problem przyprawia go już z góry o migrenę, to na pewno. A i Tobie nie wykonywałoby
się zlecenia przyjemnie dla kogoś takiego :)
>
> Szukam kogoś do współpracy, ale nie na gwałt, a do tego mam jeszcze kilka innych
zagadnień związanych z tym tematem, więc wolałbym, żeby ktoś komu dam do wykonania
podobne zlecenia nie chciał mnie rozszarpać już na wstępie, ledwo po zapoznaniu się z
zadaniem :)
bije kolega piane nieststy, bieice piany polega tu na zestawieniu kogos kto nei
chwyta jak tos ie robi (szacuje ile konkretne obliczenie bedzie trwac) z kims kto to
chwyta i powtarzaniu swojej niekompetencji i przeswiadczen zamiast zrozumieniu o co
chodzi, nop w ostatnim poscie napisalem to bardzo dobrze
co do zaplacenai za konsulatacje, to suepr ze nie bo ciezko sie z kolega meczy choc
kolega nawiasem mowiac traci dosyc enna szanse (bo ja z optymalizacji na cpu jestem
dosyc ogarniety i mam nie taka czesta do spotkania dobra wiedze) ale to kolegi strata
a nie moja..jako ze kolega bije piana i tak raczej wiadomo ze chodzi o bicie piany a
nei o zrobienie czegos naprawde
-
28. Data: 2020-05-25 21:55:22
Temat: Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128
Od: osobliwy nick <o...@g...com>
Jeśli kogoś to interesuje, to oto jak szybki jest AES:
https://crypto.stackexchange.com/questions/44927/how
-long-does-a-good-aes-encryption-take
W 6 sekund szyfruje 1 GB! A poniżej użytkownik pisze, że można zejść nawet do 1 GB w
0,6 sekund.
-
29. Data: 2020-05-26 10:35:37
Temat: Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128
Od: fir <p...@g...com>
W dniu poniedziałek, 25 maja 2020 21:55:24 UTC+2 użytkownik osobliwy nick napisał:
> Jeśli kogoś to interesuje, to oto jak szybki jest AES:
>
> https://crypto.stackexchange.com/questions/44927/how
-long-does-a-good-aes-encryption-take
>
> W 6 sekund szyfruje 1 GB! A poniżej użytkownik pisze, że można zejść nawet do 1 GB
w 0,6 sekund.
przy sprzetowej akceleracji...
problem z userami takimi jak ty jest takiz e probujesz oswiecac grupe nie znajac sie
na tym o czym mowisz co skutecznie czesto (w przypadku tego typu podejscia) prowoduje
sianie ciemnoty... (ja sam osobiscie maga nie cierpie takich ludzi bo grupa jest od
siania wlasnie wiedzy a nie degenerowania jej i siania ciemnoty)
-
30. Data: 2020-05-27 21:12:01
Temat: Re: Ile zajmie komputerowi mnożenie liczb rzędu 2^128
Od: osobliwy nick <o...@g...com>
W dniu wtorek, 26 maja 2020 10:35:38 UTC+2 użytkownik fir napisał:
> W dniu poniedziałek, 25 maja 2020 21:55:24 UTC+2 użytkownik osobliwy nick napisał:
> > Jeśli kogoś to interesuje, to oto jak szybki jest AES:
> >
> > https://crypto.stackexchange.com/questions/44927/how
-long-does-a-good-aes-encryption-take
> >
> > W 6 sekund szyfruje 1 GB! A poniżej użytkownik pisze, że można zejść nawet do 1
GB w 0,6 sekund.
>
> przy sprzetowej akceleracji...
Aha, tego nie wziąłem pod uwagę. Dotarłem do kodu AESa w Pythonie 3. Jeśli się nie
mylę, to jest przykładowa implementacja tego szyfru:
https://github.com/boppreh/aes/blob/master/aes.py
Nie potrafię tego uruchomić. A chcę to porównać z moim kodem, który także mam w
Pythonie 2. Przykładowy zestaw kluczy:
#!/usr/bin/python
from sys import argv
keys=eval(argv[1]) # list of function selectors aka the key
v=eval(argv[2]) # endianness vector
r=len(keys) # nmbr rounds implied by keys
bo=int(argv[3]) # nmbr of bits out
pt=int(argv[4]) # the plaintext
parms=[-7,-5,-3,3,5,7]
rf=[(parms[i/6],parms[i%6],2) for i in
range(36)]+[(parms[i/6],parms[i%6],-2) for i in range(36)]
def swapendian(x, nmbrbits):
s=0
for i in range(nmbrbits):
s+=2**(nmbrbits-i-1)*((x>>i)%2)
return s
def genf(a,b,c):
def f(x):
if x % 2 == 1:
return ((x * a + b)/2,1)
return (x/c,0)
return f
def round(s,a,b,c,n):
f=genf(a,b,c)
o=0
for i in range(0,n):
(s,ct)=f(s)
o+=ct*2**i
return swapendian(o,n)
def encrypt(pt,r,keys,v):
ct = pt
for i in range(r):
if v[i] == 1:
ct=swapendian(ct,bo)
(a,b,c)=rf[keys[i]]
ct=round(ct,a,b,c,bo)
return ct
print encrypt(pt,r,keys,v)
Uruchamiamy to komendą:
python main.py '[67,65,64,63,67,68,67,65,70,68,71,64,69,71,70,65,68
,66,67,70]' '[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]' 128 123
Przy czym "123", to szyfrowana liczba, możemy podać dowolną liczbę 128-bitową.
Pytanie, czy mój kod będzie szybszy niż AES. BTW - kod nie jest mojego autorstwa,
koledzy z innego forum mi pomogli. Na oko wygląda, że tak. Nie jestem pewien też, czy
dobry kod AESa znalazłem i czy to jest cały AES, czy coś tam poupraszczali. Ktoś umie
uruchomić tego AESa?
> problem z userami takimi jak ty jest takiz e probujesz oswiecac grupe nie znajac
sie na tym o czym mowisz co skutecznie czesto (w przypadku tego typu podejscia)
prowoduje sianie ciemnoty... (ja sam osobiscie maga nie cierpie takich ludzi bo grupa
jest od siania wlasnie wiedzy a nie degenerowania jej i siania ciemnoty)
Nigdzie nie napisali o akceleracji sprzętowej, nie miałem pojęcia jakie to może mieć
znaczenie. W tej chwili mam kod, jak widać powyżej, który uruchamiam w:
https://repl.it/languages/python
Bo jeszcze nie nauczyłem się nawet instalować Pythona u siebie na kompie (a nie wiem
co za procesor obsługuje ten intepreter). I muszę dojść do tego ile szyfrowanie
zajmie AESowi, a ile mojemu algorytmowi.