python3에서 특정 mod를 계산하는 함수

Question

과 같은 4 개의 큰 숫자 (최대 100 자리)가 m, y, n, r입니다. m,n과 r의 값을 알고 있으며 y 값을 찾고 싶습니다. 이 작업을 수행하려면 python3에 기능이 있습니까? 문제의 r의 값이 1이 보장되면

Answer 1

(gmpy2의 powmod 기능 등), 같은 gmpy 또는 gmpy2 모듈의 invert 기능을 일부 사용할 수 파이썬 기능이있다. 나는 당신이 원하는보다 일반적인 분수 함수를 찾지 못했습니다. 표준 반전 함수를 사용할 수는 있지만 실제로 수행 할 수있는 일부 분할을 허용하지 않습니다.

여기 내가 방금 작성한 기능이 sample code in Wikipedia에 기반하여 효율적으로 작성되었습니다. 전문 용어로 divideresidues(r, m, n)으로 전화하십시오.

def divideresidues(dividend, divisor, modulus): 
    """Return the dividend/divisor modulo modulus""" 
    r, newr = modulus, divisor 
    t, newt = 0, 1 
    while newr != 0: 
     quotient, remainder = divmod(r, newr) 
     r, newr = newr, remainder 
     t, newt = newt, t - quotient * newt 
    if t < 0: 
     t = t + modulus 
    quotient, remainder = divmod(dividend, r) 
    if remainder: 
     raise ValueError('Bad division in divideresidues()') 
    return t * quotient % modulus 

이 유클리드 알고리즘, divisor 및 modulus의 작은 자릿수, 즉 다섯 번 수와 동일 효율을 가지고있다. dividend의 크기는 기본적으로 부적합합니다. 귀하의 경우에는 최대 500 단계를 의미합니다. 이것은 큰 숫자처럼 들리지만 큰 숫자로 테스트 해 보았을 때 충분히 빠르며, 500 단계는 거의 발생하지 않습니다. 기본적으로 divisor 및 modulus이 피보나치 시퀀스의 연속 숫자 일 때입니다.