Path: csiph.com!aioe.org!.POSTED.MOzQkSx0KhOHYjsyuRHqSg.user.gioia.aioe.org!not-for-mail From: "Radoslaw Szwed" Newsgroups: pl.comp.programming Subject: =?UTF-8?Q?Re:_Ile_zajmie_komputerowi_mno=C5=BCe?= =?UTF-8?Q?nie_liczb_rz=C4=99du_2^128?= Date: Wed, 4 Dec 2019 10:41:08 +0100 Organization: Aioe.org NNTP Server Lines: 20 Message-ID: References: NNTP-Posting-Host: MOzQkSx0KhOHYjsyuRHqSg.user.gioia.aioe.org Mime-Version: 1.0 Content-Type: text/plain; format=flowed; charset="UTF-8"; reply-type=original Content-Transfer-Encoding: 8bit X-Complaints-To: abuse@aioe.org X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.5512 X-MSMail-Priority: Normal X-Priority: 3 X-Notice: Filtered by postfilter v. 0.9.2 X-Newsreader: Microsoft Outlook Express 6.00.2900.5512 Xref: csiph.com pl.comp.programming:33527 Użytkownik napisał w wiadomości news:b7426ee8-be56-48fc-9657-da5a18e0729b@googlegroups.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 ...