PGR21.com
- PGR21 관련된 질문 및 건의는 [건의 게시판]을 이용바랍니다.
- (2013년 3월 이전) 오래된 질문글은 [이전 질문 게시판]에 있습니다.
통합 규정을 준수해 주십시오. (2015.12.25.)
Date 2017/11/02 21:58:18
Name Patrick Jane
Subject [질문] a^p mod n을 구하는 빠른방법있을까요?
n은 31비트 수로 가정하고 a는 {2,3,4,.....,n-2} 이고 p는 n-1=2^r*p (p는 홀수) 입니다.

밀러라빈에서 z를 구하는과정에서 a^p mod n을 구해야하는데 수가 작으면 pow(a,p)%n을 통해서 구하는게 가능한데, n값이 앞에서 주어진데로 31비트정도되는
소수를 넣고 판별하려니 숫자가 너무 커서 제대로 구하지를 못하네요.

우선 구글링으로 검색한결과
int fastExpLimited(int base, int exp, int limit) {
        int result = base;
        while (exp > 1) {
                result *= result;
                if (exp % 2) {        
                        result *= base;
                }
                exp /= 2;
                result %= limit;
        }
        return result;
}
이런식으로 구한다는데, 실제 적용해보니 정상적으로 구하지를 못하네요. (6,5,21)을 넣으면 15를 리턴시켜주네요...6을 리턴시켜줘야하는데..
혹시 다른 방법이나 기발한 생각이있으신분 말씀해주시면 감사하겠습니다!


통합규정 1.3 이용안내 인용

"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.
법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
17/11/02 22:15
수정 아이콘
long long fexp(long long base, long long exp, long long mod) {
if (exp == 1) return base;
long long res = fexp(base, exp/2, mod);
res = res * res % mod;
if (exp % 2) res = res * base % mod;
return res;
}
이걸로 돌려보세요. 시간복잡도 O(log p) 니까 순식간에 나올겁니다.
회색사과
17/11/02 22:21
수정 아이콘
크으 그냥 롱롱 쓰면 될걸.. 그랬네요
Patrick Jane
17/11/02 22:24
수정 아이콘
허헣... 빠른답변 감사합니다!!
회색사과
17/11/02 22:21
수정 아이콘
그냥 드는 생각으로는... 로그 함수를 쓰건 pow를 쓰건...
a^q > n 이 되는 최소한의 q를 찾고, (a^q)/n 을 구한 다음에 [이걸 w라고 치고]
w^(p/q)*a^(p%q) % n 하면 어떨까요?
Patrick Jane
17/11/02 22:24
수정 아이콘
빠른답변 감사합니다!!
목록 삭게로! 맨위로
번호 제목 이름 날짜 조회
111324 [질문] 조이로드 타이어 괜찮나요? opxdwwnoaqewu5626 17/11/03 5626
111323 [질문] 낚시 초보자 출조지 강화도 vs 시화방조제 [5] 원스2258 17/11/03 2258
111322 [질문] 차 선택질문(아반떼 신차 vs lf소나타 중고) [35] 덮어쓰기10096 17/11/03 10096
111321 [질문] 33살의 인생고민입니다.(나이 들어서 이게 무슨 .. 흑흑) [14] 삭제됨4981 17/11/03 4981
111320 [질문] 조립한 새 컴퓨터에서 담배냄새가 나는데요. [13] 뜨또7075 17/11/03 7075
111319 [질문] 위키 사이트를 만들기 위해서 초보자가 참고할 만한 것이 있을까요? 목화씨내놔1480 17/11/03 1480
111318 [질문] 중고 맥북 관련 두번째 질문 드리겠습니다. [6] Lighthouse1931 17/11/03 1931
111317 [질문] 과민성대장증후군이신 분 계신가요? [20] Mindow4014 17/11/03 4014
111316 [질문] [맞선] 호텔에서 만나면 부담스럽지 않을까요? [11] 사진6450 17/11/03 6450
111315 [질문] [이사]냉장고,세탁기구매 관련 질문입니다 [5] WHIPLASH2034 17/11/03 2034
111314 [질문] 갤럭시탭S3 vs 갤럭시북12.0 어떤게 나은 선택일까요? [6] 개념은?3536 17/11/03 3536
111313 [질문] 전열기구 추천좀 해주세요 [2] 톰슨가젤연탄구이1536 17/11/03 1536
111312 [질문] 마카오 여행 관련 날씨, 맛집 추천 부탁드립니다. [3] 스윗앤솔티1691 17/11/03 1691
111310 [질문] 주말 인천공항 국제선 주차장 [4] 면역2044 17/11/03 2044
111309 [질문] 폰케이스 기스를 없애고 싶습니다. [4] Liberation3370 17/11/03 3370
111308 [질문] 플스4 구매했습니다. 타이틀 순서 질문입니다. [19] 나이스4157 17/11/03 4157
111307 [질문] (트와이스) 팬 싸인회는 어떤가요? [2] ComeAgain1278 17/11/03 1278
111306 [질문] 미러리스 카메라 첫구매 질문드립니다. [11] 워라밸3870 17/11/03 3870
111305 [질문] 핸드폰 구입 싸게사는법 있나요? [4] LubyH2081 17/11/03 2081
111304 [질문] 연말 혹은 클스마스 단체파티 미리 예약 하면 좋은 곳 추천 부탁드립니다 [4] Mindow1992 17/11/03 1992
111303 [질문] 주식 거래했는데 입금이 적게된 것 같습니다. [17] 코인괜히시작3769 17/11/03 3769
111302 [질문] 예전 pci슬롯이 달린 메인보드가 요즘에도 나오나요? [3] 정공법4438 17/11/03 4438
111301 [질문] 다음주에 1박2일 놀러갈만한곳 있을까요? [2] DAUM2238 17/11/03 2238
목록 이전 다음
댓글

+ : 최근 1시간내에 달린 댓글
+ : 최근 2시간내에 달린 댓글
맨 위로