проверка чисел на простоту

[neeble]

нужна программа (мб кто делал, скачал откудато и тп(исходники необезательны)) которая бы проверяла число представленное ввиде (2^n)-1 на простоту

нужно чтоб работала с большими n (очень большими, хотябы начиная с N>100000)

алгоритм проверки простоты можно даже не 100%
но вот чтоб он работал быстро оч даже желательно=)

ну и предчуствуя что наврятле подобная программа у когото завалялась
задаю след вапрос как это впихнуть в delphi, интересует быстрая работа с огромными числами

если болие конкретно то как возвести число 2 в n степень (где n>100000)
и как потом с ним работать (плюсавть к ниму, минусавать, делить и т д)

[VIK_aka_TOR]

длинная арифметика в помощь... вот только с быстродействием может не особо хорошо будет... но это можно сказать единственный способ... вот ещё одна реализации длинной арифметики... и возведение в степень это можно рассмотреть как всего лишь умножение))))

[Granus]

Тест простоты Люка - Лемера для чисел Мерсена

[neeble]

using System;

namespace ConsoleApplication2q
{
    class Program
    {
        static void Main(string[] args)
        {
            try
            {

                int p = int.Parse(Console.ReadLine());
      
                long M = (1 << p) - 1;
                long L = 4;
                for (int k = 1; k < p - 1; k++)
                    L = (L * L - 2) % M;
                Console.WriteLine(L == 0 ? p + " простое" : p + " не является простым");
            }
            catch { };
            Console.ReadKey();
           
        }
    }
}

я так понимаю для больших N (в данном случае P) этот код неюзабелен да?
как написать этот код с использаванием biginteger
в гугле прочитал что он может хранить сколь угодно большие числа
(попробывал записать перед перемеными вместо Int\long biginteger непомогло
(Не удалось найти имя типа или пространства имен "BigInteger" (пропущена директива using или ссылка на сборку?))

решил дописать System.Numerics тоже непомогло (Имя типа или пространства имен "Numerics" отсутствует в пространстве имен "System" (пропущена ссылка на сборку?))

using System;
using System.Numerics;

namespace ConsoleApplication2q
{
    class Program
    {
        static void Main(string[] args)
        {
            try
            {

                BigInteger p = int.Parse(Console.ReadLine());

                BigInteger M = (1 << p) - 1;
                BigInteger L = 4;
                for (BigInteger k = 1; k < p - 1; k++)
                    L = (L * L - 2) % M;
                Console.WriteLine(L == 0 ? p + " простое" : p + " не является простым");
            }
            catch { };
            Console.ReadKey();

        }
    }
}

все ето я делаю в Microsoft Visual C# 2010 Express

я в с# вообще 0

код был взять отсюда _http://www.cyberforum.ru/csharp-beginners/thread356991.html