Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/4: Рейтинг темы: голосов - 4, средняя оценка - 5.00
Mars74
1 / 1 / 0
Регистрация: 25.03.2013
Сообщений: 31
1

Возведение в степень по модулю для большого числа

12.03.2014, 21:49. Просмотров 635. Ответов 1
Метки нет (Все метки)

C++
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <vcl.h>
#pragma hdrstop
#include <iostream>
#include <math.h>
#include <conio.h>
using namespace std;
//---------------------------------------------------------------------------
#pragma argsused
long powmod(long a, long k9, long p)  // a - основание k9 степень p модуль
{
  long b=1;
  while (k9) {
    if (k9%2==0) {
      k9 /= 2;
      a = (a*a)%p;
      }
    else {
      k9--;
      b = (b*a)%p;
      }
  }
  return b;
}
int main()
{  long a,p;
 
  cout << "chislo dla testa: "; cin >> p ;
   a = rand() % (p-1);
  cout << "chislo a = " << a << endl ;
 //k= a ^((p-1) div 2) mod p;  - вычисляем по поэтапно
  double k0;
  k0=(p-1)/2;      // показатель степени
  int k01;
  k01 = (int) k0;       //  целая часть показателя степени (p-1) div 2
  cout<<"k01 = "<< k01 <<endl;
   //+++++
  long k9, k;
  k9= k01;
   k = powmod(a, k9, p);
   cout<<"!!!!! k = "<< k <<endl;
 
 
  int p01= p-1 ; // для условия
  if (k == 1) {
        cout<<"  Prostoe chislo "<< p  <<endl;
        }
        else if (k == p01 )
        {
        cout<<"  Prostoe chislo "<< p  <<endl;
        }
    else {
        cout<<" Ne prostoe chislo "<< p  <<endl;
    }
    getch(); getch();
    return 0;
}
Если для теста ввожу число 3991139 то алгоритм начинает работать не правильно... Подскажите как модифицировать функцию powmod
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.03.2014, 21:49
Ответы с готовыми решениями:

Возведение в степень
Кто нибудь знает быстро работающий алгоритм возведения числа х в степень n по модулю у, где х, у, n...

Возведение большого числа в большую степень
Появился вопрос. Реализовую алгоритм Диффи — Хеллмана и не могу возвести 300-значное число в...

Возведение числа в степень по модулю в C#
пример: 2^11(mod5)=3(mod5). Вот, что я написала, но еще как-то нужно сделать проверку, что степень...

Возведение числа в степень по модулю
Кто может поделиться функцией быстрого возведения в степень по модулю N^-1 MOD M

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

1
saden
183 / 167 / 52
Регистрация: 27.01.2013
Сообщений: 788
12.03.2014, 21:52 2
надо предусмотреть тип, чтобы а*а влазило.
Раз основной тип лонг, для произведения надо лонг лонг или инт64
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.03.2014, 21:52

Возведение числа в степень за минимальное количество умножений, не используя возведение в степень (в чем ошибка?)
должно число подводиться в степень за минимальное кол умножения не используя возведение в степень....

Возведение в степень по модулю
Доброго дня всем. Имеется код java, пытаюсь реализовать алгоритм быстрого возведения в степень...

Возведение в степень по модулю
Необходимо, используя 1)&quot;Метод, эффективно использующий память&quot; 2)&quot;Метод с использованием...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru