[C] Potęgowanie dużych liczb

[a2d2a2m]

Koledzy,
Potrzebuję napisać program w c, który będzie wykonywał działania na dużych liczbach. Utknąłem na potęgowaniu. Potrzebuję podnieść liczbę 576 bitową do potęgi 65537. Samo naapisanie programu nie jest problemem ale chodzi o czas wykonywania operacji przez komputer. Pierwszy pomysł, który mi przyszedł do głowy, to zapisanie w tablicy liczby w systemie dwójkowym i wykonywanie mnożeń, tak jak się robi ręcznie. Podniesienie liczby do potęgi drugiej zajmuje ok. 3 min. przez mój komputer ale za każdym razem trzeba mnożyć przez siebie coraz większe liczby. Chociaż, żeby obliczyć taką potęgę wystarczy wykonać 16 mnożeń, to ze względu na konieczność wykonywania działań, na coraz większych liczbach czas drasytcznie ulega wydłużeniu, co nie jest do przyjęcia.
Może ktoś zna jakiś sposób wykonania tego działania w sposób bardziej efektywny.
Nie wiem czy jasno się wyraziłem ale może ktoś coś podpowie.

[Althorion]

Skorzystaj z gotowej biblioteki do obsługi dużych liczb. jest chyba najlepsze.

[ksisquare]

Jakoś wierzyć mi się nie chce, że potrzebujesz dokładnego wyniku.
Ta liczba może mieć jakieś 11363676 cyfr.
Np \(\displaystyle{ \left({2^{576}}\right)^{65537}=1.689189111489297588500114779 \cdot10^{11363675}}\)
Co ma ? A gdyby tak w spinie zakodować zera i jedynki to czy wystarczyłoby wszechświata?

Kod: Zaznacz cały

http://www.interklasa.pl/portal/index/strony?mainSP=subjectpages&mainSRV=matematyka&methid=6600648&page=article&article_id=317521

Kurdę nie pamiętam kto proponował rachunki na "odwrocie koperty", Bentley?

A słyszałeś o tym, że liczba to prawie wielomian, a splot (mnożenie wielomianów) potrafimy robić dość sprawnie. Dzięki sinusom, cosinusom, liczbom zespolonym i innym takim Fourierom (Caratsuba, Toom, FFT - multiplication)
A dzięki pewny wzorkom np. "szybkie potęgowanie", albo jak tu dałeś konkretny wykładnik to poszukałbym "minimal adition chain", albo jakoś tak bo na angielskim byłem jakoś chyba przez tydzień.
Czeskiego, rosyjskiego i bułgarskiego uczyłem się podobnie, znaczy czytałem, czytałem do skutku.

[a2d2a2m]

Jakoś wierzyć mi się nie chce, że potrzebujesz dokładnego wyniku.
Ta liczba może mieć jakieś 11363676 cyfr.
Np \(\displaystyle{ \left({2^{576}}\right)^{65537}=1.689189111489297588500114779 \cdot10^{11363675}}\)
Co ma ? A gdyby tak w spinie zakodować zera i jedynki to czy wystarczyłoby wszechświata?

Kod: Zaznacz cały

http://www.interklasa.pl/portal/index/strony?mainSP=subjectpages&mainSRV=matematyka&methid=6600648&page=article&article_id=317521

Kurdę nie pamiętam kto proponował rachunki na "odwrocie koperty", Bentley?

A słyszałeś o tym, że liczba to prawie wielomian, a splot (mnożenie wielomianów) potrafimy robić dość sprawnie. Dzięki sinusom, cosinusom, liczbom zespolonym i innym takim Fourierom (Caratsuba, Toom, FFT - multiplication)
A dzięki pewny wzorkom np. "szybkie potęgowanie", albo jak tu dałeś konkretny wykładnik to poszukałbym "minimal adition chain", albo jakoś tak bo na angielskim byłem jakoś chyba przez tydzień.
Czeskiego, rosyjskiego i bułgarskiego uczyłem się podobnie, znaczy czytałem, czytałem do skutku.

Wynik potrzebuję bardzo dokładny, bo chodzi o szyfrowanie RSA. Program Mathematica takie obliczenia wykonuje w 2 min.. Tak więc jest jakiś sposób, żeby to obliczyć sprawnie. Podnoszenie najpierw do potęgi drugiej i potem otrzymany wynik ponownie do potęgi drugiej itd. całe liczenia można zrealizować w 16 krokach. Problem pojawia się przy mnożeniu coraz większych liczb. Zrobiłem to, jak robi się mnożenie pod kreską i niestety zbyt długo to trwa. Jak wspomniałem program mathematica to potrafi. Mam tylko problem, bo nie mogę wygenerować z tego programu kodu w C potrzeba chyba mathlink, może ktoś tutaj może mi pomóc. Program piszę w Dev c++.

[Magnum23]

Poczytaj o szybkim potęgowaniu \(\displaystyle{ a^b\ modulo\ n}\)

[a2d2a2m]

Poczytaj o szybkim potęgowaniu \(\displaystyle{ a^b\ modulo\ n}\)

Tylko ja potrzebuję tylko a^b, a nie a^b mod n. No chyba, że czegoś nie rozumię.

[royas]

A tego \(\displaystyle{ a^b}\) to nie potrzebujesz właśnie do tego, żeby potem zrobić z tego modulo?

[a2d2a2m]

A tego \(\displaystyle{ a^b}\) to nie potrzebujesz właśnie do tego, żeby potem zrobić z tego modulo?

To też ale potrzebuję głównie a^b. Z tym potęgowaniem modulo, to wiedziałem, że mnożę
liczby, potem modulo i mnożę resztę przez liczbę itd..

[Althorion]

Dlaczego więc nie skorzystasz z gotowej biblioteki do obsługi dużych liczb?

[Afish]

Zamiast trzymać liczbę w systemie dwójkowym lepiej użyj systemu \(\displaystyle{ 10^9}\) (lub większego, o ile typ danych Ci pozwoli). Ponadto spróbuj zredukować ten problem (czy też całkowicie pozbyć się potęgowania). Najlepiej podaj całą treść zadania, być może wystarczy algorytm potęgowania modularnego (jeżeli chodzi Ci tak naprawdę o resztę z dzielenia tej ogromnej liczby), jeżeli zaś potrzebujesz konkretnie wyniku potęgowania, to rozważ użycie gotowej biblioteczki - nie oszukujmy się - rozwiązanie pisane na szybko nie będzie działało szybciej.

[a2d2a2m]

Ok. Jaką bibliotekę do Dev c++ spełnającą moje potrzeby polecacię? Chodzi mi o sprawdzoną, żeby nie było problemów z jej instalacją.

[Althorion]

Skorzystaj z gotowej biblioteki do obsługi dużych liczb. jest chyba najlepsze.

[leff7]

Biblioteka GNU GMP i C++. Szybko i dokładnie dla operacji na liczbach całkowitoliczbowych. Liczby dowolnie duże ograniczone tylko zasobami komputera. Zoptymalizowana szybkość operacji na dużych liczbach. W przypadku obliczeń na zmiennoprzecinkowych biblioteka GNU MPFR. Znajomość C++ wystarczy w podstawowym zakresie. Kompilacja najlepiej w środowisku linux.