PHP နှင့် GMP တို့နှင့်အတူအရေအတွက်လူးကပ်ကပ် - လူးယာအရည်အသွေးစစ်ဆေးမှုကိုဘယ်လိုအကောင်အထည်ဖော်မလဲ

M66 2025-06-19

PHP နှင့် GMP ကို အသုံးပြု. ကြီးမားသောနံပါတ်များဖြင့် Lucas-Lehmer Primeness Test ကိုမည်သို့အကောင်အထည်ဖော်ရမည်နည်း

Lucas-Lehmer မူလတန်းစမ်းသပ်မှုသည် Mersenne အရေအတွက်ကိုအကဲဖြတ်ရန်အသုံးပြုသော algorithm ကိုအသုံးလေ့ရှိပြီးနံပါတ်သီအိုရီနှင့် cryptography များတွင်ကျယ်ပြန့်စွာအသုံးပြုသည်။ Mersenne Nums သည် Form 2 ^N -1 ၏ကိန်းဂဏန်းများဖြစ်သည်။ N သည်အပြုသဘောဆောင်သောကိန်းဖြစ်သည်။ ဤဆောင်းပါးသည် PHP နှင့် GMP စာကြည့်တိုက်များမည်သို့အသုံးပြုရမည်ကို Mersenne နံပါတ်သည် PRIME နံပါတ်ရှိမရှိဆုံးဖြတ်ရန်ဤအချက်ကိုအကောင်အထည်ဖော်ရန်မည်သို့အသုံးပြုရမည်ကိုပြလိမ့်မည်။

GMP စာကြည့်တိုက်ကို install လုပ်ပြီး configure လုပ်ပါ

ပထမ ဦး စွာသင်၏ PHP ပတ်ဝန်းကျင်တွင် GMP စာကြည့်တိုက်တပ်ဆင်ထားကြောင်းသေချာပါစေ။ GMP စာကြည့်တိုက်ကို install လုပ်ထားမရှိမရှိစစ်ဆေးရန် Phpinfo () command ကိုသုံးနိုင်သည်။ ထည့်သွင်းခြင်းမပြုပါက PHP ပြုစုသည့်အခါ GMP option ကို enable လုပ်နိုင်သည်သို့မဟုတ် Package Manager မှတဆင့် Linux System ရှိ Package Manager မှတဆင့်ထည့်သွင်းနိုင်သည်။

Lucas-Lehmer မူလတန်းစမ်းသပ်မှု function ကိုအကောင်အထည်ဖော်ခြင်း

PHP တွင် GMP စာကြည့်တိုက်ကို အသုံးပြု. ကြီးမားသောအရေအတွက်ကိုပြုလုပ်နိုင်သည်။ Lucas-Lehmer စ Primitive Test ကိုအကောင်အထည်ဖော်သည့် PHP function ၏ဥပမာတစ်ခုမှာဤတွင်ဖြစ်သည်။

 
function lucasLehmerTest($n) {
    $s = gmp_init(4);
    $m = gmp_sub(gmp_pow(2, $n), 1);

    for ($i = 0; $i < $n - 2; $i++) {
        $s = gmp_mod(gmp_sub(gmp_mul($s, $s), 2), $m);
    }

    return gmp_cmp($s, 0) == 0;
}

ဤလုပ်ဆောင်ချက်သည် Mersenne နံပါတ်၏ထပ်ကိန်းကိုကိုယ်စားပြုသော parameter n n ကိုလက်ခံသည်။ အဆိုပါ function ကို lucas-lehmer sequence ကိုအတွက် item တစ်ခုချင်းစီကိုတွက်ချက်နှင့်နောက်ဆုံး item သည် 0 င်ရှိမရှိစစ်ဆေးသည်။ ဟုတ်ကဲ့ပြန်ရောက်သည်ဆိုပါက Mersenne နံပါတ်သည်အဓိကနံပါတ်ဖြစ်သည်ဟုဆိုလိုသည်။ အကယ်. မှားယွင်းသောပြန်လာလျှင်၎င်းသည် Mersenne နံပါတ်သည်အဓိကနံပါတ်မဟုတ်ပါဟုဆိုလိုသည်။

Lucas-Lehmer-Lehmer မူလတန်းစမ်းသပ်မှု function ကိုခေါ်ပါ

ထို့နောက်အထက်ဖော်ပြပါ function ကို Mersenne နံပါတ်၏အိမ်ခြံမြေစမ်းသပ်မှုပြုလုပ်ရန်အသုံးပြုနိုင်သည်။ Mersenne နံပါတ်သည်အဓိကနံပါတ်ဖြစ်သည်ကိုရှာဖွေတွေ့ရှိရန်ဥပမာတစ်ခုရှိသည်။

 
$n = 29; // သင့်လျော်သောအညွှန်းကိန်းကိုရွေးချယ်ပါ，ဒီမှာ29ဥပမာတစ်ခုအနေဖြင့်
$isPrime = lucasLehmerTest($n);

if ($isPrime) {
    echo "2^{$n} - 1 ဒါဟာအဓိကနံပါတ်ပါ";
} else {
    echo "2^{$n} - 1 不ဒါဟာအဓိကနံပါတ်ပါ";
}

ဤဥပမာတွင်ကျွန်ုပ်တို့သည်စမ်းသပ်ခြင်းအတွက် 29 ခုကိုအညွှန်း 29 ခုကိုရွေးချယ်ပြီး,

စွမ်းဆောင်ရည်အကောင်းမြင်

Lucas-Lehmer မူလတန်းစမ်းသပ်မှုများကိုပမာဏများစွာတွက်ထားသောကြောင့်၎င်းသည်ပိုမိုကြီးမားသော n တန်ဖိုးများအတွက်အချိန်များစွာကြာနိုင်သည်။ စွမ်းဆောင်ရည်တိုးတက်စေရန်အတွက်အောက်ပါ optimization နည်းဗျူဟာများကိုထည့်သွင်းစဉ်းစားနိုင်သည် -

အကယ်. N ကိုယ်တိုင်သည် PRIME နံပါတ်ဖြစ်ပြီး 2 ⁿ -1 သည်အဓိကနံပါတ်ဖြစ်နိုင်သည်။
n နံပါတ် n ၏မမှန်ကန်တဲ့တွက်ချက်မှုကိုရှောင်ရှားရန်ထူးဆန်းနံပါတ်ဖြစ်ရမည်။
64 ထက်နည်းသော n တန်ဖိုးများကို filter လုပ်ပါ။ ဤကိစ္စများကိုအတည်ပြုပြီးဖြစ်သည်။

ဤအကောင်းမြင်မှုများနှင့်အတူ algorithm အမြန်နှုန်းကိုသိသိသာသာတိုးတက်အောင်လုပ်နိုင်သည်, အထူးသဖြင့် Mersenne နံပါတ်များကိုကိုင်တွယ်သောအခါ

နိဂုံးချုပ်အားဖြင့်

ဤဆောင်းပါးသည် Lucas-Lehmer Primeness Testing ကိုအကောင်အထည်ဖော်ရန် PHP နှင့် GMP စာကြည့်တိုက်များမည်သို့အသုံးပြုရမည်ကိုမိတ်ဆက်ပေးသည်။ GMP ကိုအကြီးစားလုပ်ငန်းများအတွက် အသုံးပြု. Mersenne နံပါတ်သည်အဓိကနံပါတ်တစ်ဖြစ်သည်ကိုသင်ထိထိရောက်ရောက်ဆုံးဖြတ်နိုင်သည်။ ထို့အပြင်တွက်ချက်မှုများကိုအရှိန်မြှင့်ရန်ကူညီရန်စွမ်းဆောင်ရည်အကောင်းဆုံးအကြံပြုချက်များကိုအချို့သောစွမ်းဆောင်ရည်အကောင်းဆုံးအကြံပြုချက်များကိုပေးထားသည်။ ဤဆောင်းပါးသည်ဤ algorithm ကိုနားလည်ရန်စိတ်ဝင်စားသောစာဖတ်သူများအားအထောက်အကူပြုလိမ့်မည်ဟုမျှော်လင့်ပါ။

ဆက်စပ်အကြောင်းအရာ

PHP နှင့် GMP ကို အသုံးပြု. ကြီးမားသောနံပါတ်များဖြင့် Lucas-Lehmer Primeness Test ကိုမည်သို့အကောင်အထည်ဖော်ရမည်နည်း