[질문] 이산로그 질문

[secre(1.216)]

a^x = b (mod p)에서

a와 p가 서로소가 아니라면 ax = 1 (mod p)를 만족하는

x가 존재하지 않는데 그럼 이때는 곱셈역원이 없으니

baby step giant step 못 쓰는거임?

a와 p가 서로소가 아니라도 x는 존재할 수 있는데 다른 방법 써야하는거임?

- dc official App

[대학원오지마세요(publfl)]

애초에 그런 문제때문에 p를 소수로 가정하지 않나? 게다가 p가 소수여도 a가 원시근이 아니면 p와 a가 서로소여도 x 존재 안할 수 있음. 그래서 이산로그는 p가 소수고 a가 원시근이라 가정할거야

[secre(1.216)]

baby step giant step은 결국 서로소가 아니면 못쓴다는거지? 내가 저 방법만 배워서 설명에 꼭 a와 p가 서로소라는 조건이 있던데 왜그런지 궁금해가지구 - dc App

[대학원오지마세요(publfl)]

2^x = 3 mod 7을 만족하는 x는 없음. 2와 7이 서로소임에도 불구하고. 뭔가 이상한곳에서 본것 같은데 원시근 관련 내용 한번 흝어봐

[secre(1.216)]

이산로그 존재성에 대해서는 바로 판단하는 조건이 없다는건 아는데 baby step giant step을 a와 p가 서로소가 아닐 때 사용할 수 없는게 맞는지 확인하고 싶었음 일단 조건 자체가 그렇게 안준다는거고 원시근을 좀 봐야겠네 - dc App

[익명(121.172)]

p는 너무 소수같으니까 m이라고 하자. a^x = b (mod m)에서 소수 p에 대해 m = k * p^e 꼴이고 a가 p의 배수라고 하면, b가 p^e의 배수가 아니면 x가 결정됨 왜냐하면 a를 너무 많이 곱하면 안 되니까. 만약에 b가 p^e의 배수라면 그냥 x가 적당히 크면 되니까 a^x = b (mod k)를 구한 다음 x가 너무 작으면 a^x의 주기를 고려해서 적당히 나중 거를 고르면 됨

[익명(121.172)]

겹치는 소수가 여러 개 있을 때도 x의 하한이 여러 개 생기는 거 뿐이니까 비슷하게 하면 됨

[익명(121.172)]

p와 a가 서로소인데도 x가 존재 안 할 수 있는데 그럴 경우는 정확한 범위는 따져봐야 하는데 x가 될 수 있는 최소값이 phi(m)보다 작은가 하는 식으로 범위가 나오기 때문에 그 범위를 다 커버할 수 있도록 baby step giant step 을 돌려서 답이 안 나오면 없는 거고

[secre(1.216)]

고맙다 태식아 원시근 먼저 이해하고 천천히 읽어볼께 - dc App

[익명(121.172)]

결론은 그러니까 할 수 있는데 문제가 많이 더러워짐 결국 서로소일 때가 가장 관심있는 거고 서로소 아닐 때는 서로소일 때로 환원한 다음 뭔가 처리를 하는 느낌