Działanie programu daje zły wynik.

Witam. Chciałem napisać program w C#, doszedłem już do momentu, w którym program musi wykonać obliczenie a = b ^ c % d (^ - potęgowanie). Oto kawałek kodu wykonywalnego:

ciagZaszyfrowany[i] = ((byte)ciagNiezaszyfrowany[i]) ^ e % n;

Usilnie próbuję wykonać obliczenie 48 ^ 97 % 187, jednak program zwraca wynik 81, a kalkulator windosowski 82, a prawidłowym wynikiem jest 82. Ponadto, przy próbie wyliczenia 49 ^ 97 % 187 wynikiem prawidłowym jest 168, a program zwraca 80... ciagZaszyfrowany to tablica int, jednak nie pomogło zamienić ten typ choćby na long :/. Bardzo proszę o pomoc i pozdrawiam.

zmieniłem indeks górny na potęgowanie (dałem ^ w plain ) - msm

Przepraszam za multipost, jednak działania te w potędze nie mają działania modulo tylko samą liczbę 97 :).

Nawias powinien pomóc.

Ja proponuję przestać potęgować przy użyciu operatora XOR: http://msdn.microsoft.com/en-us/library/zkacc7k1%28v=vs.80%29.aspx a zacząć np. metodą Math.Pow.

Tak właśnie :P. Stare przyzwyczajenia, rzadko co używam potęgowania w programowaniu ;). Dzięki za pomoc.

Tylko to działanie, które chcesz wykonać niekoniecznie się uda na longach...

Myślę że to jest to czego potrzebujesz:

http://www.algorytm.org/algorytmy-arytmetyczne/szybkie-potegowanie-modularne.html

Bardzo szybki algorytm służący właśnie do obliczania wyrażeń postaci (a ^ b) % c - w skrócie, opiera się na algorytmie szybkiego potęgowania, w którym cały czas przechowujesz jedynie resztę z dzielenia wyniku poprzedniego kroku przez c.

Kopiując pseudokod z linkowanej strony:

bits = rozloz_na_postac_binarna(b);
m = liczba_bitow(bits);
a = a mod n;
result = 1;
x = a;
for i=0 to m do
  begin
    if bits[i] = 1 then
      begin
        result = result * x;
        result = result mod n;
      end
    x = x * x;
    x = x mod n;
  end;

Wydaje mi się, że do obliczenia pow(x, y) mod z jest już gotowa metoda w .NET: http://msdn.microsoft.com/en-us/library/system.numerics.biginteger.modpow%28v=vs.100%29.aspx

Powiedzcie mi jeszcze (tak poza tematem :)) - gdy wyliczam odwrotność modulo, a wychodzi mi liczba ujemna to mam zwrócić wartość bezwzględną?

Jako że napisałeś na PW, odpowiem tutaj.

Nie zwracaj wartości bezwzględnej na pewno...
Odwrotność modulo powinna być liczbą dodatnią, jeśli u Ciebie jest inaczej to masz albo zły algorytm albo przepełnienie inta (INT_MAX + 1 = INT_MIN).

To chyba ja Ci zaproponowałem algorytm z wikipedii, pokaż może jak wyliczasz tą odwrotność to coś spróbuję poprawić :]