로그인하고 있지 않습니다. 편집하면 당신의 IP 주소가 공개적으로 기록됩니다. 계정을 만들고 로그인하면 편집 시 사용자 이름만 보이며, 위키 이용에 여러 가지 편의가 주어집니다.스팸 방지 검사입니다. 이것을 입력하지 마세요!=== p-1 공격 === {{참고|폴라드 p-1 소인수분해법}} <math>p</math>를 직접 찾는게 어려우면, <math>p-1</math>를 이용하는 것이 어떨까? <math>p</math>가 큰 소수면, <math>p-1</math>은 필연적으로 짝수인 [[합성수]]이기 때문에 여러 작은 소인수들을 가질 것이고, 그 작은 소인수들을 전부 포함시킬 수 있다면 <math>p-1</math>을 찾을 수 있을 것이고, 이어서 <math>p</math>를 찾을 수 있을 것이다. 이 아이디어를 이용한게 <math>p-1</math> 공격이며, 자세한 방법은 다음과 같다. :1보다 큰 적당한 자연수 <math>a</math>를 고른다. 보통 2를 사용한다. 이제 상한 <math>B</math>를 정한다. 이제, <math>b\equiv a^{B!}\pmod n</math>을 다음과 같이 재귀적으로 계산한다. :<math>b_1\equiv a\pmod n</math>, <math>b_k\equiv{b_{k-1}}^k\pmod n</math> :그럼 <math>b_B\equiv b\pmod n</math>이 된다. 이제, <math>d=\gcd\left(b-1,n\right)</math>을 계산한다. 만약 <math>1< d< n</math>이면, <math>d</math>가 한 소인수이다. 원리는 [[페르마의 소정리]]와 <math>p-1</math>의 소인수에 있다. 만약 <math>p-1</math>이 작은 소인수만을 가지고 있으면, 적당히 큰 <math>B</math>에 대해 <math>\left(p-1\right)\mid B!</math>일 것이다 (<math>B!</math>은 <math>B</math>보다 작은 모든 소인수를 약수로 가지고 있다). 그러면 <math>B!=\left(p-1\right)k</math>로 쓸 수 있을 것이고, 페르마 소정리에 의해 <math>b\equiv a^{B!}\equiv a^{\left(p-1\right)k}\equiv\left(a^{p-1}\right)^k\equiv1^k\equiv1\pmod p</math>가 된다. 즉, <math>p\mid\left(b-1\right)</math>. 곧, <math>b-1</math>과 <math>n</math>은 <math>p</math>를 공약수로 가지게 되는 것이다. 여기서 주의할 점은 <math>B</math>가 너무 커서는 안 된다는 것이다. <math>B</math>가 너무 크게 되면 <math>p,q\mid\left(b-1\right)</math>이 되고, <math>\gcd\left(b-1,n\right)=n</math> 또는 1이 되어 아무런 정보도 얻지 못하기 때문. 구체적인 예시를 한 번 들어보자. :1357을 소인수 분해 하고 싶다고 하자. 상한을 <math>B=15</math>로 정하고, <math>b\equiv2^{B!}\pmod{1357}</math>을 구하면, 300이 나온다. 이제, 300-1=299와 1357의 최대공약수를 구하면, 23이 튀어나오고, 1357=23×59임을 쉽게 알 수 있다. 이는 23-1=22의 가장 큰 소인수가 11이고, 15!에 포함되기 때문에 가능한 결과이다. 만약 상한을 <math>B=30</math>으로 정했다면, <math>\gcd\left(b,1357\right)=1</math>이 되어 아무런 정보도 얻지 못한다. 그럼 어떤 소수를 써야 <math>p-1</math> 공격에서 자유로울까? 이는 <math>p-1</math>과 <math>q-1</math>이 둘 다 큰 소인수를 가지게 하는 것으로 해결된다. 여기서 큰 소인수의 기준은 약 '''40자리'''. 문제는 <math>p-1</math>이 40자리의 큰 소인수를 가지게 하면서 동시에 <math>p</math>를 소수로 만드는 방법일 것이다. 다행히 이 조건을 만족하는 소수 <math>p</math>는 무한히 많다. 이를 디레클레 정리라고 하며, 더 정확한 명제는 다음과 같다. :<math>a,d</math>를 서로소인 두 정수라 가정하자. 그럼, 수열 <math>\left\{a+nd\right\}_{n=0}^\infty</math>은 무한히 많은 소수를 포함한다. 여기서 <math>a=1</math>이고, <math>d</math>를 40자리의 어떤 큰 소수라 가정하면, 디레클레 정리에 의해 <math>1+nd</math> 꼴의 소수를 무한히 만들 수 있고, 그 중에서 100자리 정도 되는 소수를 찾기만 하면 된다. 그 소수를 <math>p</math>라 하면 <math>p-1=nd</math>이므로, <math>p-1</math>은 40자리의 큰 소인수를 가져 <math>p-1</math> 공격에서 안전해지게 된다. 물론 <math>q</math>도 비슷한 방식으로 생성해야 한다. 요약: 리브레 위키에서의 모든 기여는 크리에이티브 커먼즈 저작자표시-동일조건변경허락 3.0 라이선스로 배포됩니다(자세한 내용에 대해서는 리브레 위키:저작권 문서를 읽어주세요). 만약 여기에 동의하지 않는다면 문서를 저장하지 말아 주세요. 글이 직접 작성되었거나 호환되는 라이선스인지 확인해주세요. 리그베다 위키, 나무위키, 오리위키, 구스위키, 디시위키 및 CCL 미적용 사이트 등에서 글을 가져오실 때는 본인이 문서의 유일한 기여자여야 하고, 만약 본인이 문서의 유일한 기여자라는 증거가 없다면 그 문서는 불시에 삭제될 수 있습니다. 취소 편집 도움말 (새 창에서 열림) | () [] [[]] {{}} {{{}}} · <!-- --> · [[분류:]] · [[파일:]] · [[미디어:]] · #넘겨주기 [[]] · {{ㅊ|}} · <onlyinclude></onlyinclude> · <includeonly></includeonly> · <noinclude></noinclude> · <br /> · <ref></ref> · {{각주}} · {|class="wikitable" · |- · rowspan=""| · colspan=""| · |} {{lang|}} · {{llang||}} · {{인용문|}} · {{인용문2|}} · {{유튜브|}} · {{다음팟|}} · {{니코|}} · {{토막글}} {{삭제|}} · {{특정판삭제|}}(이유를 적지 않을 경우 기각될 가능성이 높습니다. 반드시 이유를 적어주세요.) {{#expr:}} · {{#if:}} · {{#ifeq:}} · {{#iferror:}} · {{#ifexist:}} · {{#switch:}} · {{#time:}} · {{#timel:}} · {{#titleparts:}} __NOTOC__ · __FORCETOC__ · __TOC__ · {{PAGENAME}} · {{SITENAME}} · {{localurl:}} · {{fullurl:}} · {{ns:}} –(대시) ‘’(작은따옴표) “”(큰따옴표) ·(가운뎃점) …(말줄임표) ‽(물음느낌표) 〈〉(홑화살괄호) 《》(겹화살괄호) ± − × ÷ ≈ ≠ ∓ ≤ ≥ ∞ ¬ ¹ ² ³ ⁿ ¼ ½ ¾ § € £ ₩ ¥ ¢ † ‡ • ← → ↔ ‰ °C µ(마이크로) Å °(도) ′(분) ″(초) Α α Β β Γ γ Δ δ Ε ε Ζ ζ Η η Θ θ Ι ι Κ κ Λ λ Μ μ(뮤) Ν ν Ξ ξ Ο ο Π π Ρ ρ Σ σ ς Τ τ Υ υ Φ φ Χ χ Ψ ψ Ω ω · Ά ά Έ έ Ή ή Ί ί Ό ό Ύ ύ Ώ ώ · Ϊ ϊ Ϋ ϋ · ΐ ΰ Æ æ Đ(D with stroke) đ Ð(eth) ð ı Ł ł Ø ø Œ œ ß Þ þ · Á á Ć ć É é Í í Ĺ ĺ Ḿ ḿ Ń ń Ó ó Ŕ ŕ Ś ś Ú ú Ý ý Ź ź · À à È è Ì ì Ǹ ǹ Ò ò Ù ù · İ Ż ż ·  â Ĉ ĉ Ê ê Ĝ ĝ Ĥ ĥ Î î Ĵ ĵ Ô ô Ŝ ŝ Û û · Ä ä Ë ë Ï ï Ö ö Ü ü Ÿ ÿ · ǘ ǜ ǚ ǖ · caron/háček: Ǎ ǎ Č č Ď ď Ě ě Ǐ ǐ Ľ ľ Ň ň Ǒ ǒ Ř ř Š š Ť ť Ǔ ǔ Ž ž · breve: Ă ă Ğ ğ Ŏ ŏ Ŭ ŭ · Ā ā Ē ē Ī ī Ō ō Ū ū · à ã Ñ ñ Õ õ · Å å Ů ů · Ą ą Ę ę · Ç ç Ş ş Ţ ţ · Ő ő Ű ű · Ș ș Ț ț