Тест Люка - Лемера

// нахождение остатка от деления на n числа number, возведенного в степень power
unsigned __int64 mod(unsigned __int64 number, unsigned int power, unsigned __int64 n)  // (number ^ power) % n
{
  unsigned __int64 res = 1;
  while (power)
  {
    if (power & 1)  // power % 2
      res = (1ui64 * res * number) % n;
    number = (1ui64 * number * number) % n;
    power >>= 1;  // power /= 2
  }
  return res;
}
//---------------------------------------------------------------------------
// тест Люка - Лемера
bool lucas_lehmer_test(unsigned int q)  // q - простое число, причем q > 2
{
  unsigned __int64 L = 4;  // возможные значения: 4, 10, 52, 724, 970, 10084, ...
  unsigned __int64 mersenne_number = (1ui64 << q) - 1;
  for (unsigned int i = 1; i <= q-2; i++)
  {
    L = mod(L, 2, mersenne_number);
    L += (L < 2) ? mersenne_number - 2 : -2;
  }
  return !L;
}

  unsigned int q = 31;
  String res = "Число " + String((1ui64 << q) - 1);
  if (lucas_lehmer_test(q))
    res += " простое.";
  else
    res += " составное.";
  ShowMessage(res);

#include <vcl.h>
#pragma hdrstop
 
#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
    : TForm(Owner)
{
}
//---------------------------------------------------------------------------
// нахождение остатка от деления на n числа number, возведенного в степень power
BigInt mod(BigInt number, BigInt power, BigInt n)  // (number ^ power) % n
{
  BigInt res = 1;
  while (power > 0)
  {
    if ((power % 2) > 0)
      res = (res * number) % n;
    number = (number * number) % n;
    power /= 2;
  }
  return res;
}
//---------------------------------------------------------------------------
// тест Люка - Лемера
bool lucas_lehmer_test(BigInt q)  // q - простое число, причем q > 2
{
  BigInt L = 4;  // возможные значения: 4, 10, 52, 724, 970, 10084, ...
  BigInt mersenne_number = pow(2, q) - 1;
  BigInt temp = 0;
  for (BigInt i = 1; i <= q-2; i++)
  {
    L = mod(L, 2, mersenne_number);
    if (L < 2)
      temp = mersenne_number;
    L += temp - 2;
    Form1->GaugeProgress->Progress = StrToInt((Form1->GaugeProgress->MaxValue*i/(q-2)).toString().c_str());
    Application->ProcessMessages();
  }
  return (L == 0);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::ButtonTestClick(TObject *Sender)
{
  LabelResult->Visible = 0;
  DWORD start = GetTickCount();
  String temp = EditPowerQValue->Text;
  if (temp == "" || StrToInt(temp) < 3)
    EditPowerQValue->Text = 3;
  BigInt q = AnsiString(EditPowerQValue->Text).c_str();
  MemoNumber->Text = String((pow(2, q) - 1).toString().c_str());
  String res = "число ";
  if (lucas_lehmer_test(q))
    res += " простое ";
  else
    res += " составное ";
  res += " (процесс занял ";
  res += FloatToStr((GetTickCount()-start)/1000.) + " сек)";
  LabelResult->Caption = res;
  LabelResult->Visible = 1;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::EditPowerQValueKeyPress(TObject *Sender, System::WideChar &Key)
{
  if (Key == VK_RETURN)
    ButtonTest->Click();
}

#ifndef Unit1H
#define Unit1H
//---------------------------------------------------------------------------
#include <System.Classes.hpp>
#include <Vcl.Controls.hpp>
#include <Vcl.StdCtrls.hpp>
#include <Vcl.Forms.hpp>
#include "bigint.cpp"
#include <Vcl.Samples.Gauges.hpp>
//---------------------------------------------------------------------------
class TForm1 : public TForm
{
__published:    // IDE-managed Components
    TButton *ButtonTest;
    TLabel *Label1;
    TEdit *EditPowerQValue;
    TLabel *Label2;
    TMemo *MemoNumber;
    TGauge *GaugeProgress;
    TLabel *LabelResult;
    TLabel *LabelHint;
    void __fastcall ButtonTestClick(TObject *Sender);
    void __fastcall EditPowerQValueKeyPress(TObject *Sender, System::WideChar &Key);
private:    // User declarations
public:     // User declarations
    __fastcall TForm1(TComponent* Owner);
};
//---------------------------------------------------------------------------
extern PACKAGE TForm1 *Form1;
//---------------------------------------------------------------------------
#endif

#include <vcl.h>
#pragma hdrstop
 
#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
    : TForm(Owner)
{
}
//---------------------------------------------------------------------------
BigInt mersenne_number;
//---------------------------------------------------------------------------
void TForm1::UpdateProgress(BigInt i, BigInt q)
{
  GaugeProgress->Progress = StrToInt((GaugeProgress->MaxValue*i/q).toString().c_str());
  Application->ProcessMessages();
}
//---------------------------------------------------------------------------
// тест Люка - Лемера
bool TForm1::lucas_lehmer_test(BigInt q)  // q - простое число, причем q > 2
{
  BigInt L = 4;  // возможные значения: 4, 10, 52, 724, 970, 10084, ...
 
  for (BigInt i = 1; i <= q-2; i++)
  {
    L = (L * L - 2) % mersenne_number;
    UpdateProgress(i, q-2);
  }
  return (L == 0);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::ButtonTestClick(TObject *Sender)
{
  LabelResult->Visible = 0;
  DWORD start = GetTickCount();
  String temp = EditPowerQValue->Text;
  if (temp == "" || StrToInt(temp) < 3)
    EditPowerQValue->Text = 3;
  BigInt q = AnsiString(EditPowerQValue->Text).c_str();
 
//  mersenne_number = pow(2, q) - 1;
  mersenne_number = 1;
  for (BigInt i = 1; i <= q; ++i)
  {
    mersenne_number *= 2;
    UpdateProgress(i, q);
  }
  --mersenne_number;
 
  MemoNumber->Text = String(mersenne_number.toString().c_str());
  Caption = "Тест Люка - Лемера (кол-во цифр: " + String(MemoNumber->Text.Length()) + ")";
  String res = "число ";
 
  if (lucas_lehmer_test(q))
    res += " простое";
  else
    res += " составное";
 
  res += "\nпроцесс занял\n";
  DWORD diff = (GetTickCount()-start)/1000;
  res += String(diff/3600) + "ч : " + String(diff/60%60) + "м : " + String(diff%60) + "с";
  LabelResult->Caption = res;
  LabelResult->Visible = 1;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::EditPowerQValueKeyPress(TObject *Sender, System::WideChar &Key)
{
  if (Key == VK_RETURN)
    ButtonTest->Click();
}

#ifndef Unit1H
#define Unit1H
//---------------------------------------------------------------------------
#include <System.Classes.hpp>
#include <Vcl.Controls.hpp>
#include <Vcl.StdCtrls.hpp>
#include <Vcl.Forms.hpp>
#include "bigint.cpp"
#include <Vcl.Samples.Gauges.hpp>
//---------------------------------------------------------------------------
class TForm1 : public TForm
{
__published:    // IDE-managed Components
    TButton *ButtonTest;
    TLabel *Label1;
    TEdit *EditPowerQValue;
    TLabel *Label2;
    TMemo *MemoNumber;
    TGauge *GaugeProgress;
    TLabel *LabelResult;
    TLabel *LabelHint;
    void __fastcall ButtonTestClick(TObject *Sender);
    void __fastcall EditPowerQValueKeyPress(TObject *Sender, System::WideChar &Key);
private:    // User declarations
public:     // User declarations
    __fastcall TForm1(TComponent* Owner);
    void UpdateProgress(BigInt i, BigInt q);
    bool lucas_lehmer_test(BigInt q);
};
//---------------------------------------------------------------------------
extern PACKAGE TForm1 *Form1;
//---------------------------------------------------------------------------
#endif

L = (L * L - 2) % mersenne_number;  // сложение и вычитание - "узкие" места (медленно работают)