Большая степень числа

← →
Близнец (2006-01-31 06:22) [0]

Какого типа необходимо использовать переменную для возведения числа в большую степень (например, 320 в 2156 степени) , и как ею оперировать в математических выражениях?

← →
MBo © (2006-01-31 08:20) [1]

Цель какая?

← →
palva © (2006-01-31 08:46) [2]

В делфи таких типов нет. Вы должны привлечь разработки сторонних фирм или написать свою.

← →
Gero © (2006-01-31 09:21) [3]

> Какого типа необходимо использовать переменную для возведения
> числа в большую степень

Составного. Лучше всего подойдет record.

← →
Близнец (2006-01-31 09:33) [4]

2 MBo
Задание дали на учебе (заочная форма): реализация алгоритма RSA, даны P=251, Q=331, D=165131

2 palva
Спасибо, буду знать, что таких типов нет, а то уже пол инета перерыто ;)

← →
Gero © (2006-01-31 09:34) [5]

> Задание дали на учебе (заочная форма):

Ну так не зря дали. Ты должен этот тип написать самостоятельно.

← →
Gem (2006-01-31 09:39) [6]

2 Gero

> Ну так не зря дали. Ты должен этот тип написать самостоятельно.

Вообще-то преподу без разницы, хоть в тетради зашифруй, но это нереально ручками сделать...

>
> Составного. Лучше всего подойдет record.

И как его использовать можно в данном случае?

← →
Близнец (2006-01-31 09:39) [7]

← →
Gero © (2006-01-31 09:42) [8]

> но это нереально ручками сделать

Почему же, вполне реально. Я делал когда-то.

> И как его использовать можно в данном случае?

См. http://algolist.manual.ru -> Длинная арифметика.

← →
yaroslav (2006-01-31 12:10) [9]

ерунду тебе пишут!!!

алгоритм RSA (как практически ЛЮБОЙ криптографический алгоритм) берет не степень, а СТЕПЕНЬ ПО МОДУЛЮ!!!

не нужно считать 2^24 mod 25 (числа из головы ради примера) как сначала x:=2^24, а потом y:=x mod 25.

Делается так: (я понимаю, что заочник - но странно: что вам там дают преподы?)

2^24 mod 25 = 2^(6+6+6+6) mod 25 = (2^6)*(2^6)*(2^6)*(2^6) mod 25;

2^6 = 64 (это найти просто, и подсилу компьютеру),
а дальше (!) берется 64 mod 25 = 14 (вот уж точно - устный счет)
и наконец (2^6)*(2^6)*(2^6)*(2^6) mod 25 = 14*14*14*14 mod 25. согласись, что это проще, чем 64*64*64*64 mod 25 ?!
Дальше в том же духе, пока не "спустишься" до совсем уж элементарных чисел... Таким вот образом, кстати, "ручками" и считают (ну или считали).
Счет, действительно - УСТНЫЙ!

А задача для программирования - как раз разбиение "большого" числа на "маленькие" и применение уже к ним операции mod. Тут хоть longint в longint возводи!

← →
yaroslav (2006-01-31 12:12) [10]

Здесь другая арифметика - МОДУЛЬНАЯ!!
А в ней другие правила...

← →
Близнец (2006-02-01 06:33) [11]

2 yaroslav
спасибо большое за разъяснение, буду пробовать реализовать

> я понимаю, что заочник - но странно: что вам там дают преподы

а ничего практически не дают, вот рассмотрели по-быстрому, как число 5 зашифровать, где p, q и n однозначные числа, а в нагрузку выдали задание в электронном виде, а препода уже до экзамена не увидем (и в институте не найдешь)

← →
MBo © (2006-02-01 06:33) [12]

FGInt поищи

← →
Близнец (2006-02-01 06:40) [13]

2 MBo
спасибо, это тоже посмотрю

2 Близнец
будут вопросы - пиши на мыло, отвечу с радостью...

http://kladovka.net.ru/index.cgi?pid=list&rid=53

http://kladovka.net.ru/index.cgi?pid=list&rid=322

а в чем алгоритм состоит?)
если я правильно понял - P=251, Q=331, D=165131
надо P^Q mod D - по калькулятору Windows получим 59800

> Какого типа необходимо использовать переменную
> P=251, Q=331, D=165131
Достаточно использовать переменную типа Integer
Только это не будет возведение в степень. Потому что при возведении в степень нужно после каждого умножения делить результат на модуль и брать остаток. Приблизительно об этом говорил yaroslav

Почитайте здесь http://www.racal.ru/rsp/rsa.htm Наколько я понимаю это компиляция из книги Брюса Шнайера "Прикладная криптография"

← →
Близнец (2006-02-02 06:15) [19]

Всем спасибо за желание помочь, пока времени не было разбираться (сегодня 3 экзамена), думаю скоро будут вопросы ;)

Большая степень числа Найти похожие ветки