Article View: pl.comp.programming
Article #216562Ile zajmie komputerowi mnożenie liczb rzędu 2^128
From: osobliwy.nick
Date: Tue, 03 Dec 2019 23:19
Date: Tue, 03 Dec 2019 23:19
7 lines
2562 bytes
2562 bytes
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?
Technical Details
Message-ID:
<b7426ee8-be56-48fc-9657-da5a18e0729b@googlegroups.com>Path:
mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed.pionier.net.pl!3.eu.feeder.erje.net!feeder.erje.net!newsfeed.xs4all.nl!newsfeed8.news.xs4all.nl!185.151.15.255.MISMATCH!tr1.eu1.usenetexpress.com!feeder.usenetexpress.com!tr2.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!g89no2748681qtd.0!news-out.google.com!o19ni95qtr.1!nntp.google.com!g89no2748670qtd.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mailShow Full Headers
Complete Article Headers
X-Received: by 2002:a37:6e86:: with SMTP id j128mr8332471qkc.265.1575415199460; Tue, 03 Dec 2019 15:19:59 -0800 (PST) X-Received: by 2002:a37:d8a:: with SMTP id 132mr7310655qkn.324.1575415199268; Tue, 03 Dec 2019 15:19:59 -0800 (PST) Path: mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed.pionier.net.pl!3.eu.feeder.erje.net!feeder.erje.net!newsfeed.xs4all.nl!newsfeed8.news.xs4all.nl!185.151.15.255.MISMATCH!tr1.eu1.usenetexpress.com!feeder.usenetexpress.com!tr2.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!g89no2748681qtd.0!news-out.google.com!o19ni95qtr.1!nntp.google.com!g89no2748670qtd.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: pl.comp.programming Date: Tue, 3 Dec 2019 15:19:58 -0800 (PST) Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=185.186.156.102; posting-account=5sNFBgoAAAAxlae8lv99mPyGsDs6ynwB NNTP-Posting-Host: 185.186.156.102 User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: <b7426ee8-be56-48fc-9657-da5a18e0729b@googlegroups.com> Subject: Ile zajmie komputerowi mnożenie liczb rzędu 2^128 From: osobliwy.nick@gmail.com Injection-Date: Tue, 03 Dec 2019 23:19:59 +0000 Lines: 23 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit