|
In mathematics, the Lucas–Lehmer–Riesel test is a primality test for numbers of the form ''N'' = ''k'' ⋅ 2''n'' − 1, with 2''n'' > ''k''. The test was developed by Hans Riesel and it is based on the Lucas–Lehmer primality test. It is the fastest deterministic algorithm known for numbers of that form. For numbers of the form ''N'' = ''k'' ⋅ 2''n'' + 1 (Proth numbers), either application of Proth's theorem (a Las Vegas algorithm) or one of the deterministic proofs described in Brillhart-Lehmer-Selfridge 1975 are used. ==The algorithm== The algorithm is very similar to the Lucas–Lehmer test, but with a variable starting point depending on the value of ''k''. Define a sequence for all ''i'' > 0 by: : Then ''N'' is prime if and only if it divides ''u''''n''−2. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Lucas–Lehmer–Riesel test」の詳細全文を読む スポンサード リンク
|