Problem mit einem Förmelchen

MrFox

Vorsicht es folgt vermutlich ein Anfängerproblem!!!

Ich versuche gerade folgende Formel in C++ umzusetzen (ich benutze den C++Builder von Borland, der 1997 erschienen ist):

M = (C hoch d) modulo N

Da es sich um sehr große Zahlen dreht benutze ich den Datentyp long double

Wenn ich die Werte C = 11, d = 23 und N = 187 einsetze, weiß ich, dass M den Wert 88 hat.

Der Computer spuckt nach eingabe folgender Zeilen allerdings M = 168 aus:

long double C,d,N,M;
C=11;
d = 23;
N = 187;
M = fmodl(powl(C,d),N);

Noch erschreckender ist, dass wenn ich den Datentyp auf double abändere und bei den Funktionen das l wegenehme, ich als Ergebnis M = 149 bekomme.

ICH WILL ABER M=88

Hiiiiiiiiiiiiiillllllllllllllllffffffffffffeeeeeeeeeeeeeeeee

Vielen dank schonmal im voraus

MrFox

TGGC

Rundungsfehler.

Bye, TGGC \-/

volkard

inline u32 mulMod(u32 a,u32 b,u32 m){
	return u64(a)*b%m;
}
inline u32 powMod(u32 a,u32 b,u32 m){
	u32 x=1;
	while(b!=0){
		while((b%2)==0){
			b/=2;
			a=mulMod(a,a,m);
		}
		--b;
		x=mulMod(x,a,m);
	}
	return x;
}

borg

MrFox schrieb:

Da es sich um sehr große Zahlen dreht benutze ich den Datentyp long double

Wenn ich die Werte C = 11, d = 23 und N = 187 einsetze, weiß ich, dass M den Wert 88 hat.

nein, es dreht sich nicht um große zahlen. du musst das 11^23 gar nicht berechnen.

#include <iostream>

int xHochMod( int value, int exp, int mod )
{
    int result = (exp % 2) ? (value % mod) : 1;
    while( exp /= 2 )
    {
        value = (value * value) % mod;
        if( exp % 2 )
            result = (result * value) % mod;
    }
    return result % mod;
}

int main( )
{
    std::cout << xHochMod( 11, 23, 187 );
}

edit: ohgott, bin viel zu spät. hab volkards post gar nicht gesehen

volkard

man kann es nicht oft genug sagen.