模块化指数 [英] Modular Exponentiation

问题描述

我想使用此方法，以便分解具有大指数的基数，因为标准C ++库中的数据类型不存储大的数字。

问题是在最后一个循环中，我使用 fmod（）函数来修改大数字。答案应该是1，但我会得到16.有人看到一个问题吗？

  #include< iostream> 
 #include< vector> 
 #include< math.h> 
 
 using namespace std; 
 
 typedef vector< int> ivec; 
 ivec binStorage，expStorage; 
 
 void exponents（）
 {
 for（int j = binStorage.size（）; j> = 0; j--）
 if（binStorage [binStorage .size（） -  j-1]！= 0）
 expStorage.push_back（pow（2，j））; 
} 
 
 void binary（int number）
 {
 int remainder; 
 
 if（number< = 1）
 {
 cout<数; 
 return; 
} 
 
 remainder = number％2; 
 binary（number>> 1）; 
 cout<<余; 
 binStorage.push_back（remainder）; 
} 
 
 int main（）
 {
 int num = 117; 
 int message = 5; 
 int mod = 19; 
 int prod = 1; 
 binary（num）; 
 cout<< endl; 
 exponents（）; 
 
 cout<< \\\
Exponents：< endl; 
 for（int i = 0; i  cout< expStorage [i]< ; 
 
 cout<< endl; 
 cout<< \\\
Message<  - << 指数<< endl; 
 for（int i = 0; i  {
 cout<消息<  - << expStorage [i]< endl; 
 prod * = fmod（pow（message，expStorage [i]），mod）; 
} 
 cout<< \\\
Answer：< fmod（prod，mod）< endl; 
 return 0; 
} 
  

以下是我的结果：

  1110101 
 
指数：
 64 32 16 4 1 
 
消息指数
 5- 64 
 5-32 
 5-16 
 5-4 
 5-1 
 
回答：16 
 
处理退回0（0x0）执行时间：0.085 s 
按任意键继续。 
  

编辑：
这是问题循环。

  for（int i = 0; i  {
 cout<消息<  - << expStorage [i]< endl; 
 prod * = fmod（pow（message，expStorage [i]），mod）; 
} 
  

解决方案

模幂运算算法。按照链接中的步骤，您发布的算法缩减为下面的代码：

  #include< iostream> 
 #include< cmath> 
 
 // B：Base 
 // E：Exponent 
 // M：Modulo 
 constexpr int powermod（int const B，int const E，int const M ）{
 return（（E> 1）？（powermod（B，E / 2，M）* powermod（B，E / 2，M） M 
：（E == 0）？1：B％M） 
} 
 
 int main（）{
 int const e = 117; 
 int const b = 5; 
 int const m = 19; 
 
 std :: cout<< Answer：<< powermod（b，e，m）< std :: endl; 
 
 return 0; 
} 
  

注意，我使用 constexpr 。如果你的编译器不支持它，你可以删除它。使用 constexpr ，并且输入参数是常量表达式，像上面的例子，幂指数的计算将在编译时发生。

现在关于您发布的代码：

• 看起来 fmod 不适用于大数字喜欢（ 5 ^ 32 和 5 ^ 64 ）并给出错误结果。




• 此外，您的程式码会遭遇编译错误和执行阶段错误。

  基于递归计算模数。基本上是上面发布的算法的一个变体，安全防护力为4.（见下面的函数 safemod（））：

---

  #include< iostream> 
 #include< cmath> 
 #include< vector> 
 
 using namespace std; 
 
 typedef vector< int> ivec; 
 
 // B：Base（eg，5）
 // E：Exponent（eg，32）
 // M：Modulo（eg，19）
双安全码（双B，双E，双M）{
 return（（E> 4）？fmod（safemod（B，E / 2，M）* safemod（B，E / 2，M） M）
：
 fmod（pow（B，E），M））; 
} 
 
 void exponents（ivec const& binStorage，ivec& expStorage）{
 int j（pow（2.0，binStorage.size（） 
 for（vector< int> :: const_iterator it（binStorage.begin（）），ite（binStorage.end（））; it！= ite; ++ it）{
 if = 0）expStorage.push_back（j）; 
 j / = 2; 
} 
} 
 
 void binary（int const number，ivec& binStorage）{
 if（number> 0）{
 int remainder = number％2; 
 binary（number / 2，binStorage）; 
 binStorage.push_back（remainder）; 
} 
} 
 
 int main（）{
 int num = 117; 
 int message = 5; 
 int mod = 19; 
 int prod = 1; 
 ivec binStorage，expStorage; 
 
 binary（num，binStorage）; 
 for（size_t i（0）; i  cout<< endl; 
 
指数（binStorage，expStorage）; 
 cout<< \\\
Exponents：< endl; 
 for（size_t i（0）; i  cout<< endl; 
 
 cout<< \\\
Message<  - << 指数<< endl; 
 for（size_t i（0）; i  cout<消息<  - << expStorage [i]< endl; 
 prod * = safemod（message，expStorage [i]，mod）; 
} 
 
 cout<< \\\
Answer：< fmod（prod，mod）< endl; 
 
 return 0; 
} 
  

输出：

< >

1110101

指数：
64 32 16 4 1

消息指数

5 - 64

5 - 32

5 - 16

5 - 1

回答：1

I am trying to use this method in order to break down bases with large exponents because data types in the standard C++ library do not store numbers that large.

The problem is in the last loop where I use the fmod() function to mod my large numbers. The answer is supposed to be 1 but I am getting 16. Does someone see a problem?

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

typedef vector<int> ivec;
ivec binStorage, expStorage;

void exponents()
{
    for (int j=binStorage.size(); j>=0; j--)
        if(binStorage[binStorage.size()-j-1]!=0)
            expStorage.push_back(pow(2, j));
}

void binary(int number)
{
    int remainder;

    if(number <= 1)
    {
        cout << number;
        return;
    }

    remainder = number%2;
    binary(number >> 1);
    cout << remainder;
    binStorage.push_back(remainder);
}

int main()
{
    int num = 117;
    int message = 5;
    int mod = 19;
    int prod = 1;
    binary(num);
    cout << endl;
    exponents();

    cout << "\nExponents: " << endl;
    for (int i=0; i<expStorage.size(); i++)
        cout << expStorage[i] << " " ;

    cout << endl;
    cout << "\nMessage" << "-" << "Exponent" << endl;
    for (int i=0; i<expStorage.size(); i++)
    {
        cout << message << "-" << expStorage[i] << endl;
        prod *= fmod(pow(message, expStorage[i]), mod);
    }
    cout << "\nAnswer: " << fmod(prod, mod) << endl;
    return 0;
}

Here are my results:

1110101

Exponents:
64 32 16 4 1

Message-Exponent
5-64
5-32
5-16
5-4
5-1

Answer: 16

Process returned 0 (0x0)   execution time : 0.085 s
Press any key to continue.

Edit: Here is the problem loop.

for (int i=0; i<expStorage.size(); i++)
    {
        cout << message << "-" << expStorage[i] << endl;
        prod *= fmod(pow(message, expStorage[i]), mod);
    }

解决方案

The algorithm you posted is the modular exponentiation algorithm. Following the steps in the link you posted the algorithm reduces down to the following piece of code:

#include <iostream>
#include <cmath>

// B : Base
// E : Exponent
// M : Modulo
constexpr int powermod(int const B, int const E, int const M) {
  return ((E > 1) ? (powermod(B, E / 2, M) * powermod(B, E / 2, M) * powermod(B, E % 2, M)) % M
                  : (E == 0) ? 1 : B % M);
}

int main() {
  int const e = 117;
  int const b = 5;
  int const m = 19;

  std::cout << "Answer: " << powermod(b, e, m) << std::endl;

  return 0;
}

Note, that I used constexpr. If your compiler doesn't support it, you can remove it. Using constexpr and provided that the input arguments are constant expressions, like the example above, the computation of the power exponential will take place at compile time.

Now regarding the code you posted:

• It seems that fmod doesn't work well with big numbers like (5^32 and 5^64) and gives false results.

• Also your code suffers from compile errors and runtime errors so I corrected it.

• I coded an algorithm that computes the modulo based on recursion. Basically is a variation of the algorithm I posted above with a safe guard power of 4. (see function safemod() below):

---

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

typedef vector<int> ivec;

// B : Base     (e.g., 5)
// E : Exponent (e.g., 32)
// M : Modulo   (e.g., 19)
double safemod(double B, double E, double M) {
  return ((E > 4) ? fmod(safemod(B, E / 2, M) * safemod(B, E / 2, M), M)
    :
    fmod(pow(B, E), M));
}

void exponents(ivec const &binStorage, ivec &expStorage) {
  int j(pow(2.0, binStorage.size() - 1));
  for (vector<int>::const_iterator it(binStorage.begin()), ite(binStorage.end()); it != ite; ++it) {
    if (*it != 0) expStorage.push_back(j);
    j /= 2;
  }
}

void binary(int const number, ivec &binStorage) {
  if (number > 0) {
    int remainder = number % 2;
    binary(number / 2, binStorage);
    binStorage.push_back(remainder);
  }
}

int main() {
  int num     = 117;
  int message = 5;
  int mod     = 19;
  int prod    = 1;
  ivec binStorage, expStorage;

  binary(num, binStorage);
  for (size_t i(0); i < binStorage.size(); ++i) cout << binStorage[i];
  cout << endl;

  exponents(binStorage, expStorage);
  cout << "\nExponents: " << endl;
  for (size_t i(0); i<expStorage.size(); ++i) cout << expStorage[i] << " ";
  cout << endl;

  cout << "\nMessage" << "-" << "Exponent" << endl;
  for (size_t i(0); i<expStorage.size(); ++i) {
    cout << message << "-" << expStorage[i] << endl;
    prod *= safemod(message, expStorage[i], mod);
  }

  cout << "\nAnswer: " << fmod(prod, mod) << endl;

  return 0;
}

Output:

1110101

Exponents: 64 32 16 4 1

Message-Exponent

5 - 64

5 - 32

5 - 16

5 - 1

Answer: 1

这篇关于模块化指数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！