Возведение в степень и деление с остатком

@Demonstels · Регистрация: 10.10.2011

Author24 — интернет-сервис помощи студентам

Cабж, как реализовать в delphi: (a^b) mod c.

@zuxa-zuxa · 23.06.2012, 19:06

a^b = exp(ln(a)*b)

@Demonstels · 23.06.2012, 19:09 **[ТС]**

Спасибо конечно, но как отдельно степень сделать я знаю).

@zuxa-zuxa · 23.06.2012, 19:13

Delphi

1 2	c:=exp(ln(a)*b); c:=c mod 2;

Не так ли?

@Puporev · 23.06.2012, 19:21

Сообщение от zuxa-zuxa

Не так ли?

Не так, ибо с вещественного типа а mod работает только с целыми типами.

@zuxa-zuxa · 23.06.2012, 19:28

А так?

Delphi

1
2
3

c:=exp(ln(a)*b);
k:=round(c);
r:=k mod 2;

@Puporev · 23.06.2012, 19:37

zuxa-zuxa, Это совсем не так решается. На форуме несколько раз обсуждалось, нашел пока только у сишников.
Возведение в степень по модулю для чисел близких к max long long

Добавлено через 4 минуты
Вообще это олимпиадная задача.
http://www.e-olimp.com/problems/1121

@zuxa-zuxa · 23.06.2012, 19:42

http://coderlife.ru/progr/bito... vojki.html
Ну вот к примеру у дельфишников

@Puporev · 23.06.2012, 19:45

zuxa-zuxa, Во-первых я имел ввиду наш форум, а во вторых та ссылка не имеет ничего общего с задачей возведения в степень по модулю.
Ты вообще сразу начал путать, у нас mod c, а не mod 2.

@Demonstels · 23.06.2012, 19:57 **[ТС]**

Так это на делфи возможно реализовать?

@Nikitko_Cent · 24.06.2012, 19:47

Сообщение от Demonstels

Так это на делфи возможно реализовать?

Т.е. тебе нужно сначало возвести в степень A^B, а потом от полученного значения найти остаток от деления на число C?

Что то я наверно поздно откликнулся

@duhar · 25.06.2012, 15:20

Delphi

Uses Math;
...
var a,b,c:Real;
     r:integer;
begin
  r:=Power(a,b) mod c;
  ShowMessage('r='+IntToStr(r));
end;

@Demonstels · 29.06.2012, 16:33 **[ТС]**

Сообщение от duhar

Delphi

Uses Math;
...
var a,b,c:Real;
     r:integer;
begin
  r:=Power(a,b) mod c;
  ShowMessage('r='+IntToStr(r));
end;

Я попробовал данный код, выдает ошибку что операнд не верного типа, разве можно операцию с вещественными числами присваивать integer?

@Nikitko_Cent · 29.06.2012, 16:36

Сообщение от Demonstels

Я попробовал данный код, выдает ошибку что операнд не верного типа, разве можно операцию с вещественными числами присваивать integer?

Скажи точно: тебе операции нужно производить только с целыми числами, т.е. A,B,C только целые? Если да, то сделать это будет элементарно, если нет-то я не знаю

@duhar · 30.06.2012, 14:53

Сообщение от Demonstels

Я попробовал данный код, выдает ошибку что операнд не верного типа, разве можно операцию с вещественными числами присваивать integer?

Код написан на коленке без учета всех условий, возьми и поменяй тип

@Demonstels · 01.07.2012, 18:19 **[ТС]**

Код написан на коленке без учета всех условий, возьми и поменяй тип

r:=Power(a,b) mod c; - Выдает ошибку: Operator not applicable to this operand type, при различных типах.

Скажи точно: тебе операции нужно производить только с целыми числами, т.е. A,B,C только целые? Если да, то сделать это будет элементарно, если нет-то я не знаю

Да, все эти числа должны быть целые.

Добавлено через 14 минут
Полное условие задачи, вдруг кому поможет:
Алгоритм создания ЭЦП:
1) Выбирают большое простое число P.
2) Выбирают большое простое число Q, которое является делителем числа (P-1).
3) Выбирают число G, 1<G<(P-1), (G^Q) mod P = 1.
4) Генерируют секретный ключ T, 1<T<Q.
5) Вычисляют открытый ключ R = (G^T) mod P.
6) Находят хэш-функцию (В качестве примера она дана), m = ((k^2)+1000) mod P, где k- кол-во символов.
7) Выбирают случайное число F, 1<F<Q.
8) Создание ЭЦП:
a = ((G^F) mod P) mod Q.
b = (T*a + F*m) mod Q.
9) Вывести результат: (a, b).
*Ecли m mod Q = 0, то это значение принимают равным 1.
*Если a = 0, то выбирают другое значение F и вычисляют вновь.

@Puporev · 01.07.2012, 18:33

Сообщение от Demonstels

Полное условие задачи, вдруг кому поможет:

СМ этого и начал бы, глядишь флуда бы не было, а то

Сообщение от Demonstels

как реализовать в delphi: (a^b) mod c.

Ну тебе и отвечают на это типа

Delphi

p:=1;
for i:=1 to b do
p:=p*a;
x:=p mod c;

что великолепно работает для чисел типа integer.
Но тебе-то нужны числа типа 2^63, а возможно и больше, а ты мозг конопатишь.

@Demonstels · 04.07.2012, 01:13 **[ТС]**

Но тебе-то нужны числа типа 2^63, а возможно и больше, а ты мозг конопатишь.

Насколько я понимаю это длинная арифметика? Я в ней вообще не бум бум(.

murderer · 04.07.2012, 09:26

IntPower не подойдёт?

Добавлено через 13 минут
https://www.cyberforum.ru/post1161020.html

@Demonstels · 06.07.2012, 14:59 **[ТС]**

Испробовав код: https://www.cyberforum.ru/post1161020.html, убедился в том что он не может посчитать к примеру 41^25, на степенях по ниже он работает.
Ладно подумал я и скачал: http://www.delphisources.ru/pa... lator.html, но он не прошел первый же тест 41^25 mod 269, хотя его собрат из Windows отлично все считает.
Есть ли еще исходники калькулятора Windows(желательно Pascal)? Буду очень благодарен за ссылки.

@Demonstels 0 / 0 / 1 Регистрация: 10.10.2011 Сообщений: 21
		1
	Возведение в степень и деление с остатком 23.06.2012, 18:58. Показов 3396. Ответов 19 Метки нет (Все метки) Cабж, как реализовать в delphi: (a^b) mod c. 0

@zuxa-zuxa Мишка Косолапый :) 284 / 254 / 86 Регистрация: 15.02.2012 Сообщений: 1,511
	23.06.2012, 19:06	2
	*a^b = exp(ln(a)b)** 0

@Demonstels 0 / 0 / 1 Регистрация: 10.10.2011 Сообщений: 21
	23.06.2012, 19:09 [ТС]	3
	Спасибо конечно, но как отдельно степень сделать я знаю). 0

@Puporev Почетный модератор 64300 / 47595 / 32743 Регистрация: 18.05.2008 Сообщений: 115,181
	23.06.2012, 19:21	5
	Сообщение от zuxa-zuxa Не так ли? Не так, ибо с вещественного типа а mod работает только с целыми типами. 0

@Puporev Почетный модератор 64300 / 47595 / 32743 Регистрация: 18.05.2008 Сообщений: 115,181
	23.06.2012, 19:37	7
	zuxa-zuxa, Это совсем не так решается. На форуме несколько раз обсуждалось, нашел пока только у сишников. Возведение в степень по модулю для чисел близких к max long long Добавлено через 4 минуты Вообще это олимпиадная задача. http://www.e-olimp.com/problems/1121 1

@zuxa-zuxa Мишка Косолапый :) 284 / 254 / 86 Регистрация: 15.02.2012 Сообщений: 1,511
	23.06.2012, 19:42	8
	http://coderlife.ru/progr/bito... vojki.html Ну вот к примеру у дельфишников 0

@Puporev Почетный модератор 64300 / 47595 / 32743 Регистрация: 18.05.2008 Сообщений: 115,181
	23.06.2012, 19:45	9
	zuxa-zuxa, Во-первых я имел ввиду наш форум, а во вторых та ссылка не имеет ничего общего с задачей возведения в степень по модулю. Ты вообще сразу начал путать, у нас mod c, а не mod 2. 0

@Demonstels 0 / 0 / 1 Регистрация: 10.10.2011 Сообщений: 21
	23.06.2012, 19:57 [ТС]	10
	Так это на делфи возможно реализовать? 0

@Nikitko_Cent 148 / 118 / 37 Регистрация: 27.10.2011 Сообщений: 690
	24.06.2012, 19:47	11
	Сообщение от Demonstels Так это на делфи возможно реализовать? Т.е. тебе нужно сначало возвести в степень A^B, а потом от полученного значения найти остаток от деления на число C? Что то я наверно поздно откликнулся 0

@Nikitko_Cent 148 / 118 / 37 Регистрация: 27.10.2011 Сообщений: 690
	29.06.2012, 16:36	14
	Сообщение от Demonstels Я попробовал данный код, выдает ошибку что операнд не верного типа, разве можно операцию с вещественными числами присваивать integer? Скажи точно: тебе операции нужно производить только с целыми числами, т.е. A,B,C только целые? Если да, то сделать это будет элементарно, если нет-то я не знаю 0

@duhar 61 / 44 / 6 Регистрация: 15.01.2012 Сообщений: 167
	30.06.2012, 14:53	15
	Сообщение от Demonstels Я попробовал данный код, выдает ошибку что операнд не верного типа, разве можно операцию с вещественными числами присваивать integer? Код написан на коленке без учета всех условий, возьми и поменяй тип 0

@Demonstels 0 / 0 / 1 Регистрация: 10.10.2011 Сообщений: 21
	01.07.2012, 18:19 [ТС]	16
	Код написан на коленке без учета всех условий, возьми и поменяй тип r:=Power(a,b) mod c; - Выдает ошибку: Operator not applicable to this operand type, при различных типах. Скажи точно: тебе операции нужно производить только с целыми числами, т.е. A,B,C только целые? Если да, то сделать это будет элементарно, если нет-то я не знаю Да, все эти числа должны быть целые. Добавлено через 14 минут Полное условие задачи, вдруг кому поможет: Алгоритм создания ЭЦП: 1) Выбирают большое простое число P. 2) Выбирают большое простое число Q, которое является делителем числа (P-1). 3) Выбирают число G, 1<G<(P-1), (G^Q) mod P = 1. 4) Генерируют секретный ключ T, 1<T<Q. 5) Вычисляют открытый ключ R = (G^T) mod P. 6) Находят хэш-функцию (В качестве примера она дана), m = ((k^2)+1000) mod P, где k- кол-во символов. 7) Выбирают случайное число F, 1<F<Q. 8) Создание ЭЦП: a = ((G^F) mod P) mod Q. b = (Ta + Fm) mod Q. 9) Вывести результат: (a, b). Ecли m mod Q = 0, то это значение принимают равным 1. Если a = 0, то выбирают другое значение F и вычисляют вновь. 0

@Demonstels 0 / 0 / 1 Регистрация: 10.10.2011 Сообщений: 21
	04.07.2012, 01:13 [ТС]	18
	Но тебе-то нужны числа типа 2^63, а возможно и больше, а ты мозг конопатишь. Насколько я понимаю это длинная арифметика? Я в ней вообще не бум бум(. 0

murderer 4165 / 1817 / 216 Регистрация: 06.10.2010 Сообщений: 4,074
	04.07.2012, 09:26	19
	IntPower не подойдёт? Добавлено через 13 минут https://www.cyberforum.ru/post1161020.html 1

@Demonstels 0 / 0 / 1 Регистрация: 10.10.2011 Сообщений: 21
	06.07.2012, 14:59 [ТС]	20
	Испробовав код: https://www.cyberforum.ru/post1161020.html, убедился в том что он не может посчитать к примеру 41^25, на степенях по ниже он работает. Ладно подумал я и скачал: http://www.delphisources.ru/pa... lator.html, но он не прошел первый же тест 41^25 mod 269, хотя его собрат из Windows отлично все считает. Есть ли еще исходники калькулятора Windows(желательно Pascal)? Буду очень благодарен за ссылки. 0