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

[o***@gmail.com]

Cześć. Badam pewne funkcje pod kątem zastosowań kryptograficznych. I mam następujący problem. Muszę oszacować ile czasu zajmie mnożenie liczby 2^128-5, z dodawaniem. Konkretnie - w pierwszym kroku obliczamy (2^128-5)*2,5+2,5, następnie dzielimy całość przez 2. A potem znów wynik mnożymy razy 2,5 i dodajemy 2,5. I znów dzielimy wynik przez 2. Musimy w sumie wykonać 128 takich operacji, to jest 64 mnożenia z dodawaniem i 64 dzielenia przez 2.

Dosyć łatwo wykazać, że liczba końcowa będzie całkowita i każda liczba uzyskana po drodze też będzie całkowita. Ale nie chodzi mi o wynik, tylko o sprawdzenie ile komputerowi zajmie policzenie czegoś takiego.

Zaznaczę, że dla tak dużych liczb szybko tracona jest precyzja. Jestem laikiem, ale z tego co wiem trzeba do tego albo specjalnych bibliotek albo jakichś własnych rozwiązań do wykonywania obliczeń na tak dużych liczbach (które pewnie będą znacznie wolniejsze, niż dedykowane, specjalne biblioteki, które stworzyli np. naukowcy do różnych zaawansowanych obliczeń).

Czy ktoś jest w stanie wykonać takie obliczenia i zmierzyć czas? A może możecie podsunąć jakiś sensowny sposób oszacowania tego?

[Radoslaw Szwed]

Post by o***@gmail.com
Cześć. Badam pewne funkcje pod kątem zastosowań kryptograficznych. I mam następujący problem. Muszę oszacować ile czasu zajmie
mnożenie liczby 2^128-5, z dodawaniem. Konkretnie - w pierwszym kroku obliczamy (2^128-5)*2,5+2,5, następnie dzielimy całość przez
2. A potem znów wynik mnożymy razy 2,5 i dodajemy 2,5. I znów dzielimy wynik przez 2. Musimy w sumie wykonać 128 takich operacji,
to jest 64 mnożenia z dodawaniem i 64 dzielenia przez 2.
Dosyć łatwo wykazać, że liczba końcowa będzie całkowita i każda liczba uzyskana po drodze też będzie całkowita. ...

Naprawdę będzie całkowita? Tak z ciekawości sprawdziłem dla 2^64

2^64 -5= 18446744073709551611 * 2,5= 46116860184273879027,5 +2,5= 46116860184273879030 /2
=23058430092136939515 * 2,5 =57646075230342348787,5 +2,5 = 57646075230342348790 /2 =
28823037615171174395 *2,5= 72057594037927935993,75 + 2,5 ...

[Radoslaw Szwed]

Post by Radoslaw Szwed

Post by o***@gmail.com
Cześć. Badam pewne funkcje pod kątem zastosowań kryptograficznych. I mam następujący problem. Muszę oszacować ile czasu zajmie
mnożenie liczby 2^128-5, z dodawaniem. Konkretnie - w pierwszym kroku obliczamy (2^128-5)*2,5+2,5, następnie dzielimy całość
przez 2. A potem znów wynik mnożymy razy 2,5 i dodajemy 2,5. I znów dzielimy wynik przez 2. Musimy w sumie wykonać 128 takich
operacji, to jest 64 mnożenia z dodawaniem i 64 dzielenia przez 2.
Dosyć łatwo wykazać, że liczba końcowa będzie całkowita i każda liczba uzyskana po drodze też będzie całkowita. ...

Naprawdę będzie całkowita? Tak z ciekawości sprawdziłem dla 2^64
2^64 -5= 18446744073709551611 * 2,5= 46116860184273879027,5 +2,5= 46116860184273879030 /2
=23058430092136939515 * 2,5 =57646075230342348787,5 +2,5 = 57646075230342348790 /2 =
28823037615171174395 *2,5= 72057594037927935993,75 + 2,5 ...

Coś mi się źle wymnożyło :)

[o***@gmail.com]

Post by Radoslaw Szwed

Post by Radoslaw Szwed
Naprawdę będzie całkowita? Tak z ciekawości sprawdziłem dla 2^64
2^64 -5= 18446744073709551611 * 2,5= 46116860184273879027,5 +2,5= 46116860184273879030 /2
=23058430092136939515 * 2,5 =57646075230342348787,5 +2,5 = 57646075230342348790 /2 =
28823037615171174395 *2,5= 72057594037927935993,75 + 2,5 ...

Coś mi się źle wymnożyło :)

Chyba tak. Kilka pierwszych wyrazów:

850705917302346158658436518579420528630

425352958651173079329218259289710264315

1063382396627932698323045648224275660790

531691198313966349161522824112137830395

1329227995784915872903807060280344575990

664613997892457936451903530140172287995

1661534994731144841129758825350430719990

830767497365572420564879412675215359995

2076918743413931051412198531688038399990

1038459371706965525706099265844019199995

[Piotr Chamera]

Post by o***@gmail.com

Post by Radoslaw Szwed

Post by Radoslaw Szwed
Naprawdę będzie całkowita? Tak z ciekawości sprawdziłem dla 2^64
2^64 -5= 18446744073709551611 * 2,5= 46116860184273879027,5 +2,5= 46116860184273879030 /2
=23058430092136939515 * 2,5 =57646075230342348787,5 +2,5 = 57646075230342348790 /2 =
28823037615171174395 *2,5= 72057594037927935993,75 + 2,5 ...

Coś mi się źle wymnożyło :)

850705917302346158658436518579420528630
425352958651173079329218259289710264315
1063382396627932698323045648224275660790
531691198313966349161522824112137830395
1329227995784915872903807060280344575990
664613997892457936451903530140172287995
1661534994731144841129758825350430719990
830767497365572420564879412675215359995
2076918743413931051412198531688038399990
1038459371706965525706099265844019199995

Jeśli się gdzieś nie pomyliłem, to komplet wyników
pośrednich (po mnożeniu, dodawaniu i dzieleniu) to:

340282366920938463463374607431768211451
425352958651173079329218259289710264315
531691198313966349161522824112137830395
664613997892457936451903530140172287995
830767497365572420564879412675215359995
1038459371706965525706099265844019199995
1298074214633706907132624082305023999995
1622592768292133633915780102881279999995
2028240960365167042394725128601599999995
2535301200456458802993406410751999999995
3169126500570573503741758013439999999995
3961408125713216879677197516799999999995
4951760157141521099596496895999999999995
6189700196426901374495621119999999999995
7737125245533626718119526399999999999995
9671406556917033397649407999999999999995
12089258196146291747061759999999999999995
15111572745182864683827199999999999999995
18889465931478580854783999999999999999995
23611832414348226068479999999999999999995
29514790517935282585599999999999999999995
36893488147419103231999999999999999999995
46116860184273879039999999999999999999995
57646075230342348799999999999999999999995
72057594037927935999999999999999999999995
90071992547409919999999999999999999999995
112589990684262399999999999999999999999995
140737488355327999999999999999999999999995
175921860444159999999999999999999999999995
219902325555199999999999999999999999999995
274877906943999999999999999999999999999995
343597383679999999999999999999999999999995
429496729599999999999999999999999999999995
536870911999999999999999999999999999999995
671088639999999999999999999999999999999995
838860799999999999999999999999999999999995
1048575999999999999999999999999999999999995
1310719999999999999999999999999999999999995
1638399999999999999999999999999999999999995
2047999999999999999999999999999999999999995
2559999999999999999999999999999999999999995
3199999999999999999999999999999999999999995
3999999999999999999999999999999999999999995
4999999999999999999999999999999999999999995
6249999999999999999999999999999999999999995
7812499999999999999999999999999999999999995
9765624999999999999999999999999999999999995
12207031249999999999999999999999999999999995
15258789062499999999999999999999999999999995
19073486328124999999999999999999999999999995
23841857910156249999999999999999999999999995
29802322387695312499999999999999999999999995
37252902984619140624999999999999999999999995
46566128730773925781249999999999999999999995
58207660913467407226562499999999999999999995
72759576141834259033203124999999999999999995
90949470177292823791503906249999999999999995
113686837721616029739379882812499999999999995
142108547152020037174224853515624999999999995
177635683940025046467781066894531249999999995
222044604925031308084726333618164062499999995
277555756156289135105907917022705078124999995
346944695195361418882384896278381347656249995
433680868994201773602981120347976684570312495
542101086242752217003726400434970855712890620

ale dalsze iteracje już są ułamkowe.

dla 2^64 całkowite są tylko do 32 iteracji:

18446744073709551611
23058430092136939515
28823037615171174395
36028797018963967995
45035996273704959995
56294995342131199995
70368744177663999995
87960930222079999995
109951162777599999995
137438953471999999995
171798691839999999995
214748364799999999995
268435455999999999995
335544319999999999995
419430399999999999995
524287999999999999995
655359999999999999995
819199999999999999995
1023999999999999999995
1279999999999999999995
1599999999999999999995
1999999999999999999995
2499999999999999999995
3124999999999999999995
3906249999999999999995
4882812499999999999995
6103515624999999999995
7629394531249999999995
9536743164062499999995
11920928955078124999995
14901161193847656249995
18626451492309570312495
23283064365386962890620
116415321826934814453105/4
582076609134674072265545/16
2910383045673370361327805/64
14551915228366851806639345/256
72759576141834259033198005/1024
363797880709171295165995145/4096
1818989403545856475829996205/16384
9094947017729282379150062945/65536
45474735088646411895750642405/262144
227373675443232059478754522745/1048576
1136868377216160297393777856605/4194304
5684341886080801486968910254545/16777216
28421709430404007434844635158805/67108864
142108547152020037174223511338345/268435456
710542735760100185871118898869005/1073741824
3552713678800500929355599863054145/4294967296
17763568394002504646778020790107205/17179869184
88817841970012523233890189849881945/68719476736
444089209850062616169451292846793405/274877906944
2220446049250313080847257838623501745/1099511627776
11102230246251565404236294690675647605/4398046511104
55511151231257827021181495443610793545/17592186044416
277555756156289135105907565178984189805/70368744177664
1387778780781445675529538177738641837345/281474976710656
6938893903907228377647692296068092740005/1125899906842624
34694469519536141888238467109839997913145/4503599627370496
173472347597680709441192358067198126418205/18014398509481984
867361737988403547205961880407983179500945/72057594037927936
4336808689942017736029809762327886087144405/288230376151711744
21684043449710088680149050252791311194280745/1152921504606846976
108420217248550443400745257028564079005638605/4611686018427387904
542101086242752217003726308201250487165132545/18446744073709551616

[o***@gmail.com]

Post by Piotr Chamera
ale dalsze iteracje już są ułamkowe.

Zgadza się. Traktujesz mnożenie z dzieleniem jako jedną operację. Natomiast są to dwie operacje.
To też się zgadza. Zrobiłeś tak naprawdę 64 iteracje, wypisałeś tylko nieparzyste. Ogólnie nie można tego w żaden sposób skrócić. Trzeba liczyć tak jak jest. Czyli a*2,5+2,5=b. A dopiero później dzielimy przez 2.

To wynika z definicji funkcji, którą rozważam:

f(x) = 2,5*x+2,5 - gdy x jest nieparzyste

f(x) = x/2 - gdy x jest parzyste

Dla liczb 2^n-5 jest ją łatwo liczyć. Ale gdy spróbujemy 2^n-19, to nie ma dróg na skróty. Kolejne wyrazy raz są nieparzyste, raz parzyste - brak wyraźnego wzorca. Stąd w każdym trzeba sprawdzać ich parzystość i albo dzielić przez 2 albo mnożyć z dodawaniem. Dlatego nie chciałem, żebyście stosowali jakieś skróty, czy uproszczenia wynikające z matematyki, bo w większości przypadków nie da się ich zastosować.

[Piotr Chamera]

Post by o***@gmail.com
Cześć. Badam pewne funkcje pod kątem zastosowań kryptograficznych. I mam następujący problem. Muszę oszacować ile czasu zajmie mnożenie liczby 2^128-5, z dodawaniem. Konkretnie - w pierwszym kroku obliczamy (2^128-5)*2,5+2,5, następnie dzielimy całość przez 2. A potem znów wynik mnożymy razy 2,5 i dodajemy 2,5. I znów dzielimy wynik przez 2. Musimy w sumie wykonać 128 takich operacji, to jest 64 mnożenia z dodawaniem i 64 dzielenia przez 2.
Dosyć łatwo wykazać, że liczba końcowa będzie całkowita i każda liczba uzyskana po drodze też będzie całkowita. Ale nie chodzi mi o wynik, tylko o sprawdzenie ile komputerowi zajmie policzenie czegoś takiego.
Zaznaczę, że dla tak dużych liczb szybko tracona jest precyzja. Jestem laikiem, ale z tego co wiem trzeba do tego albo specjalnych bibliotek albo jakichś własnych rozwiązań do wykonywania obliczeń na tak dużych liczbach (które pewnie będą znacznie wolniejsze, niż dedykowane, specjalne biblioteki, które stworzyli np. naukowcy do różnych zaawansowanych obliczeń).
Czy ktoś jest w stanie wykonać takie obliczenia i zmierzyć czas? A może możecie podsunąć jakiś sensowny sposób oszacowania tego?

Rzeczywiście wychodzi liczba całkowita, ale dla pojedynczej takiej pętli
czas jest niemierzalny w tej implementacji lispu

CL-USER> (time
(let ((x (- (expt 2 128) 5)))
(dotimes (i 64)
(setf x (/ (+ (* x 5/2)
5/2)
2)))
x))

wynik:

542101086242752217003726400434970855712890620


(LET ((X (- (EXPT 2 128) 5))) (DOTIMES (I 64) (SETF X (/ (+ (* X 5/2)
5/2) 2))) X)
took 0 microseconds (0.000000 seconds) to run.
During that period, and with 6 available CPU cores,
0 microseconds (0.000000 seconds) were spent in user mode
0 microseconds (0.000000 seconds) were spent in system mode
22,592 bytes of memory allocated.

Dla 1000 powtórzeń pętli mamy

(DOTIMES (N 1000) (LET ((X (- (EXPT 2 128) 5))) (DOTIMES (I 64) (SETF X
(/ (+ (* X 5/2) 5/2) 2))) X))
took 166,000 microseconds (0.166000 seconds) to run.
9,762 microseconds (0.009762 seconds, 5.88%) of which was spent
in GC.
During that period, and with 6 available CPU cores,
156,250 microseconds (0.156250 seconds) were spent in user mode
0 microseconds (0.000000 seconds) were spent in system mode
22,528,064 bytes of memory allocated.

czyli wychodziłoby 166 mikrosekund na takie obliczenie.

Ale trzeba pamiętać, że to jest nieoptymalizowany program w lispie,
na pewno można napisać program, który policzy to szybciej.

[o***@gmail.com]

Post by Piotr Chamera
czyli wychodziłoby 166 mikrosekund na takie obliczenie.
Ale trzeba pamiętać, że to jest nieoptymalizowany program w lispie,
na pewno można napisać program, który policzy to szybciej.

Dzięki za pomoc. Niestety to dużo za dużo. Spodziewałem się wielkości o dwa rzędy mniejszej. Nawet optymalizacja nie sprawi chyba, że mogłoby to być 0,5 mikrosekundy, nie?

Generalnie chciałbym, aby było to dokładnie 0,1 lub okolice tych czasów. Jest pewien algorytm, który na procesorze klasy Pentium M o szybkości 1.7 GHz ma właśnie taką wydajność szyfrowania, bo o szyfrowanie cały czas chodzi. Oczywiście działa on zupełnie inaczej od mojego, ale muszę w takim razie tak dobrać parametry, aby zbliżyć się do tej prędkości.

Czy byłbyś w stanie sprawdzić mniejsze przypadki, np. liczbę 2^100-5 dla 100 iteracji? Ogólnie znaleźć takie n, że dla n iteracji na liczbie 2^n-5 ten czas będzie wynosił ok. 0,1 mikrosekundy?

[fir]

Post by o***@gmail.com

Post by Piotr Chamera
czyli wychodziłoby 166 mikrosekund na takie obliczenie.
Ale trzeba pamiętać, że to jest nieoptymalizowany program w lispie,
na pewno można napisać program, który policzy to szybciej.

Dzięki za pomoc. Niestety to dużo za dużo. Spodziewałem się wielkości o dwa rzędy mniejszej. Nawet optymalizacja nie sprawi chyba, że mogłoby to być 0,5 mikrosekundy, nie?
Generalnie chciałbym, aby było to dokładnie 0,1 lub okolice tych czasów. Jest pewien algorytm, który na procesorze klasy Pentium M o szybkości 1.7 GHz ma właśnie taką wydajność szyfrowania, bo o szyfrowanie cały czas chodzi. Oczywiście działa on zupełnie inaczej od mojego, ale muszę w takim razie tak dobrać parametry, aby zbliżyć się do tej prędkości.
Czy byłbyś w stanie sprawdzić mniejsze przypadki, np. liczbę 2^100-5 dla 100 iteracji? Ogólnie znaleźć takie n, że dla n iteracji na liczbie 2^n-5 ten czas będzie wynosił ok. 0,1 mikrosekundy?

troche nudne to pytanie, ale mozesz zalozyc ze proste operacje (dodawanie, mnozenei , shift) na 64 bitowym incie zajmuje w granicach 1-5 cykli (powiedzmy)

czyli w temacie zgrubnego ogarniecia mozesz zalozyc ze jedna operacje zajmuje okolo 1 nanosekunde

z tym ze taki mnozenie przez 2.5 to raczej jest mnozenie x przez dwa i dodanie polowy x czyli

((x<<1) + (x>>1)) + 2.5

4 operacje, zalozmy ze to zajmuje 4 ns (mozliwe ze w praktyce zajmie ciut mniej, moze ze 2 ns)

wiec sto iteracji tego zajmie 400 ns (200 ns?)

to przy zalozeniu ze mowimy o obliczeniach ktore sie da zrobi na 64 bitowych integerach, jak robi sie to na 128 bitowych integereach mysle ze zjamie to minimum 2 razy tyle (zief)

swoje droga esli to jest iteracja na stalej 2^128 - 5 to wynik konkretnej liczby iteracji na tym (np 100) jest znany i nie trzeba tego liczyc wiec wyliczenie tego wynosi 0 czasu (i dlatego tez niekonkretne pytaia sa nie tylko niecialawe ale i denerwujace (ziew))

[o***@gmail.com]

Post by fir
swoje droga esli to jest iteracja na stalej 2^128 - 5 to wynik konkretnej liczby iteracji na tym (np 100) jest znany i nie trzeba tego liczyc wiec wyliczenie tego wynosi 0 czasu (i dlatego tez niekonkretne pytaia sa nie tylko niecialawe ale i denerwujace (ziew))

To jest tylko część bardziej złożonego problemu nad którym się głowię. Może on wyda Ci się ciekawszy. Rozważmy funkcje rekurencyjne o następującej definicji:

f(x) = a/2*x+b/2 - gdy x jest nieparzyste
f(x) = x2 - gdy x jest parzyste

a i b to jakieś liczby nieparzyste, a x może być dowolną liczbą naturalną. Określając a i b dostajemy jakiś ciąg zdefiniowany za pomocą funkcji rekurencyjnej. Najsłynniejszym z nich jest ciąg Collatza, którego dotyczy nierozwiązania do dziś hipoteza. Ciąg Collatza dostaniemy dla a=3 i b=1. Weźmy pary a, b z przedziału (-7,-5, ..., 5, 7). Będzie ich tyle co wariacji z powtórzeniami, 2-wyrazowych, w zbiorze 8-elementowym, czyli 64. Dla każdej z takich 64 par a i b mamy zdefiniowaną jakąś funkcję rekurencyjną. To co chcę oszacować, to ile zajmie policzenie w każdej z tych 64 funkcji n iteracji dla kolejnych liczb naturalnych z przedziału od 1 do 2^n. Np. dla a=5 i b=3 oraz n=3 mamy do policzenia iteracje dla liczb 1,2,3,...,8:

1,4,2,1
2,1,4,2
3,9,24,12
4,2,1,4
5,14,7,19
6,3,9,24
7,19,49,124
8,4,2,1

Rzecz w tym, że interesują mnie duże n, rzędu minimum 50, a najlepiej rzędu 100. Nie wiem, czy to jest bardziej interesujące? Na pewno żaden komputer tego nie policzy w żadnym czasie np. dla n=128. Łatwo policzyć, że, jeśli średnio taki ciąg jest liczony np. przez 100 mikrosekund, to obliczenia dla 64 par a i b zajmą 64*100*1/1000000*2^128 sekund, czyli może jeszcze nastąpi to przed śmiercią cieplną Wszechświata, a może nie. Dlatego trzeba policzyć średni przypadek i ten, który podałem jest średnim przypadkiem, można bowiem udowodnić, że średnio w tych ciągach w przedziale liczb od 1 do 2^n wystąpi tyle samo mnożeń z dodawaniem, co dzieleń. Natomiast potrzebuję to oszacować, bo zamierzam stworzyć algorytm, który będzie się wymagał obliczenia losowego x z przedziału od 1 do 2^n dla losowej pary a i b. I chcę wiedzieć ile średnio zajmie to czasu. W szczególności jakie maksymalne n mogę przyjąć, aby taki pojedynczy ciąg był liczony około 0,1 mikrosekundy.

[o***@gmail.com]

Jeszcze raz definicja:

f(x) = a/2*x+b/2 - gdy x jest nieparzyste
f(x) = x/2 - gdy x jest parzyste

Zjadłem znak dzielnika dla x parzystych.

[fir]

Post by o***@gmail.com

Post by fir
swoje droga esli to jest iteracja na stalej 2^128 - 5 to wynik konkretnej liczby iteracji na tym (np 100) jest znany i nie trzeba tego liczyc wiec wyliczenie tego wynosi 0 czasu (i dlatego tez niekonkretne pytaia sa nie tylko niecialawe ale i denerwujace (ziew))

f(x) = a/2*x+b/2 - gdy x jest nieparzyste
f(x) = x2 - gdy x jest parzyste
1,4,2,1
2,1,4,2
3,9,24,12
4,2,1,4
5,14,7,19
6,3,9,24
7,19,49,124
8,4,2,1
Rzecz w tym, że interesują mnie duże n, rzędu minimum 50, a najlepiej rzędu 100. Nie wiem, czy to jest bardziej interesujące? Na pewno żaden komputer tego nie policzy w żadnym czasie np. dla n=128. Łatwo policzyć, że, jeśli średnio taki ciąg jest liczony np. przez 100 mikrosekund, to obliczenia dla 64 par a i b zajmą 64*100*1/1000000*2^128 sekund, czyli może jeszcze nastąpi to przed śmiercią cieplną Wszechświata, a może nie. Dlatego trzeba policzyć średni przypadek i ten, który podałem jest średnim przypadkiem, można bowiem udowodnić, że średnio w tych ciągach w przedziale liczb od 1 do 2^n wystąpi tyle samo mnożeń z dodawaniem, co dzieleń. Natomiast potrzebuję to oszacować, bo zamierzam stworzyć algorytm, który będzie się wymagał obliczenia losowego x z przedziału od 1 do 2^n dla losowej pary a i b. I chcę wiedzieć ile średnio zajmie to czasu. W szczególności jakie maksymalne n mogę przyjąć, aby taki pojedynczy ciąg był liczony około 0,1 mikrosekundy.

dla mnie to wogole nie jest interesujace, a jesli chcesz odpowiedz to raczej staraj sie zadac pytanie w jakis zachecajacy sposob (bez glupot i dziur logicznych oraz w miare krotki i nie mulace - bo ludzie sa leniwi, zwlaszcza na starosc ;c)


jak oszacowac czas obliczen napisalem
takie proste obliczenie jak dodawanie, mnozenie, i dzilenie przez dwa dla liczb calkowitych mozesz optymistycznie zalozyc zajmuja minimum jeden cykl procesora na dzialanie, ale oprocz arytmetyki moga byc tez tam movy (nalezaloby to napisac przy pomoy komend w asemblerze by to sobie zwizualizowac), dlatego jabym to pomnozyl przez 2 lub 3, do tego jesli mowa o ifie to ten juz sie robi duzo drozszy (powiedzmy z 15-20 cykli)

takie cos

Post by o***@gmail.com
f(x) = a/2*x + b/2 - gdy x jest nieparzyste
f(x) = x2 - gdy x jest parzyste

(w zaleznosci od tego czym to naprawde jest, np czy to dzielenie przed dwa ma obcinac bit..oraz czy przypadkiem nie da sie jakos usunac tego if) mozna zgrubnie oszacowac na okolo 10 nanosekund (20-30 cykli) na iteracje (mowiac srednio optymistycznie) (jesli mowimy o 64 bitowych intach, dla 128 bit bedzie chyab ze 2-3 razy wolniej)

napisz kod w c i sprawdz czy dziala (tj czy daje wogole poprawne wyniki - podejrzewam ze zanim go napiszesz to przejdziesz przez 15 wersji w ktorych bedzie dawal nipoprawne ;c i jak juz bedziesz to miec to nie ma problemu ze zmierzeniem tego - ale jesli chesz zgrubne oszacowanie to z ogory ci mowie takie rzeczy zajmuja w okolicach kilkudziesieciu cykli na iteracje (w zaleznosci od szczegolow)czyli w granicach 5,10,20, 30 nanosekund na iteracje (w zaleznosci od szczegolow)

oczywiste jest ze nie w czasie tego kawalka jest problem tylko w tej kombinatoryce a ja trzeba jakos optymalizowac w inny sposob (matematycznie, hackerskom itd..nie che mis ie w to wnikac bo to za nudne dla mnie)

[o***@gmail.com]

Post by fir
dla mnie to wogole nie jest interesujace

Kwestia gustu, mnie fascynują te problemy, zwłaszcza, że mają istotne związki z hipotezą Collatza. Chaos deterministyczny, Wolfram rules, automaty komórkowe - dla mnie to wszystko ciekawe rzeczy.

Post by fir
a jesli chcesz odpowiedz to raczej staraj sie zadac pytanie w jakis zachecajacy sposob (bez glupot i dziur logicznych oraz w miare krotki i nie mulace - bo ludzie sa leniwi, zwlaszcza na starosc ;c)

Nie wiem jaki to jest zachęcający sposób, ale wnioskuję, że po prosty zwięzły i konkretny, to masz pewnie na myśli.

Post by fir
jak oszacowac czas obliczen napisalem
takie proste obliczenie jak dodawanie, mnozenie, i dzilenie przez dwa dla liczb calkowitych mozesz optymistycznie zalozyc zajmuja minimum jeden cykl procesora na dzialanie, ale oprocz arytmetyki moga byc tez tam movy (nalezaloby to napisac przy pomoy komend w asemblerze by to sobie zwizualizowac), dlatego jabym to pomnozyl przez 2 lub 3, do tego jesli mowa o ifie to ten juz sie robi duzo drozszy (powiedzmy z 15-20 cykli)

Ok, rozumiem.

Post by fir
takie cos

Post by o***@gmail.com
f(x) = a/2*x + b/2 - gdy x jest nieparzyste
f(x) = x2 - gdy x jest parzyste

(w zaleznosci od tego czym to naprawde jest, np czy to dzielenie przed dwa ma obcinac bit..oraz czy przypadkiem nie da sie jakos usunac tego if) mozna zgrubnie oszacowac na okolo 10 nanosekund (20-30 cykli) na iteracje (mowiac srednio optymistycznie) (jesli mowimy o 64 bitowych intach, dla 128 bit bedzie chyab ze 2-3 razy wolniej)

Ok, daje mi to jakieś ogólne pojęcie.

Post by fir
napisz kod w c i sprawdz czy dziala (tj czy daje wogole poprawne wyniki - podejrzewam ze zanim go napiszesz to przejdziesz przez 15 wersji w ktorych bedzie dawal nipoprawne ;c i jak juz bedziesz to miec to nie ma problemu ze zmierzeniem tego - ale jesli chesz zgrubne oszacowanie to z ogory ci mowie takie rzeczy zajmuja w okolicach kilkudziesieciu cykli na iteracje (w zaleznosci od szczegolow)czyli w granicach 5,10,20, 30 nanosekund na iteracje (w zaleznosci od szczegolow)

Rozumiem. Czyli wszystko w sumie rozbija się w tym przypadku o napisanie konkretnego programu od A do Z i sprawdzenie tego. Dodam tylko, że nie umiem programować, zapomniałem swój kurs programowania z podstaw w C ze studiów, nie pamiętam jak uruchomić program, w czym to się kompilowało itd. Dlatego pytam Was i nie sprawdzę sobie tego sam, dopóki nie zrobię solidnej powtórki. Poza tym chciałem mieć tylko ogólne pojęcie nt. tego, czy realne jest zbliżenie się przy parametrze n=100 do czasów 0,5 mikrosekundy. Wydaje się to być możliwe, ale tak na 100% nie wiadomo.

[fir]

Post by o***@gmail.com

Post by fir
dla mnie to wogole nie jest interesujace

Kwestia gustu, mnie fascynują te problemy, zwłaszcza, że mają istotne związki z hipotezą Collatza. Chaos deterministyczny, Wolfram rules, automaty komórkowe - dla mnie to wszystko ciekawe rzeczy.

Post by fir
a jesli chcesz odpowiedz to raczej staraj sie zadac pytanie w jakis zachecajacy sposob (bez glupot i dziur logicznych oraz w miare krotki i nie mulace - bo ludzie sa leniwi, zwlaszcza na starosc ;c)

Nie wiem jaki to jest zachęcający sposób, ale wnioskuję, że po prosty zwięzły i konkretny, to masz pewnie na myśli.

Post by fir
jak oszacowac czas obliczen napisalem
takie proste obliczenie jak dodawanie, mnozenie, i dzilenie przez dwa dla liczb calkowitych mozesz optymistycznie zalozyc zajmuja minimum jeden cykl procesora na dzialanie, ale oprocz arytmetyki moga byc tez tam movy (nalezaloby to napisac przy pomoy komend w asemblerze by to sobie zwizualizowac), dlatego jabym to pomnozyl przez 2 lub 3, do tego jesli mowa o ifie to ten juz sie robi duzo drozszy (powiedzmy z 15-20 cykli)

Ok, rozumiem.

Post by fir
takie cos

Post by o***@gmail.com
f(x) = a/2*x + b/2 - gdy x jest nieparzyste
f(x) = x2 - gdy x jest parzyste

(w zaleznosci od tego czym to naprawde jest, np czy to dzielenie przed dwa ma obcinac bit..oraz czy przypadkiem nie da sie jakos usunac tego if) mozna zgrubnie oszacowac na okolo 10 nanosekund (20-30 cykli) na iteracje (mowiac srednio optymistycznie) (jesli mowimy o 64 bitowych intach, dla 128 bit bedzie chyab ze 2-3 razy wolniej)

Ok, daje mi to jakieś ogólne pojęcie.

Post by fir
napisz kod w c i sprawdz czy dziala (tj czy daje wogole poprawne wyniki - podejrzewam ze zanim go napiszesz to przejdziesz przez 15 wersji w ktorych bedzie dawal nipoprawne ;c i jak juz bedziesz to miec to nie ma problemu ze zmierzeniem tego - ale jesli chesz zgrubne oszacowanie to z ogory ci mowie takie rzeczy zajmuja w okolicach kilkudziesieciu cykli na iteracje (w zaleznosci od szczegolow)czyli w granicach 5,10,20, 30 nanosekund na iteracje (w zaleznosci od szczegolow)

Rozumiem. Czyli wszystko w sumie rozbija się w tym przypadku o napisanie konkretnego programu od A do Z i sprawdzenie tego. Dodam tylko, że nie umiem programować, zapomniałem swój kurs programowania z podstaw w C ze studiów, nie pamiętam jak uruchomić program, w czym to się kompilowało itd. Dlatego pytam Was i nie sprawdzę sobie tego sam, dopóki nie zrobię solidnej powtórki. Poza tym chciałem mieć tylko ogólne pojęcie nt. tego, czy realne jest zbliżenie się przy parametrze n=100 do czasów 0,5 mikrosekundy. Wydaje się to być możliwe, ale tak na 100% nie wiadomo.

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

wpieniajace jet tez to ze kolega sugeruje jakoby to bylo wazne pytanie a jest glupkowate i przez to traci czas ludziom

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

[osobliwy nick]

Post by fir
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ć:

1000000/166*128/20*1/2^20= 0.037 MB/s

To mizernie, ale jeszcze pewnie gdzieś na pograniczu praktycznych zastosowań.

Post by fir
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ć.

Post by fir
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ć.

[fir]

Post by osobliwy nick

Post by fir
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.
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).

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

Post by osobliwy nick
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

Post by osobliwy nick
To mizernie, ale jeszcze pewnie gdzieś na pograniczu praktycznych zastosowań.

Post by fir
wpieniajace jet tez to ze kolega sugeruje jakoby to bylo wazne pytanie a jest glupkowate i przez to traci czas ludziom

https://patents.google.com/patent/US20130108038A1/en
https://arxiv.org/pdf/1801.05079.pdf
https://link.springer.com/article/10.1007/s41870-019-00307-9
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ć.

Post by fir
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ć.

[fir]

Post by fir

Post by osobliwy nick

Post by fir
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.
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).

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

Post by osobliwy nick
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

Post by osobliwy nick
To mizernie, ale jeszcze pewnie gdzieś na pograniczu praktycznych zastosowań.

Post by fir
wpieniajace jet tez to ze kolega sugeruje jakoby to bylo wazne pytanie a jest glupkowate i przez to traci czas ludziom

https://patents.google.com/patent/US20130108038A1/en
https://arxiv.org/pdf/1801.05079.pdf
https://link.springer.com/article/10.1007/s41870-019-00307-9
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ć.

Post by fir
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

[osobliwy nick]

Post by fir
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:

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.

Post by fir

Post by osobliwy nick
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.

Post by fir
(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?

Post by fir
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-faster-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.

[Piotr Chamera]

Post by osobliwy nick
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 :).

[osobliwy nick]

Post by Piotr Chamera

Post by osobliwy nick
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.

[fir]

Post by osobliwy nick

Post by fir
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

http://youtu.be/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.
"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.

Post by fir

Post by osobliwy nick
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)

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.

Post by fir
(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?

Post by fir
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

https://crypto.stackexchange.com/questions/52958/is-there-an-encryption-algorithm-which-is-a-magnitude-faster-than-aes-with-wea
"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

Post by osobliwy nick
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.pdf

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

[osobliwy nick]

Post by fir
tlumaczyl;em ci jak to sie szacuje byc zrozumial i nie bil piany na grupie

Nie biję piany :)

Post by fir
znasz chyba jakies elementarne podstawy asemblera?

Nie.

Post by fir
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.

Post by fir
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.

Post by fir
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 :)

[fir]

Post by osobliwy nick

Post by fir
tlumaczyl;em ci jak to sie szacuje byc zrozumial i nie bil piany na grupie

Nie biję piany :)

Post by fir
znasz chyba jakies elementarne podstawy asemblera?

Nie.

Post by fir
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.

Post by fir
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.

Post by fir
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

[fir]

Post by o***@gmail.com

Post by fir
dla mnie to wogole nie jest interesujace

Kwestia gustu, mnie fascynują te problemy, zwłaszcza, że mają istotne związki z hipotezą Collatza. Chaos deterministyczny, Wolfram rules, automaty komórkowe - dla mnie to wszystko ciekawe rzeczy.

nie watpie ;c problem w tym ze jak sie szuka odpowiedzi trzeba znalezc kogos koho to interesuje lub zainteresuje a z tym w praktyce bywa ciezko ;< (co znam z zycia gdzie wiekszosc ciekawych tematow trzeba robic zupelnie samemu a na forum mozn apogadav glownie o pewnym waskim wycinku tematow o ktorych akurat komus chce sie gadac)

[Radoslaw Szwed]

....

Post by o***@gmail.com
Czy ktoś jest w stanie wykonać takie obliczenia i zmierzyć czas? A może możecie podsunąć jakiś sensowny sposób oszacowania tego?

Program do testowania wersja 32bit. Wersja 64bit powinna działać szybciej niestety
byłem w podróży i miałem dostęp tylko do laptopa z systemem 32bit.
Zrobiłem testy dla 16,32,64,128 powtórzeń.

Czas obliczeń uzyskany przy pomocy rozkazu RDTSC
Pierwsza liczba do ilość powtórzeń druga średnia ilość cykli zegara

Procesor i5-4200 2,5GHz
16 - 14000
32 - 15900
64 - 19500
128 - 26500

Porcesor i7-6700 3.4GHz
16 - 9800
32 - 12500
64 - 15900
128 - 24000

Porcesor i7-8750 2.2GHz
16 - 7500
32 -10000
64 - 11000
128 - 14000

[osobliwy nick]

Post by Radoslaw Szwed
Program do testowania wersja 32bit. Wersja 64bit powinna działać szybciej niestety
byłem w podróży i miałem dostęp tylko do laptopa z systemem 32bit.
Zrobiłem testy dla 16,32,64,128 powtórzeń.
Czas obliczeń uzyskany przy pomocy rozkazu RDTSC
Pierwsza liczba do ilość powtórzeń druga średnia ilość cykli zegara
Procesor i5-4200 2,5GHz
16 - 14000
32 - 15900
64 - 19500
128 - 26500
Porcesor i7-6700 3.4GHz
16 - 9800
32 - 12500
64 - 15900
128 - 24000
Porcesor i7-8750 2.2GHz
16 - 7500
32 -10000
64 - 11000
128 - 14000

Ok, dzięki! To niesie ważną informację, że nie warto zmniejszać liczby operacji, bowiem oszczędności na prędkości są bardzo niewielkie w porównaniu do utraty bezpieczeństwa. Szyfrowanie w blokach 16-bitowych nie może się nawet równać z szyfrowaniem w blokach 128-bitowych. Jeśli dobrze rozumiem w ostatnim przypadku 128 iteracji zostało wykonanych w czasie 14000/(2,2*1000000000) sekund. A to jest 2.2*1000000000/14000*128/20*1/2^20 = 0,96 MB na sekundę w moim algorytmie. Są to już praktyczne i użyteczne wartości dla większości zastosowań szyfrów symetrycznych. Czyli warto pracować nad tym algorytmem! Fakt, aby dogonić AES'a trzeba szyfrować 10-100 razy szybciej, choć te szacunki rozjeżdżają się mocno.

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.

[osobliwy nick]

Dodam jeszcze tylko, że najprawdopodobniej szyfrowanie mogłoby się odbywać również w blokach 64-bitowych lub nawet 32-bitowych. A zatem podobne obliczenia wystarczy oszacować dla 64 iteracji, zaczynając od liczby 2^64-5 albo dla 32 iteracji zaczynając od liczby 2^32-5.

Przyjąłem bloki 128-bitowe, ponieważ są one współcześnie standardem. Według mojej wiedzy nie są one jednak koniecznością i większość symetrycznych szyfrów blokowych używa tak dużych bloków z konieczności, bowiem mają one ścisły związek z rozmiarem ich kluczy. Klucze zaś muszą być współcześnie duże, minimum 128-bitowe, aby zapewniały bezpieczeństwo. W moim algorytmie jednak można zastosować nawet klucz 256-bitowy, zaś szyfrowanie może odbywać się w praktycznie dowolnie małych blokach.

Nie mogą być one jednak za małe. Dla bloków 128-bitowych wszystkie możliwe wektory binarne o 128 cyfrach można ułożyć na 128! sposobów, czyli 3,86*10^215. Zaś dla przypadku bloków 64-bitowych można to zrobić na 64!=1,27*10^89. To wciąż znacznie więcej możliwych sposobów, niż liczba możliwych 128-bitowych kluczy. To również nieosiągalne do odtworzenia ilości dla kogoś kto podsłuchiwałby transmisje (w celu odtworzenia permutacji, którą realizuje algorytm), czy w ogóle kogoś, kto chciałby pomieścić tak ogromne permutacje na dysku. Wydaje się zatem, że bez utraty bezpieczeństwa można szyfrować również w krótszych blokach (choć muszę jeszcze zgłębić ten temat).

A to by oznaczało, że mój algorytm mógłby być najszybszym algorytmem na świecie, bo prawdopodobnie obliczenia dla przypadku n=64 będą o rząd lub kilka rzędów wielkości szybsze.

[osobliwy nick]

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.

[fir]

Post by osobliwy nick
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)

[osobliwy nick]

Post by fir

Post by osobliwy nick
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?

Post by fir
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.

[fir]

Post by osobliwy nick

Post by fir

Post by osobliwy nick
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...

https://github.com/boppreh/aes/blob/master/aes.py
#!/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)]
s=0
s+=2**(nmbrbits-i-1)*((x>>i)%2)
return s
return ((x * a + b)/2,1)
return (x/c,0)
return f
f=genf(a,b,c)
o=0
(s,ct)=f(s)
o+=ct*2**i
return swapendian(o,n)
ct = pt
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)
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?

Post by fir
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)

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.

NIE WIEM ILE CI TO ZAJMIE ALE CO TY JESTES ZA DZIWAKIEM BY SNUC TAKIE ROZWAZANIA

[fir]

Post by fir

Post by osobliwy nick

Post by fir

Post by osobliwy nick
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...

https://github.com/boppreh/aes/blob/master/aes.py
#!/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)]
s=0
s+=2**(nmbrbits-i-1)*((x>>i)%2)
return s
return ((x * a + b)/2,1)
return (x/c,0)
return f
f=genf(a,b,c)
o=0
(s,ct)=f(s)
o+=ct*2**i
return swapendian(o,n)
ct = pt
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)
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?

Post by fir
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)

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.

NIE WIEM ILE CI TO ZAJMIE ALE CO TY JESTES ZA DZIWAKIEM BY SNUC TAKIE ROZWAZANIA

ile badz ci nie zajmie jak napiszesz dobrze )prawdopodobnie po kilku latach uczenia sie programowania) to zajmie ci tyle co innnym a jak napiszesz zle to zajmie ci duzo wiecej - ot i cala tajemnica

oczywiscie pewnie mozna wymyslec cos jako tako oryginalnego wtym temacie ale najpierw raczej trzeba go opanowac co niestety moze zajac (wliczajc nauke kodowania) pare lat


co do instalacji pythona to rozpakowujesz go
do jakiegoc folderu typu c:\PYTHON35 i juz

pozniej piszesz kod w pliku costam.py
a ja odpalam to batem o takieh tresci

set PATH=c:\Python34;c:\Python34\Lib;C:\Python34\DLLs;

python.exe costam.py


takie ustawianie sciezki w baie dziala w obrebie bata ale tow ystarczy i nie robui syfu w sciezkach (nie jestem pewien czy wszystkie te 3 sciezki sa nawet potrzebne)