メルセンヌ眶 - Security Akademeia

ⅲサイト
附哼避枉している客¨23

ⅲこのペ〖ジ
圭纷避枉荚眶¨4408
海泣の避枉荚眶¨4
候泣の避枉荚眶¨2

ⅲメニュ〖
úインフォメ〖ション
ū碰サイトの蝗い数

ⅲメインコンテンツ
úコンピュ〖タ怪郝
úピッキング怪郝
ú芭规怪郝
ú眶池怪郝
ú步池怪郝
ú栏湿池怪郝
ú恕池怪郝
ú板池怪郝
ú沸蹦池怪郝
ú沸貉池怪郝
ú看妄池怪郝
ú家柴池怪郝
ú悟凰池怪郝
ú暖池怪郝
ūその戮の怪郝

ⅲサブコンテンツ
ú螟今のサポ〖トペ〖ジ
ú桂梦旺悟
ú瘦瓷技
ú矢汤浩氟
úリンク
ú供侯ˇ悸赋
ū穷湿篡

ⅲ瓷妄客の攫鼠
úプロフィ〖ル
úTwitter
ú粕今メ〖タ〖
úあにみた—
úmixi
úはてなブックマ〖ク
úXbox Live
ūyoutube

ⅲ恍隋サイト
úハッカ〖畸灰舶
ú获呈啼玛末里
úアカデメイアシティ
úSAS
ūWizard Bible

ⅲ瓷妄客脱
ú肋年恃构旺悟
úメモ
úMenuBar
úRightBar
úコラム
úお传め徊雇矢弗
ūアクセス豺老

このペ〖ジを崔むはてなブックマ〖ク

このペ〖ジを崔むlivedoor クリップ

誊肌 †

誊肌
メルセンヌ燎眶
メルセンヌ眶の燎傍眶尸豺
徊雇矢弗

メルセンヌ燎眶 †

[年盗]p⒑Nとし、 $M_p=2^p~-~1$ の妨の眶をメルセンヌ眶という。

[年盗]Mpが燎眶の眷圭はメルセンヌ燎眶、そうではない眷圭はメルセンヌ圭喇眶という。

[年妄]Mpが∈メルセンヌ∷燎眶のときは、pも燎眶になる。

[沮汤]pが圭喇眶と簿年する∈秦妄恕∷。

　p=abとすると、Mpは肌のように鸥倡できる。

$M_p$
$=M_{ab}$
$=2^{ab}~-~1$
$=(2^a~-1)~\{~2^{a(b-1)~+~2^{a(b-2)}+~\cdots~+~1~\}$

　a′1、b′1ならば、宝收の尉傍眶は1よりも络きい。よって、Mpは圭喇眶である。これは谭解。　ⅱ

　この年妄の嫡は涩ずしも喇り惟たない。つまり、pが燎眶であっても、Mp=2p-1が燎眶とは嘎らない。

p	メルセンヌ眶Mp	燎眶か容か
2	3	燎眶
3	7	燎眶
5		燎眶
7		燎眶
11	2047=23∵89	燎眶でない
13		燎眶
17		燎眶
19		燎眶
23		燎眶でない

p=2,3,5,7に滦するMpが燎眶になることは、概くから梦られていた。
p=13,16,19に滦するMpが燎眶になることは、17坤氮介片に澄千された。
1644钳にメルセンヌはp=2,3,5,7,13,17,19に裁えて、さらにp=31,67,127,257に滦するMpが燎眶であり、p°257である戮の极脸眶pに滦するMpは圭喇眶であると肩磨した。
- 1坤氮笆惧沸った1750钳に、オイラ〖によりp=31に滦するMpが圭喇眶であることを券斧した。
- 1903钳にアメリカのコロンビア络池の眶池荚フランクˇコ〖ルはM67が圭喇眶であることを券斧した。
附哼、p=67,257に滦するメルセンヌの肩磨は疙りで、さらにp=61,89,107の眷圭は燎眶であることがわかっている。
リュカはメルセンヌ眶が燎眶かどうかを冉年するアルゴリズムを券斧した。
- 20坤氮に掐ってからDˇNˇレ〖マ〖によってそのアルゴリズムは猖紊された。

[踏豺疯啼玛]
(1)痰嘎に驴くのメルセンヌ燎眶があるか々
(2)痰嘎に驴くのメルセンヌ圭喇眶があるか々

メルセンヌ眶の燎傍眶尸豺 †

　メルセンヌ眶は2n-1の妨になっている。nが饿眶2kの眷圭は、肌のように鸥倡できる。

$a^n~-~1=a^{2k}~-~1=(a^k~-~1)(a^k~+~1)$

　よって、この眷圭の燎傍眶尸豺をするためには、ak+1の燎傍灰を梦る涩妥がある。

　そこで、腊眶a,pを疯めておき、p|am+1となるmがあるかどうかを雇弧する。

[年妄]p′2と簿年する。
そのとき、p|am+1となるような腊眶m∈′0∷があれば、p|an-1となるような呵井の腊眶n∈′0∷は饿眶である。
嫡に、p|an-1となる呵井のnが饿眶ならば、p|am+1となるような腊眶mはn/2に霹しい。

[沮汤]

[1]⑼を绩す。

p|am+1
$a^m~\equiv~-1~\,~\pmod{p}$ 　(*)

そのようなmを1つ疯めておく。

$a^n~\equiv~1~\,~\pmod{p}$ となるような呵井のnの认跋を拇べる。

(*)の尉收を2捐すると、肌が喇り惟つ。

$(a^m)^2~\equiv~(-1)^2~\,~\pmod{p}$
$a^{2m}~\equiv~1~\,~\pmod{p}$

よって、nは呵井としているので、n″2mが喇り惟つ。

ここで、nを瘩眶と簿年する。

すると、n°2mである。

また、2mをnで充ったときの睛をq、途りをrとすると、肌が喇り惟つ。

$2m=qn+r,~0~\le~r~<~n$

すると、肌のように鸥倡できる。

$1$
$\equiv~a^{2m}$
$=~a^{qn+r}$
$=~(a^n)^q~a^r$
$\equiv~a^r$ 　∈㈣ $a^n~\equiv~1~\,~\pmod{p}$ ∷

ここで、nの呵井拉より、r=0でなければならない。
そうでないと、nより井さいべきr′0に滦して、 $a^r~\equiv~1~\,~\pmod{p}$ となって谭解するため。

よって、2m=qnが喇り惟つ。

なお、amは肌のように鸥倡できるが、p′2としたので、これは(*)と谭解する。

$a^m$
$=~(a^n)^{\frac{m}{n}}$ 　∈㈣nが瘩眶と簿年したので、nはmを充り磊る∷
$\equiv~1^{\frac{m}{n}}$ 　∈㈣ $a^n~\equiv~1~\,~\pmod{p}$ ∷
$=~1$

ゆえに、nは饿眶である。

[2]を绩す。

p|an-1となる呵井のnが饿眶ならば、n=2kとおく。

$a^n~-1~=~a^{2k}~-1~=~(a^k~-1)(a^k~+1)$

ここで、 $a^n~-~1\equiv~0~\,~\pmod{p}$ かつ $a^k~-~1~\not{\equiv}~0~\,~\pmod{p}$ ∈k°nとnの呵井拉より∷であるため、 $a^k~+~1~\equiv~0~\,~\pmod{p}$ である。

k=mとなる。　???

よって、n=2k=2mである。篓ち、m=n/2が喇り惟つ。　ⅱ

[输怪]この年妄において、p′2という簿年は涩妥である。

もし、p=2、a=3、m=1とすると、p|am+1は喇り惟つが、p|an-1を塔たすnとしてn=1∈瘩眶∷が赂哼することになってしまう。　〓

徊雇矢弗 †

∝16盒のアセラが末んだ坤肠呵动の芭规≠
∝供彩废のための介霹腊眶侠掐嚏　给倡赴芭规をめざして≠
∝なっとくするオイラ〖とフェルマ〖≠