вычисление больших степеней по модулю - Rsa

[Студент]

Задача: реализовать вычисление (z^k)mod(n), где
0 <= z <= 255
k может быть порядка 10^5
n ~ 10^4

Проблема состоит в том, что при вычислении разрядная сетка не выдерживает возведения в большие степени. Решение было найдено в виде рекурсивной функции, попарно возводящей x в квадрат, и передающей вниз по стеку. Получилось вот что:

//Возвращает остаток от деления num на comp
int mod ( int num, int comp )	
{
	return num%comp;
}

//возвращает (base^gauge)mod(comp)
int pow_mod ( int base, int gauge, int comp )
{
	// 1 - если gague нечетно
	int odd_factor;

	//устанавливаем odd_factor
	if ( gauge % 2 )
		odd_factor = 1;
	else
		odd_factor = 0;

	//если возведение закончено, раскручиваем стек
	if ( gauge == 1 )
		return base;
	//Иначе, передаем результаты вниз по стеку
	else
	{	//если число ножителей нечетно,
		if ( odd_factor )
			//домножаем на base, и результат берем по модулю
			return mod ( pow_mod ( mod ( base*base, comp ), gauge/2, comp ) * base, comp );
		else//если четно, просто передае дальше
			return pow_mod ( mod ( base*base, comp ), gauge/2, comp );
	}
}

ПРоблема в том, что эта задача - чать алгоритма шифрования RSA, которрый гарантирует, что (((x^e)mod(n))^d)mod(n) = x.
Результаты работы 2080, для n = 4648, e = 31, d = 291, x = 254. Что я делаю не так??

[nexuos]

Скорее всего ключи (открытый и секретный) не совпадают. На калькуляторе проверял! (MathCad 11)

[Maslan]

Может я не понял чего-то....

 
int pow_mod2( int base, int exp, int modulo )
{  int tmp=1;
    for (int i=0; i < exp; i++) {
      tmp = (tmp * base)%modulo;
    }
    if (tmp <0) {
      return tmp+modulo;
    }
      return tmp;

}

Это покороче....

pow_mod2(pow_mod2(254,31,4648),291, 4648) тоже выдаёт 2080 (хотя, раз уж на Маткаде считали)...

Есть подозрение.....
d - ключ второго абонента, но ведь он должен быть простым вроде бы!?
Но 291=3*97.

Вычилсления идут в поле, т.е. по модулю большого простого числа, а n - не простое. (я точно не помню что там должно быть только ВЗАИМНОпростым, а что "совсем" ПРОСТЫМ)

RSA, которрый гарантирует, что (((x^e)mod(n))^d)mod(n) = x.

Почитайте внимательно для каких e,d,n это справедливо