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

Article View: pl.comp.programming

Article #216563

Back to pl.comp.programming Previous Next

#216563

From: Radoslaw Szwed
Date: Wed, 04 Dec 2019 09:41

15 lines
2043 bytes

Użytkownik <osobliwy.nick@gmail.com> 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 ...

Technical Details

Message-ID: <qs7uv5$col$1@gioia.aioe.org>

Path:

mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed.pionier.net.pl!news-2.dfn.de!news.dfn.de!news.uni-stuttgart.de!news.unit0.net!news.mixmin.net!aioe.org!.POSTED.MOzQkSx0KhOHYjsyuRHqSg.user.gioia.aioe.org!not-for-mail

References: <b7426ee8-be56-48fc-9657-da5a18e0729b@googlegroups.com>

Show Full Headers

Complete Article Headers

Path: mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed.pionier.net.pl!news-2.dfn.de!news.dfn.de!news.uni-stuttgart.de!news.unit0.net!news.mixmin.net!aioe.org!.POSTED.MOzQkSx0KhOHYjsyuRHqSg.user.gioia.aioe.org!not-for-mail
From: "Radoslaw Szwed" <radekszwed@pochta.fm>
Newsgroups: pl.comp.programming
Subject: Re: Ile zajmie komputerowi mnożenie liczb
 rzędu 2^128
Date: Wed, 4 Dec 2019 10:41:08 +0100
Organization: Aioe.org NNTP Server
Lines: 20
Message-ID: <qs7uv5$col$1@gioia.aioe.org>
References: <b7426ee8-be56-48fc-9657-da5a18e0729b@googlegroups.com>
NNTP-Posting-Host: MOzQkSx0KhOHYjsyuRHqSg.user.gioia.aioe.org
Mime-Version: 1.0
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
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

Reply to Parent Message