http://www.scipy.org/

>безрезультатно
fixed

Лисп? У меня под рукой, к сожалению, нет..

Это число 4.43974... * 10^11753385352

Зачем тебе такое число? :)

Куда это?

Если не секрет, а где понадобились такие вычисления, и какая программа будет переварить результат? Это же 11753385353-значное число.

Да, чтобы было понятно - это число, записанное в десятичном виде займёт файл в 11Гб.

Перл не задумываясь говорит 1302865442. Подозреваю, что врёт :)

Блин, вообще делаю курсовой по RSA, http://ru.wikipedia.org/wiki/RSA

Именно эти числа у меня при дешифровке S(C) = C^d mod n

>Зачем тебе такое число? :)

Наверное он с RSA играется.

/me до последнего не хотел лезть в исходники и смотреть реализацию rsa, ибо все предыдущие вычисления делал в ooocalc, придетсо лезть в чужой код.

Практика.

А нельзя обозначить результат вычисления за Х, а потом написать стандартное: "Из этого, очевидно, следует..."?

вот, уже нашел быстрый алгоритм: http://pavel.przone.ru/rsa.html - в самом низу.

Интересно: Wolfram Alpha дает только последние цифры результата.

http://www52.wolframalpha.com/input/?i=487272467^1352865329

Last few digits:
...7827697747

log = 2.706316990522037*10^10

Ты, наверное, в начале вычисляешь степень и потом считаешь модуль, так?
Иди ещё учись. Алгоритм пишется за 5 минут.

Посмотри сюда:

http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%B1%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B3%D0%BE_%D0%B2%D0%BE%D0%B7%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D1%8F_%D0%B2_%D1%81%D1%82%D0%B5%D0%BF%D0%B5%D0%BD%D1%8C


Единственное отличие умножать нужно по модулю. Это действительно
очень просто

Вот, проверь:

int power(int t, int k, int modn) {
// возведение t в степень k
  int res = 1;
  while (k) {
	if (k & 1) res = (res * t) % modn;
	t = (t * t) % modn;
	k >>= 1;
  }
  return res;
}


Эээх

Кстати да, логафрифмирование позволяет заменить манипуляции с числами манипуляциями с порядками. log (a ^ b) = b * log(a)

Спасибо. Мне бы эту статейку года два назад =)

Тебе (если чо), надо возводить в степень по модулю.. :]

gmp

Всем спасибо. :)

Просто я решил ВНЕЗАПНО восстановиться в универе и все же заполучить уже второй свой диплом. Еще один курсач, пара экзаменов и проект - вот я дважды и инженер... А науку успел забыть за 2 года, ибо не пригождалось на практике.

собственно, это реальная задача? ^_^

поскольку для прблизительных расчетов, просто можно разбить на экспонетну и мантиссу

еще один момент: сложность вычисления (a^b) mod c намного ниже (это умеет, емнип, dc)

еще пришло в голову: разбить степень в двоичном виде и подсчитать:

a^2, a^4=(a^2)^2... и так далее вплоть до соответстующей степени двойки

>и так далее вплоть до соответстующей степени двойки

Побитово сдвигать 11-гигабайтное число - не очень весело :)

Кстати, э... В криптографии обычно избегают чётных чисел (и, вообще, составных) ;)

>Вот, проверь:
Никакого инта тут нехватит, да и любого другого типа

bc?

>Никакого инта тут нехватит, да и любого другого типа

Лет через 10, когда оперативки будет гига по 32 и процессоры будут раз иметь по 100 ядер, наверное, можно будет посчитать в лоб на Питоне или Хаскеле :)

Хотя... Блин, возведение в степень, вроде, не распараллелить. Так что ядра тут не особо помогут :)

хм... позднее время не сказалось на твоем ответе?), если нет, то:

>> a^2, a^4=(a^2)^2... и так далее вплоть до соответстующей степени двойки

> Побитово сдвигать 11-гигабайтное число - не очень весело :)

собственно, при чем тут побитовый сдвиг?

> Кстати, э... В криптографии обычно избегают чётных чисел (и, вообще, составных) ;)

во первых какая связь с криптографией, а во-вторых, тот же RSA основан на NP-полноте (и предположение NP != P) задачи факторизации, вероятно знаешь, что public-ключ (в простейших реализациях) - есть просто произведение двух простых чисел (private - соответственно, сами множители)

> Хотя... Блин, возведение в степень, вроде, не распараллелить. Так что ядра тут не особо помогут :)

с чего бы? a^(n-1)*a -> берем половины a^(n-1) и умножаем -> profit,

только, емнип, для эффективности такого подхода нужна shared-memory (для домашних ядер это так и есть)

ты в курсе, что ты немного флудер?)

bc делает вид что всё ещё считает.