[C, C#, Pascal, ...] PowerMod()

0

Hej, potrzebuje implementacji funkcji PowerMod(a, n, m), najlepiej w C#, ale jak bedzie w jakims innym jezyku to niepogardze nia i sobie przerobie :D
Szukalem po necie, ale wiekszosc nie dziala jak jest duze n :/

Jesli dam

PowerMod(8192, 1305401749868677, 1697022274829280)

To powinno podac 2, a podaje jakies bzdury
Jesli zrobilem swoja (baaardzo prymitywna) funkcje to zadzialalo, ale, bez przesady nie bede jej uzywal bo wykonuje dosc duzo petli i jest wola.
Zna ktos szybki i skuteczny sposob jej implementacji??

0

Moze dla niewtajemniczonych podasz co ta funkcja ma robic? Podaj tez na jak duzych liczbach ma dzialac.

0
foflik napisał(a)

Moze dla niewtajemniczonych podasz co ta funkcja ma robic?

PowerMod(a, b, m) = a^b mod m
foflik napisał(a)

Podaj tez na jak duzych liczbach ma dzialac.
Wystarczy Int64, tak zeby przyklad ktory podalem sie nie wywalal ;P

0

powinieneś poszukać coś na ten temat w matematyce dyskretnej, która zajmuje się między innymi takimi rzeczami
np. jeśli chodzi o modulo to dotyczy go np. chińskie twierdzenie o resztach

mój pomysł jest taki, że dla modulo obowiązuje zasada:
ij (mod m)=((i mod m)(j mod m)) mod m

zmienna i to nasza podstawa, możemy więc zauważyć, że np dla i^2(mod b)=(i mod b)*(i mod b) mod b...i dla wyższych potęg też jest to słuszne...
można więc zrobić jakąś iterację, która będzie wyliczać resztę dla jakiejś części wykładnika, potem podnosić to do jakiejś potęgi i tak w kółko, złożoność po każdej pętli będzie maleć wykładniczo...
np (1525)mod 33=((155)mod 33)^2 mod 33 a to już znacznie przyspiesza obliczenia. Pozostaje tylko kwestia jak sobie rozbijez wykładnik na kawałki...

0
mwach20 napisał(a)

Pozostaje tylko kwestia jak sobie rozbijez wykładnik na kawałki...
No tylko wlasnie w tym problem ze faktoryzacja jest dosc dluga (jesli chodzi o czas wykonywania). :-/
A jak wiadomo dla duzych liczb troszke dlugo to bedzie trawalo, a jesli w szczegolnosci trafi sie liczba pierwsza, ktora mamy podniesc do potegi, to ten algorytm troszke traci sens :(

0
  1. To nie jest "potęga modulo", tylko potęgowanie modulo: Modular Exponentiation -> modexp :-P
  2. Masz to w każdej bibliotece kryptograficznej...
  3. NTF -> C#
0
marcinEc napisał(a)
  1. To nie jest "potęga modulo", tylko potęgowanie modulo: Modular Exponentiation -> modexp :-P
    a kto mowi ze "potega"?? PowerMod() taka funkcja jest w wielu programach matematycznych ktore zajmuja sie roznymi skomplikowanymi obliczeniami :P
marcinEc napisał(a)
  1. Masz to w każdej bibliotece kryptograficznej...

Ale ja potrzebuje KOD zrodlowy. Tak to bez problemu bym podczepil jakas dll'ke albo nawet prosciej wykozystal funkcje kryptograficzne wbudowane w .NET'a :]

marcinEc napisał(a)
  1. NTF -> C#
    To jeszcze rozwin skrot NTF zebym wiedzial gdzie tego szukac ;)
0

Ech, po toś dostał modexp() żebyś sobie poszukał algorytmu, a jak nie to se używaj powermod w programach matematycznych.
Słyszałeś o kodzie źródłowym biblioteki??

0
aaa napisał(a)

Słyszałeś o kodzie źródłowym biblioteki??
hmmm, chyba nie... a co to takiego?? Jakas hinduska potrawa?? ;P

Myslisz ze nie szukalem w necie??
A zanim zaczniesz sie wkurzac i mnie osmieszac, wez sobie jeden z Twoich modexp'ow, podstaw do nich Int64 takie jakie podalem w przykladzie i zobacz czy zwroci 2.
Kod zrodlowy funkcji mam!! Ale dziala TYLKO na malych liczbach. Nie mowcie ze mobsluge duzych musze sobie sam zaimplementowac, bo UInt64 (ani mnozenie dwóch liczb po 40.000) nie jest duzym wynikiem i kompilator sobie powinien poradzic.

0

Naprawdę jesteś takim ignorantem??

desperat napisał(a)

(...)
bo UInt64 (ani mnozenie dwóch liczb po 40.000) nie jest duzym wynikiem i kompilator sobie powinien poradzic.

Akurat z mnożeniem sobie doskonale radzi, tylko widzisz: masz ograniczony zakres liczb w rejestrach procesora.

Co do potęgowania: przy tak ogromnym m=1697022274829280, już w trzecim kroku algorytmu XXX - przed wykonaniem operacji modulo - masz 31 cyfrowy wynik! Jak to chcesz w int64 umieścić?? To nawet w long double się nie mieści dokładnie.

8192 x^2:67108864 67108864 67108864
67108864 x^2:4503599627370496 1109555077711936
1109555077711936 x^2:1231112470476340300000000000000 [błąd zabrakło precyzji na long double "1231112470476340336104996868096"]

Nie mnożyłeś chyba 1 305 401 749 868 677 razy liczby 8192?! :-P

1 użytkowników online, w tym zalogowanych: 0, gości: 1