找到了一些模素数的倒数 [英] Find the inverse of a number modulo a prime

问题描述

我在想一个算法，解决了一致性 AX = 1模p 与对素数。 我想使用费马大定理。因为我知道，

A ^（P-1）= 1模p

和

A ^（P-1）= A *（A ^（P-2））

这意味着 A ^（P-2）模p 是解决方案。不幸的是这种解决方案，虽然数学上正确，不利于电脑因为对于大素数我必须做的 A ^（P-2）通常是不可计算的。

哪种算法好计算机科学？

解决方案

  

因为对于大素数我必须做的 A ^（P-2）通常是不可计算的。

您需要模幂，所以由平方的幂=htt​​p://stackoverflow.com /一/一百〇一万一千九百九十五分之一千四百〇九万三千六百一>由IVlad提到你只需要Θ（日志P）尺寸的数量至多模乘 P-1 。中间结果被围点^ 2 ，所以尽管 A ^（P-2）不是可计算为大素数，（一^（P-2））％P 通常是。这种方法实现起来很简单：

 无符号长长invert_mod（无符号长一长，无符号长长P）{
    无符号长长的前= P-2，结果= 1;
    而（例如大于0）{
        如果（例如％2 == 1）{
            结果=（结果* A）％P;
        }
        一个=（A * A）％磷;
        前/ = 2;
    }
    返回结果;
}
 

，但有几个缺点。 （P-1）^ 2 必须重新presentable在使用类型（不除巨大 <$ C $的一个问题[ C> P ]如果任意precision整数使用），或者你得到应有的溢出无效的结果，它总是使用至少日志（P-2）/日志2 模乘。

扩展欧几里得算法，所建议的user448810 或等效地连分数法，从不生成大于中间值 P ，这样就避免了如果 P 重新presentable，通常需要较少的部门都溢出问题。此外，它计算所述模逆不仅为素数，但对于任何两个互质数。

 无符号长长invert_mod（无符号长一长，无符号长长P）{
    无符号长长新= 1，旧= ​​0，Q = P，R，H;
    INT POS = 0;
    而（a取代; 0）{
        R = Q％A;
        Q = Q / A;
        H = Q *新+旧的;
        旧=新;
        新= H;
        Q = A;
        一= R;
        POS = POS！;
    }
    返回POS？老：（P  - 旧）;
}
 

在code是稍长，而是一个优化的编译器应该利用每次迭代只有一个师把它编译成一个短回路。

I was thinking about an algorithm to solve the congruence ax = 1 mod p with p prime. I was thinking about using Fermat theorem. Since I know that

a ^ (p-1) = 1 mod p

and that

a ^ (p-1) = a * (a ^ (p-2))

It means that a ^ (p-2) mod p is the solution. Unfortunately this solution, although mathematically correct, isn't good for computer since for big primes I have to do a ^ (p-2) which is usually not calculable.

Which algorithm is good for computer science?

解决方案

since for big primes I have to do a ^ (p-2) which is usually not calculable.

You need modular exponentiation, so with the exponentiation by squaring mentioned by IVlad you only need Θ(log p) modular multiplications of numbers of size at most p-1. The intermediate results are bounded by p^2, so despite a^(p-2) not being calculable for large primes, (a ^ (p-2)) % p usually is. That method is simple to implement:

unsigned long long invert_mod(unsigned long long a, unsigned long long p) {
    unsigned long long ex = p-2, result = 1;
    while (ex > 0) {
        if (ex % 2 == 1) {
            result = (result*a) % p;
        }
        a = (a*a) % p;
        ex /= 2;
    }
    return result;
}

but has a few drawbacks. (p-1)^2 must be representable in the used type (not a problem [except for huge p] if arbitrary precision integers are used), or you get invalid results due to overflow, and it always uses at least log (p-2)/log 2 modular multiplications.

The extended Euclidean algorithm, as suggested by user448810, or equivalently the continued fraction method, never produces intermediate values larger than p, thus avoiding all overflow problems if p is representable, and usually needs fewer divisions. Additionally, it computes the modular inverse not only for primes, but for any two coprime numbers.

unsigned long long invert_mod(unsigned long long a, unsigned long long p) {
    unsigned long long new = 1, old = 0, q = p, r, h;
    int pos = 0;
    while (a > 0) {
        r = q%a;
        q = q/a;
        h = q*new + old;
        old = new;
        new = h;
        q = a;
        a = r;
        pos = !pos;
    }
    return pos ? old : (p - old);
}

The code is slightly longer, but an optimising compiler ought to compile it to a short loop using only one division per iteration.

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