정수 내의 그룹 순서에 관한 암호 이론의 그룹 이론 Z * p

Question

나는 그룹 이론에 깊이 빠져 들었고, 나는 암호화 클래스에 대해 약간 분실되었다. 기본적으로 실제 내가

이것은에서의 순서를 반환해야합니다 (모든 A, 소수, P-1의 요소 목록), 자바에

순서를 구현해야 그룹 Z * p, 여기서 f는 p-1의 소수 요소 목록입니다. f가 중복을 포함 할 때 당신의 방법이 작동하는지 확인하십시오. 예를 들어, p는 = 17 여기

내가 지금까지 (내 노트 내에서 단계에서 촬영) 한 어떤 경우

public static BigInteger order(BigInteger p, List<BigInteger> f, BigInteger a){ 
    //Algorithm starts like this 
    //Start by setting t equal to p-1 i.e t= p1 p2...pn 
    BigInteger t = p.subtract(BigInteger.ONE); 
    for(BigInteger pi : f){ 
     //test if a^t1 = 1 mod p where t1 = t/pi 
     BigInteger t1 = t.divide(pi); 

     if(Practical5ExponentiationModMSquareAndMultiply.expm(p, a, t1).equals(BigInteger.ONE)){ 
      t = t1; 
      System.out.println("t after mod = "+t); 
      System.out.println("pi after mod = "+pi); 
     } 
    }  
    return t; 

} 

가 주요 요인 (F)의 목록이 다른 방법에 의해 생성 된 후 전달을 고려 in

내가 가지고있는 메모는 이해하기가 어렵고 어떤 것이 실제로 돌아와야 하는지를 말할 수 있는지 궁금해하고 있습니다. 그것은 당신이 가장 적은 수의 o 등이 a^o == 1 (mod p), 즉 p이 a^o - 1을 나누는 작은 o 같은 것을 찾고있는

Answer 1

내 더 practicals에 도움이 될 수로 또한 u는 나에게 그룹 이론의이 조각의 가능성 이해를 줄 수 있습니다.

여러분이 필요로하는 그룹 이론 결과는 정수 mod p의 곱셈 그룹이 차수 p-1의 순환이라는 것입니다.

가

• 순서가 oa^o == 1 (mod p)
• 순서 o 앞의 조건을 만족하는 최소 개수 p-1 만족 분할이는 것을 의미한다.

따라서 당신은 p-1의 주요 요인을 고려 반복이 p이 a^n - 1 분할이 더 이상 사실이 없을 때까지 그들에 의해 p-1 나누어 순서를 찾을 수 있습니다.

예 1 : p = 13, P-1 = 3 * 2 * 2, A = P 5.

= 2^5 (12/2) == 12 MOD (13) 따라서 순서대로 2를 잃을 수는 없습니다.

p = 3, 5^(12/3) == 1 (mod 13) 인 경우 순서대로 3을 잃을 수 있습니다.

예 2 : p = 17, P-1 =

따라서 순서는 2 × 2 = 4

하면 (p가 = 17) 또 다른 예시적인 사건에 주어진 예는 2 * 2 * 2 * 2, A = 9

^(16/2) == 1 MOD (17)는 잃게 할 수 있도록 상기 제 2

9 ^ (16/4) = = 16 (mod 17)이므로 두 번째 2를 잃을 수 없으며 검색을 중지 할 수 있습니다.

따라서 순서는 알고리즘을 참조하기 * 2 * 2 = 8

2 희망이 충분해야한다.