• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

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

Object Storage Arubacloud
0 głosów
468 wizyt
pytanie zadane 2 grudnia 2019 w C i C++ przez osobliwy nick Użytkownik (900 p.)
Weźmy liczbę 2^128-1 i pomnóżmy ją razy 1,5 oraz dodajmy 0,5. Powtórzmy operację 128 razy. Ile zajmie komputerowi obliczenie końcowej liczby? Zaznaczę tylko, że nie chodzi mi o matematyczne rozwiązanie, bo wiem, że będzie to 3^128-1. Chcę wiedzieć ile zajmują operacje na tak dużych liczbach i czy są to jakieś rozsądne czasy.

1 odpowiedź

0 głosów
odpowiedź 2 grudnia 2019 przez RafalS VIP (122,820 p.)
edycja 2 grudnia 2019 przez RafalS
In [2]: %%timeit 
   ...: x = 2 **128 - 1 
   ...: for _ in range(128): 
   ...:     x = x * 1.5 + 0.5 
   ...:                                                                         

5.88 µs ± 180 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

C++ radzi sobie jeszcze lepiej:

#include <iostream>
#include <chrono>
#include <cmath>

int main()
{
    using namespace std::chrono;
    steady_clock::time_point begin = steady_clock::now();
    double x = pow(2., 128) - 1;
    for (size_t i = 0; i < 128; i++)
    {
        x = x * 1.5 + 0.5;
    }
    steady_clock::time_point end = steady_clock::now();
    std::cout << duration_cast<nanoseconds>(end - begin).count() << "[ns]" << std::endl;
}
// 601[ns]

 

 

komentarz 2 lutego 2020 przez osobliwy nick Użytkownik (900 p.)
edycja 2 lutego 2020 przez osobliwy nick

Mam pytanie co do działania na liczbach. Jakie jest błąd bezwzględny?

Nie wiem, trzeba to sprawdzić. Mam jednak teoretycznie ustalony najgorszy przypadek, najlepszy przypadek oraz średni przypadek (który podałem).

Ogólnie najgorszy przypadek wymagałby obliczenia ok. 100 iteracji dla liczby 2^100*5/3-5/3 = 2112751000380382335827838675625. Liczbę tę musimy mnożyć razy 2.5 i dodawać 2.5. I tak 100 razy:

1. 2112751000380382335827838675625*2.5+2.5 = 5281877500950955839569596689065

2. 5281877500950955839569596689065*2.5+2.5 = 13204693752377389598923991722665

I tak dalej (wszystkie liczby po drodze będą całkowite). Nie wiem ile to czasu zajmie. Zaś najlepszy przypadek to podzielenie liczby 2^100 przez 2 również 100 razy, ale krok po kroku. Docelowo algorytm nie ma faktoryzować liczb (i nie wie, że można podzielić od razu kilka razy przez 2), sprawdza tylko parzystość liczby po każdej operacji. Jeśli liczba jest parzysta to dzieli, jeśli nieparzysta to mnoży, z dodawaniem. Średni przypadek, to liczba 2^100-5 i wykonywanie naprzemiennie operacji x*2,5+2,5 oraz x/2, 100 razy pod rząd.

Szybkość mimo wszystko jest zależna od jednostki na której testujesz.

Wiem, trzeba to też uwzględnić.

Wracając do dowodu. Mimo, że Twój tok może być poprawny, to jest mała szansa by grono matematyczne przyjęło Cię z otwartymi ramionami. Możliwe rozwiązania Hipotezy Riemanna przez osoby z poza środowiska nie są chętnie rozpatrywane, w Twoim przypadku może być podobnie. 

Zdaję sobie z tego sprawę, jakkolwiek docelowo chcę tym zainteresować raczej biznes niż środowisko naukowe (choć publikacja naukowa jest niezbędna, o czym za chwilę). Kogoś kto ewentualnie pomógłby mi sfinansować adaptację algorytmu, wszelkie niezbędne testy, konsultację naukową (bez proszenia nikogo, tylko opłacenie takiej usługi u odpowiednich ludzi) no i ewentualnie dążenie do patentu, jeśli wszystko będzie wyglądać obiecująco. Później lub gdzieś po drodze należy oczywiście algorytm opublikować, w formie publikacji naukowej i musi zostać on poddany ocenie przez środowisko naukowe, a nie przez jednego naukowca, czy jeden tylko zespół (jak bardzo fachowy by on nie był). Taka weryfikacja, debata, może trwać nawet wiele lat. Dopiero wówczas algorytm można uznać wstępnie za bezpieczny, jeśli nikt nie znajdzie w nim dziur. Ale szeroka adopcja takich nowości w tak newralgicznym temacie jak np. bezpieczeństwo kont bankowych, czy korespondencji na wysokim szczeblu to też nie jest sielanka. Dlatego znów - nie widzę swoich szans w pojedynkę w takim biznesie, bez ludzi i kapitału, który byłby w stanie cierpliwie czekać na zyski (spodziewanie, nie gwarantowane).

Trzeba też zdawać sobie sprawę, że mój pomysł nie jest porównywalny z rozwiązaniem hipotezy Riemanna, nie implikuje ani wielkiej rewolucji w matematyce, ani nie jest wielkiego rodzaju odkryciem matematycznym. Raczej w odpowiedni, sprytny sposób wykorzystuje obecnie znaną wiedzę (w dosyć niszowej dziedzinie matematyki, jak dotychczas czysto teoretycznej), dodając pewną dozę innowacji od siebie, czyniąc ją praktyczną w zakresie właśnie kryptografii. W temacie, w którym już kilku autorów w ciągu ostatnich lat dostrzegło potencjał kryptograficzny i pisało o tym. Powstał przynajmniej jeden prosty algorytm szyfrujący obrazy w oparciu o ciąg Collatza, a także funkcja hashująca (wcześniej bardzo podobną funkcję próbowało nawet już opatentować Apple, ale odrzucono ich wiosek).

Bez przedstawienia dowodów, to tylko puste słowa. Przedstaw dowód matematyczne popierający Twoją hipotezę. 

Nie stawiam żadnej hipotezy. Dowód na co miałbym przedstawić? Algorytm można przetestować pod kątem czasu pracy, oraz czegoś co można nazwać pseudolosowością szyfrowania (są na to ścisłe kryteria, np. konfuzja i dyfuzja) i tyle. Fakt, przydałaby się ścisła wiedza na temat dystrybucji kluczy, o których pisałem, ale jak na razie ten temat też musi być tylko obiektem testów (możliwe, że ścisłych rozwiązań nie ma).

komentarz 2 lutego 2020 przez tkz Nałogowiec (42,000 p.)
Twoją hipotezą jest to, że to działa. Dowód maiłby przedstawić czy jest łatwo odwracalny. Dużo ogólników w Twoich wiadomościach, jak będzie coś bardzo konkretnego, to z chęcią poczytam.
komentarz 2 lutego 2020 przez mokrowski Mędrzec (156,220 p.)

@osobliwy nick, rozumiem że uzyskałeś odpowiedź na postawione w wątku pytanie? Ja od siebie dodam że zwykła biblioteka gmp https://gmplib.org/ , wykonuje obliczenia o które pytasz IMHO wystarczająco szybko.

Tu także bym zajrzał bo widzę w wątku "gdybania i przypuszczenia" https://uprp.gov.pl/pl

Co do finansowania, poszukaj tzw. Aniołów Biznesu: https://pl.wikipedia.org/wiki/Anio%C5%82_biznesu weź tylko prawnika do podpisania umów.

Jeśli Twój pomysł ma sens i potencjał biznesowy (co nie zawsze idzie ze sobą w parze), to znajdziesz inwestora.

komentarz 3 lutego 2020 przez osobliwy nick Użytkownik (900 p.)

Twoją hipotezą jest to, że to działa. Dowód maiłby przedstawić czy jest łatwo odwracalny. Dużo ogólników w Twoich wiadomościach, jak będzie coś bardzo konkretnego, to z chęcią poczytam.

Jeśli liczba kluczy wynosi 2^140, a każdy klucz zadaje unikalne szyfrowanie trzeba przeszukać wszystkie klucze, żeby zgadnąć, który został użyty. Jeśli sprawdzenie pojedynczego klucza zajmuje jakiś niepomijalny czas nie da się tego szybko sprawdzić. Nawet gdyby były to tylko nanosekundy obliczenia zajmą miliardy lat. Oczywiście istnieją rodzaje ataków na różne algorytmy, które pozwalają np. mając jakąś liczbę tekstów jawnych i szyfrogramów wyłuskać klucz. Zajmuje się tym kryptoanaliza różnica, liniowa, statystyczna. Są też rodzaje ataków dedykowanych na różne algorytmy, o ile dany algorytm ma akurat jakąś słabość. Jeśli algorytm nie ulegnie tego rodzaju atakom to można uznać, że jest bezpieczny (w przypadku mojego algorytmu będzie trzeba zrobić tego rodzaju testy, zaś najlepiej, aby był on przedmiotem właśnie szerokiej recenzji środowiska naukowego, po publikacji). Ale bardzo rzadko istnieje dowód na to, że nie ma żadnego rodzaju ataku, który dany algorytm mógłby złamać w jakiś sprytny sposób, który jak dotychczas nie jest znany nauce. Nie ma takich dowodów w przypadku większości algorytmów obecnie używanych, jak RSA, czy choćby wspomniany AES i nikt nie robi z tego wielkiego problemu. Oznacza, to, że może AES da się złamać w jakiś sprytny sposób jakimś sposobem, ale nikt jak na razie nie przedstawił takiego sposobu i wydaje się to bardzo mało prawdopodobne (zwłaszcza, że nie poddaje się żadnym znanym metodom ataku).

komentarz 3 lutego 2020 przez osobliwy nick Użytkownik (900 p.)
edycja 3 lutego 2020 przez osobliwy nick

@osobliwy nick, rozumiem że uzyskałeś odpowiedź na postawione w wątku pytanie?

Uzyskałem odpowiedź od RafalS, ale jego obliczenia traciły precyzję, więc nie można jej traktować jako zbyt dokładnej. Natomiast dokładniejsze wyliczenia, bez traconej precyzji dostałem na innym forum, a później policzył mi to też kolega. Więc odpowiedź na pytanie, które zadałem na początku jest już dla mnie całkiem jasna (choć wciąż dostaję sugestie, że w jakiś sposób, w jakimś języku, gdyby to zoptymalizować można to zrobić o rząd lub nawet dwa rzędy wielkości szybciej i to jest dla mnie jeszcze niejasne).

Tu także bym zajrzał bo widzę w wątku "gdybania i przypuszczenia" https://uprp.gov.pl/pl

 Polski urząd patentowy w ogóle mnie nie interesuje. W Polsce nie da się opatentować algorytmu, polskie prawo w ogóle nie chroni algorytmów. Jesteśmy zacofani w tej dziedzinie, jak zresztą ze wszystkim. Ja chcę to opatentować w USA. Taki patent tam, razem z pomocą odpowiedniej firmy, która zajmuje się właśnie pomocą w uzyskiwaniu patentów, dopinaniem formalności kosztuje ok. 60000$. Nie mam takich pieniędzy, stąd musiałbym zrobić to albo za pieniądze inwestora albo własnej firmy, która zresztą też potrzebowałaby finansowania, jak już pisałem. Argumentem przemawiającym za patentem w USA jest również fakt, iż wiele, a może większość firm zainteresowanych odkupieniem lub wykorzystaniem patentu prawdopodobnie również pochodziłaby z USA, w szczególności większość technologicznych gigantów podchodzi właśnie stamtąd. To jest ogromny rynek docelowy tej technologii, trzeba więc myśleć o patencie tam właśnie.

Przypomnę, że Apple próbowało już patentować funkcję hashującą stworzoną na podstawie funkcji, które są także podstawą działania mojego algorytmu:

https://patents.google.com/patent/US20130108038A1/en

Takie firmy prowadzą nieprzerwane prace w dziedzinie kryptografii, są zainteresowane nowymi technologiami w tej branży, mają pieniądze na patenty i jak widać są skłonne próbować swoich sił oraz wykładać pieniądze na innowacyjne patenty dokładnie w tej dziedzinie, z której wywodzi się mój algorytm. Myślę, że w Apple nikt nie zastanawia się za bardzo, czy patent przeszkodzi im we wdrożeniu oraz w adopcji danej technologii, czy nie, bo oni to po prostu patentują, wdrażają i sprzedają. W Polsce zaś trwają debaty, czy patentować, czy może lepiej nie albo, czy algorytm to powinna być własność intelektualna, chroniona prawnie, czy nie. W tym samym momencie zaś Apple zarabia na nas sprzedając nam smartfony, między innymi ze swoim własnym systemem szyfrującym, którego nie umiało złamać nawet FBI, w głośnej sprawie dotyczącej aresztowanego przez nich teorrorysty, posługującego się Apple.

Co do finansowania, poszukaj tzw. Aniołów Biznesu: https://pl.wikipedia.org/wiki/Anio%C5%82_biznesu weź tylko prawnika do podpisania umów.

Jeśli Twój pomysł ma sens i potencjał biznesowy (co nie zawsze idzie ze sobą w parze), to znajdziesz inwestora.

O czymś takim właśnie myślałem oraz o różnego rodzaju funduszach zalążkowych. Oczywiście, pod warunkiem, że algorytm ma sens. Tzn. o tym, że ma sens wiem na pewno. Otwarte pozostaje pytanie tylko o rozkład kluczy szyfrujących, odporność na znane ataki kryptoanalityczne oraz o konfuzję i dyfuzję, czyli na ile pseudolosowo algorytm podmienia i miesza bity. Część z tych parametrów to kwestia testów, po nich będzie można mieć już wstępną pewność, że algorytm jest coś wart. Wówczas można już myśleć o patencie, bez ryzyka i bujania w obłokach. Następnie zaś potrzebne jest upublicznienie algorytmu, najlepiej w formie publikacji naukowej i pogłębiona recenzja środowiska naukowego.

 

Podobne pytania

0 głosów
1 odpowiedź 2,618 wizyt
pytanie zadane 5 lutego 2017 w C i C++ przez partycja Nowicjusz (150 p.)
0 głosów
1 odpowiedź 328 wizyt
pytanie zadane 14 czerwca 2021 w Algorytmy przez Tanormalnie Użytkownik (550 p.)
0 głosów
1 odpowiedź 605 wizyt
pytanie zadane 1 listopada 2020 w Algorytmy przez niezalogowany

92,674 zapytań

141,575 odpowiedzi

320,045 komentarzy

62,038 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...