일정한 모듈로 A 전력을 초래하는 곱셈 체인 2

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

문제

"곱셈 체인"을 제공하는 실용적인 알고리즘이 있습니까?

명확히하기 위해, 목표는 곱셈 변경을 생성하는 것입니다. 임의적이고 정확합니다 길이
길이 1의 곱셈 체인은 사소합니다.

"Multiplication Chain"은 코드에 사용되는 2 숫자 {start} 및 {multiplier}로 정의됩니다.

 Given a pointer to array of size [{count}]   // count is a parameter
 a = start;
 do 
 {
      a = a * multiplier;  // Really: a = (a * multiplier) MOD (power of 2
      *(pointer++) = a;   
 }
 while (a != {constant} )
 // Postcondition:  all {count} entries are filled.

세 가지 매개 변수를 취하는 루틴을 찾고 싶습니다.
1. 2의 힘
2. 중지 {constant}
3. {count} - 루프가 반복되는 횟수

루틴은 {start} 및 {multiplier}를 반환합니다.

이상적으로는 0의 {constant} 값이 유효해야합니다.

사소한 예 :

power of 2 = 256  
stopping constant = 7
number of times for the loop = 1  
returns {7,1}

사소한 예 : 

power of 2 = 256  
stopping constant = 1
number of times for the loop = 49
returns {25, 19}

주어진 2의 전력에 대한 최대 {count}는 상당히 작을 수 있습니다.
예를 들어, 2^4 (16)는 4의 카운트로 제한되는 것 같습니다.

도움이 되었습니까?

해결책

다음은 상수가 홀수 인 경우 사례의 시작 및 승수 값을 계산하는 방법입니다.

  1. m 모듈로 2^d의 순서가 적어도 계산되는 홀수 m (m = multiplier)을 찾으십시오. 나는 무작위로 추측하는 것보다 그러한 m을 찾는 다른 방법을 모르지만, 약간의 실험에서 1 ~ 2^d 사이의 홀수의 절반은 순서 2^(d-2)가 최대 인 것으로 보인다. (최대 12 세를 위해 노력했습니다.)

  2. x * m^count = 1 (mod 2^d)가되도록 x를 계산하고 start = x * constant (mod 2^d)를 설정하십시오.

이러한 X는 "확장 된 유클리드 알고리즘"으로 찾을 수 있습니다. 공통 구분이없는 A와 B가 주어지면 A * x + B * Y = 1이되도록 X와 Y를 제공합니다. 여기서 A = M^COUNT MOD 2^D 및 b = 2^d.

편집하다: 상수가 고르게 발생하면 2^k의 전력으로 나눌 수 있습니다. {start*2^k, multiplier}를 반환합니다.

다른 팁

다음 모듈 식 방정식에 대한 사소한 솔루션을 요구하고 있습니다.

s * m^N = C (mod 2^D)

어디

  • S는 시작 상수입니다
  • M은 승수입니다
  • n은 반복 횟수입니다 (문제에 의해 주어진)
  • C는 최종 상수입니다 (문제에 의해 주어진)
  • D는 2의 힘의 지수입니다 (문제에 의해 주어진)

살펴보십시오 오일러의 정리 숫자 이론에서.

임의의 경우 이상한 m (2^d로 프라임), 당신은

m^phi(2^D) = 1 (mod 2^D)

이와 같이

C * m^phi(2^D) = C (mod 2^D)

그리고 마지막으로

C * m^(phi(2^D)-N) * m^N = C (mod 2^D)

가져가다

s = C * m^(phi(2^D)-N)

그리고 당신은 끝났습니다. 그만큼 Euler의 PHI 기능 2의 힘은입니다 반 그 힘 2의 힘, 즉 :

phi(2^D) = 2^(D-1)

예시. 허락하다

  • n = 5
  • C = 3
  • 2^d = 16
  • Phi (16) = 8

임의로 M = 7 (홀수)을 선택하고 계산합니다.

3 * 7^(8-5) = 1029
s = 1029 mod 16 = 5

지금

s * m^N = 5 * 7^5 = 84035
84035 mod 16 = 3 == C

이것이 왜 요구 사항을 충족시키지 못합니까?

start = constant;
multiplier = 1;

업데이트 : 이제 루프 수가 입력 매개 변수 중 하나임을 알 수 있습니다. 이 문제는 특별한 경우 또는 적어도 관련된 것 같습니다. 불연속 로그 문제.

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