프라임 순서의 순환 그룹에서 요소 찾기

요소 a가 제너레이터의 특정주기 그룹 G에 속하는지 확인하려면 어떻게합니까? 지금은 단순히 그룹의 모든 요소를 생성하고 컨테이너에 저장 한 다음 요소가 해당 요소에 있는지 확인합니다. a 요소가 그룹에있는 경우 단순히 확인프라임 순서의 순환 그룹에서 요소 찾기

public HashSet<BigInteger> group_elements(BigInteger g, BigInteger q) { 

    HashSet<BigInteger> group = new HashSet<BigInteger>(); 

    BigInteger element = modPow(g,ONE,q); 

    for (int i = 2; !group.contains(element); i++) { 
     group.add(element); 
     element = modPow(g, BigInteger.valueOf(i), q); 
    } 

    return group; 

}

및보고 :

if (group.contains(num)) { ... }

당신이 언어를 볼 수 있듯이이 코드 메신저는 현재 그룹의 모든 요소를 생성하기 위해 사용하고 Java입니다.

출처

2010-03-25 Martin Andersson

당신이 사용하고있는 언어 ** 당신이 시도한 것을 보여주십시오 ** –

일반적으로 코드를 작성하는 것이 아니라 프로그래밍이 잘된 것 같습니다. 그것은 당신을 붙들어 놓은 문제의 수학입니다. –

잠깐, 뭐라구? 귀하의 그룹은 q의 곱셈 그룹입니다. 맞습니까? 따라서 q로 나눌 수없는 정수는 그 그룹의 원소입니다. [또는 코드가하는 것처럼 각 잔류 클래스에 대한 담당자를 선택하는 경우 그룹은 {1, ..., q-1}입니다.] 어느 쪽이든 너무 많이 작성할 필요는 없습니다. 암호. :-) – ShreevatsaR

discrete logarithm 문제와 algorithms을 확인하십시오.

출처

2010-03-25 19:37:12 starblue

아마도 그룹의 모양에 대한 정보가 더있을 수 있습니다.

g가 생성 한 그룹 G의 순서를 알고 q가 소수 일 경우 (G의 순서는 소수이지만 q는 아님), 요소 x가 들어 있는지 확인할 수 있습니다 테스트에 의한 G

1 = x ^{ord (G)} mod q.

q가 소수가 아닌 경우이 테스트는 작동하지 않습니다. 카운터 예제는 g = 22, q = 91, x = 53입니다. 여기에서 g는 요소가 {1, 22, 29} 인 하위 그룹을 생성합니다. x는 또한 순서 3을 갖지만 g에 의해 생성 된 하위 그룹의 요소는 아닙니다.

출처

2010-03-26 11:36:39 abc

프라임 순서의 순환 그룹에서 요소 찾기

답변

관련 문제