mod 표현식에서 변수 값을 어떻게 찾습니까?

StackOverflow https://stackoverflow.com/questions/1812460

  •  06-07-2019
  •  | 
  •  

문제

9 = 2^x 모드 11

X는 무엇이며 어떻게 x를 찾습니까?

RSA 알고리즘에서 일반 텍스트를 찾는 것과 관련이 있으며 C 프로그램을 작성하고 있습니다.

도움이 되었습니까?

해결책

답은 모든 정수 i의 경우 6 + 10i입니다.

작은 계수를위한 솔루션을 얻는 간단한 방법은 x의 모든 값을 반복하는 것입니다. 솔루션이 존재하는 경우 첫 번째 솔루션을 찾으려면 0과 10 (= 11-1) 사이에서만 확인하면됩니다.

x = 0
while x < 50:
    if 9 == 2**x % 11:
         print x
    x += 1

산출:

6
16
26
36
46

분명히 계수가 크면 시간이 오래 걸릴 것입니다.

자세한 정보는 다음과 같습니다 불연속 로그 페이지. 메모:

일반 이산 로그를 계산하기위한 효율적인 고전 알고리즘이 알려져 있지 않습니다. LOGBG는 알려져 있습니다. 순진한 알고리즘은 원하는 G가 발견 될 때까지 B를 더 높고 더 높은 전력 K로 올리는 것입니다. 이것은 때때로 시험 곱셈이라고합니다. 이 알고리즘은 그룹 g 크기의 실행 시간 선형이어야하므로 그룹 크기의 숫자 수를 지수해야합니다.

모듈 식 지출을 쉽게 반전 시키면 암호화 프리미티브가 좋지 않습니다.

다른 팁

분명히, 2^n 모드 11의 시퀀스는 주기적이다.

2^0 모드 11 = 1
2^1 모드 11 = 2
2^2 모드 11 = 4
2^3 모드 11 = 8
2^4 모드 11 = 5
2^5 모드 11 = 10
2^6 모드 11 = 9
2^7 모드 11 = 7
2^8 모드 11 = 3
2^9 모드 11 = 6
2^10 모드 11 = 1
2^11 모드 11 = 2

따라서 사이클 길이는 10입니다.

2^n mod 11 = 9의 경우 n = 6+10*m 여기서 m은 정수입니다.

나는 그것이 해결할 수 있다고 생각합니다 모듈 식 산술. 또 다른 방법은 9 = 2^x를 F에서 계산하는 것입니다.11 (Z/11Z), 그러나 그것은 모듈 식 산술의 일부이기도합니다.

또 다른 솔루션 (하나의 솔루션 만 찾을 수있는 곳)은 방정식을 수치 적으로 해결하는 것입니다. 이는 C 프로그램에서 더 쉽습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top