파이썬의 모듈러 곱셈 역함수
일부 표준 파이썬 모듈에는 숫자의 모듈식 곱셈 역수를 계산하는 함수가 포함되어 있습니까?y = invmod(x, p)
할 정도로x*y == 1 (mod p)
구글은 이것에 대해 어떤 좋은 힌트도 주지 않는 것 같습니다.
물론, 확장 유클리드 알고리즘의 집에서 만든 10-라이너를 생각해 낼 수 있지만, 왜 바퀴를 재창조하는지에 대해서는 생각해 낼 수 있습니다.
예를 들어, Java의BigInteger
가지다modInverse
방법.파이썬에도 비슷한 게 있지 않나요?
파이썬 3.8+
y = pow(x, -1, p)
Python 3.7 이전 버전
아마도 누군가는 이것이 유용하다고 생각할 것입니다(위키북스에서).
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m
만약 당신의 계수가 소수라면 (당신은 그것을 소수라고 부릅니다.p
) 그런 다음 다음을 간단히 계산할 수 있습니다.
y = x**(p-2) mod p # Pseudocode
또는 Python에서 적절한:
y = pow(x, p-2, p)
파이썬에서 몇 가지 숫자 이론 기능을 구현한 사람이 있습니다. http://www.math.umbc.edu/ ~campbell/Computers/Python/numbthy.html
다음은 프롬프트에서 수행된 예입니다.
m = 1000000007
x = 1234567
y = pow(x,m-2,m)
y
989145189L
x*y
1221166008548163L
x*y % m
1L
또한 gmpy 모듈을 살펴볼 수도 있습니다.Python과 GMP 다중 정밀 라이브러리 사이의 인터페이스입니다.gmpy는 필요한 작업을 정확히 수행하는 반전 기능을 제공합니다.
>>> import gmpy
>>> gmpy.invert(1234567, 1000000007)
mpz(989145189)
업데이트된 답변
@hyh에 의해 언급된 바와 같이,gmpy.invert()
역수가 없는 경우 0을 반환합니다.그것은 GMP의 행동과 일치합니다.mpz_invert()
기능. gmpy.divm(a, b, m)
에 대한 일반적인 솔루션을 제공합니다.a=bx (mod m)
.
>>> gmpy.divm(1, 1234567, 1000000007)
mpz(989145189)
>>> gmpy.divm(1, 0, 5)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ZeroDivisionError: not invertible
>>> gmpy.divm(1, 4, 8)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ZeroDivisionError: not invertible
>>> gmpy.divm(1, 4, 9)
mpz(7)
divm()
다음과 같은 경우 솔루션을 반환합니다.gcd(b,m) == 1
곱셈 역이 존재하지 않는 경우 예외를 발생시킵니다.
고지 사항:저는 현재 gmpy 라이브러리의 관리자입니다.
업데이트된 답변 2
gmpy2는 이제 역이 존재하지 않을 때 예외를 적절하게 발생시킵니다.
>>> import gmpy2
>>> gmpy2.invert(0,5)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ZeroDivisionError: invert() no inverse exists
3.8 피톤스 pow() 함수는 계수와 음의 정수를 취할 수 있습니다.여기 보세요.사용 방법에 대한 그들의 사례는.
>>> pow(38, -1, 97)
23
>>> 23 * 38 % 97 == 1
True
다음은 코드파이트를 위한 하나의 라이너입니다. 이것은 가장 짧은 솔루션 중 하나입니다.
MMI = lambda A, n,s=1,t=0,N=0: (n < 2 and t%N or MMI(n, A%n, t, s-A//n*t, N or n),-1)[n<1]
돌아올 것입니다.-1
한다면A
에 승법 역수가 없습니다.n
.
용도:
MMI(23, 99) # returns 56
MMI(18, 24) # return -1
솔루션은 확장 유클리드 알고리즘을 사용합니다.
심볼릭 수학을 위한 파이썬 모듈인 Sympy는 자신만의 모듈식 역함수를 구현하고 싶지 않은 경우(또는 Sympy를 이미 사용하고 있는 경우) 내장되어 있습니다.
from sympy import mod_inverse
mod_inverse(11, 35) # returns 16
mod_inverse(15, 35) # raises ValueError: 'inverse of 15 (mod 35) does not exist'
Sympy 웹 사이트에는 문서화되어 있지 않은 것 같습니다만, 다음 문서 문자열이 있습니다.Github의 Sympy mod_inverse docstring
여기 외부 라이브러리를 사용하지 않고 이를 수행하는 간결한 1-라이너가 있습니다.
# Given 0<a<b, returns the unique c such that 0<c<b and a*c == gcd(a,b) (mod b).
# In particular, if a,b are relatively prime, returns the inverse of a modulo b.
def invmod(a,b): return 0 if a==0 else 1 if b%a==0 else b - invmod(b%a,a)*b//a
이것은 단지 단일 관심 계수만 반환하도록 간소화된 egcd입니다.
이 스레드에서 다른 솔루션을 사용해보고 결국에는 다음과 같은 솔루션을 사용합니다.
def egcd(a, b):
lastremainder, remainder = abs(a), abs(b)
x, lastx, y, lasty = 0, 1, 1, 0
while remainder:
lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
x, lastx = lastx - quotient*x, x
y, lasty = lasty - quotient*y, y
return lastremainder, lastx * (-1 if a < 0 else 1), lasty * (-1 if b < 0 else 1)
def modinv(a, m):
g, x, y = self.egcd(a, m)
if g != 1:
raise ValueError('modinv for {} does not exist'.format(a))
return x % m
여기 제 코드가 있어요, 엉성할 수도 있지만 어쨌든 저한테는 잘 맞는 것 같아요.
# a is the number you want the inverse for
# b is the modulus
def mod_inverse(a, b):
r = -1
B = b
A = a
eq_set = []
full_set = []
mod_set = []
#euclid's algorithm
while r!=1 and r!=0:
r = b%a
q = b//a
eq_set = [r, b, a, q*-1]
b = a
a = r
full_set.append(eq_set)
for i in range(0, 4):
mod_set.append(full_set[-1][i])
mod_set.insert(2, 1)
counter = 0
#extended euclid's algorithm
for i in range(1, len(full_set)):
if counter%2 == 0:
mod_set[2] = full_set[-1*(i+1)][3]*mod_set[4]+mod_set[2]
mod_set[3] = full_set[-1*(i+1)][1]
elif counter%2 != 0:
mod_set[4] = full_set[-1*(i+1)][3]*mod_set[2]+mod_set[4]
mod_set[1] = full_set[-1*(i+1)][1]
counter += 1
if mod_set[3] == B:
return mod_set[2]%B
return mod_set[4]%B
위의 코드는 python3에서 실행되지 않으며 GCD 변형에 비해 효율성이 떨어집니다.하지만 이 코드는 매우 투명합니다.이것이 계기가 되어 좀 더 콤팩트한 버전을 만들게 되었습니다.
def imod(a, n):
c = 1
while (c % a > 0):
c += n
return c // a
cpython 구현 소스 코드에서:
def invmod(a, n):
b, c = 1, 0
while n:
q, r = divmod(a, n)
a, b, c, n = n, c, b - q*c, r
# at this point a is the gcd of the original inputs
if a == 1:
return b
raise ValueError("Not invertible")
이 코드 위의 코멘트에 따르면, 작은 음의 값을 반환할 수 있으므로, b를 반환하기 전에 음의 경우 잠재적으로 확인하고 음의 경우 n을 추가할 수 있습니다.
모듈식 승법 역수를 파악하려면 다음과 같이 확장 유클리드 알고리즘을 사용하는 것이 좋습니다.
def multiplicative_inverse(a, b):
origA = a
X = 0
prevX = 1
Y = 1
prevY = 0
while b != 0:
temp = b
quotient = a/b
b = a%b
a = temp
temp = X
a = prevX - quotient * X
prevX = temp
temp = Y
Y = prevY - quotient * Y
prevY = temp
return origA + prevY
음, 여기 당신이 쉽게 파이썬으로 변환할 수 있는 C의 기능이 있습니다.아래의 c 함수에서 확장 유클리드 알고리즘은 역 모드를 계산하는 데 사용됩니다.
int imod(int a,int n){
int c,i=1;
while(1){
c = n * i + 1;
if(c%a==0){
c = c/a;
break;
}
i++;
}
return c;}
Python 함수로 변환
def imod(a,n):
i=1
while True:
c = n * i + 1;
if(c%a==0):
c = c/a
break;
i = i+1
return c
위의 C 함수에 대한 참조는 두 개의 상대적 소수의 모듈식 곱셈 역을 찾기 위해 다음 링크 C 프로그램에서 가져옵니다.
언급URL : https://stackoverflow.com/questions/4798654/modular-multiplicative-inverse-function-in-python
'it-source' 카테고리의 다른 글
ASP.NET 응용 프로그램을 디버깅하는 동안 Fiddler에서 로컬 호스트 트래픽을 표시하는 방법은 무엇입니까? (0) | 2023.06.30 |
---|---|
루비 배열의 마지막 요소를 제외한 모든 요소 (0) | 2023.06.30 |
Oracle 11g 데이터베이스에 원격으로 연결하는 방법 (0) | 2023.06.30 |
어떤 프로그램이 주어진 파일에 C 배열을 생성합니까? (0) | 2023.06.30 |
소스에 X개의 요소가 있지만 대상에는 1개만 허용됩니다. (0) | 2023.06.30 |