我要计算一米模N,其中ñ是一个素数,而米是非常大的.而这样做二进制功率计算,我想找到这样X那一个X =α(MOD N) ,然后计算一个(M模x)的模N.
显然这样的x存在于任何a,因为powers mod n在某个时刻循环,但我没有找到如何使用模块化算术计算它.我想知道我是否遗漏了某些东西,或者是否存在一些数值方法？
我正在解决一个问题:用户输入3个树高和树高限制.然后程序计算要删除的树的数量.
样本输入:
Tree1: 14
Tree2: 7
Tree3: 16
Tree limit: 11
样本输出:
Amount to remove: 8
这对我来说通常不会太糟糕,虽然我还是初学者,但问题是,我将在没有if语句的情况下计算它.我必须使用Modulus来计算.我花了很长时间研究和尝试不同的东西,但我似乎无法得到它？有任何想法吗？
这是我在学校做的一项任务.我在生成私钥时遇到问题.我的主要问题是理解我的方程式之间的关系.为了设置一切,我们有:
p = 61
q = 53
n = p * q (which equals 3233)
从这里我们得到n(phi(n))的总数等于3120,现在我们可以选择素数e; 其中1 <e <3120
e = 17
好的很容易.
对于我的任务,我们已经意识到d = 2753,但是我仍然需要能够任意生成这个值.
现在这里是我遇到麻烦的地方.我一直在仔细阅读维基百科以及某些东西没有连接.我知道,我需要找到模反元素的e (mod phi(n)),这将是d我们的私人指数.
通过维基百科阅读告诉我们找到mmi我们需要使用扩展欧几里德算法.我在python中实现了如下算法:
def egcd(a, b):
x, lastX = 0, 1
y, lastY = 1, 0
while (b != 0):
q = a // b
a, b = b, a % b
x, lastX = lastX - q * x, x …我一直在研究这个来自大量模数的维基百科的链接,这是伪代码.
function modular_pow(base, exponent, modulus)
result := 1
while exponent > 0
if (exponent mod 2 == 1):
result := (result * base) mod modulus
exponent := exponent >> 1
base = (base * base) mod modulus
return result
我不明白维基中给出的解释.为什么我要检查exp%2是偶数还是奇数.为什么我要做三个操作？
我知道,
(a*b)%m = ((a%m)*(b%m))%m
但是有可能溢出.为简单起见,假设整数大小为2位.如果a = 2(即10 2)且b = 2(即10 2),m = 3(即11 2),那么%m和b%m结果为2并且在乘法后,答案为4(即100)不适合整数大小.如果从4开始考虑2-lsb,则最终答案将为0.但实际答案为1.
我该怎么做才能避免这种情况？
我正在尝试为Rust u32和u64数据类型实现快速素性测试.作为它的一部分,我需要计算(n*n)%d其中n和d是u32(或u64,分别地).
虽然结果很容易适合数据类型,但我对如何计算它感到茫然.据我所知,没有处理器原语.
因为u32我们可以伪造它 - 铸造u64,以便产品不会溢出,然后取模数,然后再回落u32,知道这不会溢出.但是因为我没有u128数据类型(据我所知),这个技巧不起作用u64.
因此,对u64,我能想到的最明显的方式来完成,这是莫名其妙地计算x*y得到一对(carry, product)的u64,所以我们捕获,而不是仅仅失去它(或恐慌,或其他)溢出量.
有没有办法做到这一点？还是另一种解决问题的标准方法？
模逆可以计算如下（来自Rosetta Code）：
#include <stdio.h>
int mul_inv(int a, int b)
{
int b0 = b, t, q;
int x0 = 0, x1 = 1;
if (b == 1) return 1;
while (a > 1) {
q = a / b;
t = b, b = a % b, a = t;
t = x0, x0 = x1 - q * x0, x1 = t;
}
if (x1 < 0) x1 += b0;
return x1;
}
但是，ints如您所见，输入为 。上面的代码是否也适用于无符号整数（例如 …
math integer-overflow greatest-common-divisor modular-arithmetic
我目前正在将nacl库转换为risc-v。我已经有poly1305工作。我正在尝试使用risc-v核心指令集来执行此操作，因此我没有乘法器。Pol1305的算法正在使用ceil（m / 16）* 17 * 17 8位乘法，其中m是消息长度（以字节为单位）（两个2 ^ 130整数乘以2 ^ 8以2 ^ 130-5为基数） 。因此，我想使用快速乘法算法来保持快速。
目前，我有用于乘法的移位加法算法。但是，对于8位值，这需要63个周期，因为我需要避免分支（定时侧通道），因此涉及一些需要更多周期的屏蔽。
andi t2, t0, 1 //t0 is the multiplier
sub t2, zero, t2 //creating a mask
and t3, t1, t2 //applying the mask to the multiplicand
add a0, a0, t3 //doing the add
srli t0, t0, 1 //shifting the multiplier
slli t1, t1, 1 //shifting the multiplicand
这给了我每次乘法63个周期的有效结果。问题在于，对于131字节的消息，程序的总执行时间为175219个周期。此时，将9 * 17 * 17 * 63 = 163863个周期用于乘法。我想改善。
assembly multiplication micro-optimization modular-arithmetic riscv
这是我用于计算的代码(n^p)%mod。不幸的是，当我从方法调用它时，它对于mod（在我的情况下mod = 10000000000ULL）的大值失败main()。任何的想法; 为什么？
ull powMod(ull n, ull p, ull mod) {
ull ans = 1;
n = n%mod;
while(p) {
if(p%2 == 1) {
ans = (ans*n)%mod;
}
n = (n*n)%mod;
p /= 2;
}
return ans;
}
这里，ull是一个 typedef unsigned long long。
c++ algorithm cryptography exponentiation modular-arithmetic
#include <bits/stdc++.h>
#define mx 1000005
#define mod 1000003
using namespace std;
long long arr[mx];
int fact()
{
arr[0]=1;
for(int i=1; i<mx; i++)
{
arr[i]=((i%mod)*(arr[i-1]%mod))%mod;
}
}
int main()
{
int t;
long long a,b,C,E;
fact();
cin>>t;
while(t--)
{
cin>>a>>b;
C=(arr[a]%mod)%mod;
E=((arr[b])%mod)*((arr[a-b])%mod)%mod;
}
}
在这个问题中我必须计算 (C/E)%1000003。我如何使用模乘逆技术来做到这一点？还有其他方法可以计算这个吗？