finding x and p when we have successive large powers of an integer x, with modulo of prime p

 

 

그냥 심심해서

link : https://math.stackexchange.com/questions/1952453/finding-an-integer-x-and-a-3-digit-prime-p-that-solves-the-problem

Finding an integer $x$ and a 3-digit prime $p$ that solves the problem

 

 

353,46,618,30,877,235,98,24,107,188,673

다음 값은 mod p에 대한 x의 거듭제곱이다.

이 상황에서 x와 p를 구할 수 있을까?

 

결론적으로 가능하다. 재미있는 수학시간^-^..

식을 2개만 가져와 작성하자면 다음과 같다.

$$ x^n ≡ 353 (mod p) $$

$$ x^{n+1} ≡ 46 (mod p) $$

저 두 식을 조금만 치환해보면, 다음같은 수식도 당연히 말이 되겠죠?

$$ x^{n+1} ≡ 46 (mod p) $$ $$ 353 * x ≡ 46 (mod p) $$

 

추가적으로 46x ≡ 618... and so on!

그 중에서 식을 2개만 가져와봅시당

 

 98x≡24 (mod p)  => 49x ≡ 12 (mod p) (2, p is relatively prime)

24x≡107 (mod p)

 

차례로 (1), (2)라고 할 때, 

(1) - (2)*2 진행

 

x ≡ -202 (mod p)

 

자 거의다 왔습니다

여기서 p만 구하면 구할 수 있죠?

한 가지 알 수 있는 것은 문제 자체를 통해 3자리수 소수인 것을 알 수 있고, 최소 877 초과인 것을 알 수 있습니다.

이걸 기억하면서, (2)번의 식에 대입해볼게요.

 

24(-202)≡107 (mod p)

즉, 24*(202) + 107 = p * n (n은 자연수)

저는 877 초과, 1000미만인 소수 중 저 값을 나눌 수 있는 값이 있는지 확인해보도록 하겠습니다.

def get_prime(lower, upper):
    result = []
    for num in range(lower, upper + 1):
        # all prime numbers are greater than 1
        if num > 1:
            for i in range(2, num):
                if (num % i) == 0:
                    break
            else:
                result.append(num)
    
    return result

if __name__ == "__main__":
    eq = 24*(202) + 107
    prime_list = get_prime(877, 1000)
    print(f"prime between 877~1000: {prime_list}")
    for i in prime_list:
        if eq % i == 0:
            print(f"[*] found prime : {i}")

굳굳

즉 p는 991이고, x는 789네요

 

담에는 이런거 할때 패드로 해야겠다

끝~