Вычислить значение выражения a^b mod n

@kLeimor · Регистрация: 15.05.2012

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

Условия задачи в вложении. Нужна помощь, очень срочно, до завтра.

@Mikl___ · 26.06.2013, 11:12

kLeimor,
обленился до такой степени, что даже задание набрать не можешь

а тем не менее нарушение правил форума

Запреты и ограничения.
5.18 Запрещено размещать задания в виде картинок и других файлов с их текстом.

@kLeimor · 26.06.2013, 12:35 **[ТС]**

Упс, ошибся, каюсь =(
Не знаю как подредактировать тему=(
Найти a^b mod n
а, b, n - вводятся с клавиатуры.
b>10⁵, n приблизительно 10⁴

@Dmitrinik · 26.06.2013, 19:24

Если только очень простенько,то

Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
    mov  ecx,b
    mov  ebx,n
    mov  eax,a
    cdq
  L1:
    div  ebx
    mov  eax,edx
    dec  ecx
    jz   L2
    cdq
    mul  a
    jmp  L1
  L2:

Результат будет в EAX

murderer · 27.06.2013, 12:23

Кажется работает, но не понимаю как

Кликните здесь для просмотра всего текста

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
uses
  Math;
 
function calc(a,b,n: integer): integer;
begin
  result:=a mod n;
  for b:=b downto 1 do
    if b>1 then
      result:=(result mod n)*a
    else
      result:=result mod n;
end;
 
begin
  writeln(round(IntPower(5,7)) mod 4,' = ',calc(5,7,4));
  readln;
end.

a^b mod n = a mod n * a mod n * a mod n ...

@Mikl___ · 27.06.2013, 12:31

Assembler
1
2
3
4
5
6
7
     mov eax,a
     mov ecx,b
     dec ecx
a1: mul a
     loop a1
     div n
    mov result,edx

Добавлено через 6 минут

C
1
2
3
4
5
6
7
8
9
10
int power(int a, int b) {
// возведение a в степень b
  int res = 1;
  while (b) {
    if (b & 1) res *= a;
    a *= a;
    b >>= 1;
  }
  return res;
}

murderer · 27.06.2013, 12:34

@Mikl___

b>10⁵

Сомневаюсь, что сработает подход "в лоб". А вот у Dmitrinik вроде-бы работает.

@Mikl___ · 27.06.2013, 13:15

Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
    finit
        fild b ;Загружаем показатель степени
        fild a ;Загружаем основание
        fyl2x ;Стек FPU теперь содержит: ST(0)=y*log2(x)
        fld st(0) ;Создаем еще одну копию z
        frndint   ;Округляем ST(0)=trunc(z)        | ST(1)=z
        fxch st(1);ST(0)=z                             | ST(1)=trunc(z)
        fsub st(0),st(1)  ;ST(0)=z-trunc(z)        | ST(1)=trunc(z)
        f2xm1  ;ST(0)=2**(z-trunc(z))-1            | ST(1)=trunc(z)
        fld1     ;ST(0)=1 ST(1)=2**(z-trunc(z))-1  | ST(2)=trunc(z)
        faddp st(1),st ;ST(0)=2**(z-trunc(z))      | ST(1)=trunc(z)
        fscale ;ST(0)=(2**(z-trunc(z)))*(2**trunc(z))=2**(z)
        fistp result ;Результат
        mov edx,dword ptr result+4
        mov eax,dword ptr result
    div N
    mov dword ptr result,edx

Добавлено через 4 минуты
херасе, "простенькая программа"

murderer · 27.06.2013, 13:25

Не - происходит переполнение и прога вылетает на fistp

Кликните здесь для просмотра всего текста

Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
{$APPTYPE CONSOLE}
function calc(a,b,n: integer): integer;
begin
  result:=a mod n;
  for b:=b downto 1 do
    if b>1 then
      result:=(result mod n)*a
    else
      result:=result mod n;
end;
 
function calc2(a,b,n: integer): int64;stdcall;
asm
  fild   [b]
  fild   [a]
  fyl2x
  fld    st(0)
  frndint
  fxch   st(1)
  fsub   st(0),st(1)
  f2xm1
  fld1
  faddp  st(1),st
  fscale
  fistp  [result]
  mov    edx,dword[result+4]
  mov    eax,dword[result]
  div    [n]
  mov    dword[result],edx
  mov    dword[result+4],0
end;
 
begin
  writeln(calc2(5,70000,4),' = ',calc(5,70000,4));
  readln;
end.

На маленьких степенях конечно работает

Добавлено через 2 минуты

херасе, "простенькая программа"

Ну если знать математику то не сложно ведь

@Mikl___ · 27.06.2013, 13:31

murderer,
не может "простенькая программа" быть с аргументами b>10⁵, n $https://www.cyberforum.ru/cgi-bin/latex.cgi?\approx$ 10⁴

Добавлено через 2 минуты
мне кажется есть разница между (a^b) mod N и (a mod N)^b

murderer · 27.06.2013, 13:33

Присмотрись - там не (a mod N)^b

Наверное вытекает отсюда

(x + y) mod N = ((x mod N) + (y mod N)) mod N

(x - y) mod N = ((x mod N) - (y mod N)) mod N

(x * y) mod N = ((x mod N) * (y mod N)) mod N

@Mikl___ · 27.06.2013, 13:40

у меня Виндовый калькулятор отказался вычислять 5⁷⁰⁰⁰⁰
видимо, основываясь на (x * y) mod N = ((x mod N) * (y mod N)) mod N переиначили в
(x * х) mod N = ((x mod N) * (х mod N)) mod N = х² mod N=((x mod N)²) mod N
я о "Китайской теореме об остатках" (Chinese Remainder Theorem) слышал, но никогда с ней не сталкивался

murderer · 27.06.2013, 14:01

Нашёл как посчитать за O(logn) - тырц

Pascal
1
2
3
4
5
6
7
8
9
10
11
function calc2(a,b,n: integer): integer;
begin
  result:=1;
  while b<>0 do
  begin
    if b and 1<>0 then
      result:=result*a mod n;
    b:=b shr 1;
    a:=a*a mod n;
  end;
end;

Добавлено через 18 минут
Возведение в степень по модулю. Большие числа

@Mikl___ · 27.06.2013, 14:08

murderer,
очень похоже на

C
1
2
3
4
5
6
7
8
9
10
int power(int a, int b) {
// возведение a в степень b
  int res = 1;
  while (b) {
    if (b & 1) res *= a;
    a *= a;
    b >>= 1;
  }
  return res;
}

только mod n не хватает

Добавлено через 6 минут

C
1
2
3
4
5
6
7
8
9
10
int power(int a, int b, int n) {
// возведение a в степень b
  int res = 1;
  while (b) {
    if (b & 1) res *= a mod n;
    a *= a mod n;
    b >>= 1;
  }
  return res;
}

Новые блоги и статьи Все статьи Все блоги /
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .	Фото: Daniel Greenwood kumehtar 13.11.2025	Расскажи мне о Мире, бродяга kumehtar 12.11.2025 — Расскажи мне о Мире, бродяга, Ты же видел моря и метели. Как сменялись короны и стяги, Как эпохи стрелою летели. - Этот мир — это крылья и горы, Снег и пламя, любовь и тревоги, И бескрайние. . .

@kLeimor 5 / 5 / 5 Регистрация: 15.05.2012 Сообщений: 66

	Вычислить значение выражения a^b mod n 26.06.2013, 10:33. Показов 4384. Ответов 13 Метки нет (Все метки) Условия задачи в вложении. Нужна помощь, очень срочно, до завтра. Миниатюры 0

@kLeimor 5 / 5 / 5 Регистрация: 15.05.2012 Сообщений: 66
	26.06.2013, 12:35 [ТС]
	Упс, ошибся, каюсь =( Не знаю как подредактировать тему=( Найти a^b mod n а, b, n - вводятся с клавиатуры. b>10⁵, n приблизительно 10⁴ 0

@Mikl___ Ушел с форума 16371 / 7683 / 1080 Регистрация: 11.11.2010 Сообщений: 13,757
	27.06.2013, 13:31
	murderer, не может "простенькая программа" быть с аргументами b>10⁵, n $https://www.cyberforum.ru/cgi-bin/latex.cgi?\approx$ 10⁴ Добавлено через 2 минуты мне кажется есть разница между (a^b) mod N и (a mod N)^b 0

@Mikl___ Ушел с форума 16371 / 7683 / 1080 Регистрация: 11.11.2010 Сообщений: 13,757
	27.06.2013, 13:40
	у меня Виндовый калькулятор отказался вычислять 5⁷⁰⁰⁰⁰ видимо, основываясь на (x * y) mod N = ((x mod N) * (y mod N)) mod N переиначили в (x * х) mod N = ((x mod N) * (х mod N)) mod N = х² mod N=((x mod N)²) mod N я о "Китайской теореме об остатках" (Chinese Remainder Theorem) слышал, но никогда с ней не сталкивался 0