Эти задачи - упражнения из книги Н.Смарт "Криптография".
Вот что у меня получилось по первым двум:
1)))Тест Рабина-Миллера состоит в следующем:
Пусть n-нечетное и n-1=2^s t,t- нечетное. Если число n является простым, то при всех a≥2 выполняется сравнение a^(n-1)≡1 (mod n). Поэтому, рассматривая элементы a^t,a^2t,…,a^(2^(s-1) t), можно заметить, что либо среди них найдется равный -1 (mod n), либо a^t≡1 (mod n).
На этом замечании основан следующий вероятностный тест простоты:
[list=]Выбираем случайное число из интервала {1,2,…,n-1} и проверяем с помощью алгоритма Евклида условие (a,n)=1;
Если оно не выполняется, то ответ «n-составное»;
Вычисляем a^t (mod n);
Если a^t≡±1 (mod n), то переходим к п. 1;
Вычисляем 〖〖(a〗^t)〗^2,〖〖(a〗^t)〗^4,…,〖〖(a〗^t)〗^(2^(s-1) ) (mod n) до тех пор, пока не появится -1;
Если ни одно из этих чисел не равно -1, то ответ «n-составное»;
Если мы достигли -1, то ответ неизвестен, и тест можно повторить.[/list]
Код:
static string pow(IntX n)
{
IntX even = 0, odd = 0;
for (IntX i = 2; ; i *= 2)
{
even++;
if (n < i)
if (i - n < n - i / 2)
{
odd = i - n;
return "2^" + even.ToString() + " - " + odd.ToString();
}
else
{
odd = n - i / 2;
return "2^" + (--even).ToString() + " + " + odd.ToString();
}
}
}
/\/\/\/\/\/\//\/\
public static string Ferma1(IntX N, IntX A)
{
IntX n = N, a = A, n2 = N;
IntX temp = 1, temp2, q, count = 1, count2; IntX[] mas = new IntX[2000];
ulong Maxi = 0;
mas[0] = 1;
n2 -= 1;
for (ulong i = 1; n2 > 1; )
{
q = n2 / 2; temp2 = n2 % 2;
if (temp2 != 0)
{
mas[i] = n2;
n2 -= 1;
Maxi = i;
i++;
}
else n2 = q;
}
for (ulong i = Maxi; n > count; )
{
temp2 = temp * a;
q = temp2 / n; temp = temp2 % n;
if (temp == 0) break;
count2 = count + 1;
if (i == 0)
{
a = temp;
count2 = count * 2;
count = count2;
}
else
{
if (count2 >= mas[i])
{
a = A;
i--;
count++;
}
else
{
a = temp;
count2 = count * 2;
count = count2;
}
}
}
if (temp == 1)
return "Maybe this number is simple";
else
return "This number is composite";
}
2)))«(p-1) метод факторизации Полларда»
Предположим, что n- нечетное составное число, не имеющее небольших простых делителей. Обозначим через p намиеньший простой делитель числа n. Наша задача заключается в его нахождении.
Предположим, что число (p-1) разлагается в произведение небольших простых делителей. Выберем число k, которое является параметром метода. Для успешной работы нужно, чтобы выполнялось условие
(p-1) | M(k), где M(k)=k!
В силу малой теоремы Ферма выполняется сравнение
2^(M(k))≡1 (mod p).
Если при этом
2^(M(k))≢1 (mod n),
то
p | (2^M(k) -1,n),
где 1<p,(2^M(k) -1,n)<n. Таким образом, d=(2^M(k) -1,n) является собственным делителем числа n, кратным p.
На этой идее основан следующий метод нахождении собственного делителя числа n. Так как число k неизвестно, то в нем использован последовательный перебор малых значений до некоторого фиксированного значения.
Пусть k целое число, например k<〖10〗^6, и c небольшое целое с условием (c,n)=1, например c=2.
Для каждого i от 1 до k вычисляется m_i=c^(M(i)) (mod n) и проверяется тест шага 2.
Вычислить d=(m_i-1,n). Если 1<d<n, то найден нетривиальный делитель числа n. В противном случае полагаем i=i+1.
Код:
using System;
using System.Collections.Generic;
using System.Text;
namespace Math_Crypt_Meth
{
class Legandr_symbol
{
//define
//construct
public Legandr_symbol()
{
}
//methods
//main algorithm for symbol
public int l_sym(long q, long p)
{
//check if q==2
if (q != 2)
{
//check if q<p
//check(ref q, ref p);
//check if need to place (-)minus
if (a_mod_m(q, 4) == 3 && a_mod_m(p, 4) == 3)
{
//making smaller q
q = a_mod_m(q, p);
//check if q<p if q!=2, coze other algorithms
//if (q != 2)
//check(ref q, ref p);
//call base function
return -Le(q, p);
}
//if without (-)minus
else
{
//making smaller q
q = a_mod_m(q, p);
//check if q<p if q!=2, coze other algorithms
//if (q != 2)
//check(ref q, ref p);
//call base function
return Le(q, p);
}
}
return Le(q, p);
}
//internal
//compare a b
void check(ref int a, ref int b)
{
if (a < b)
{
int temp;
temp = a; a = b; b = temp;
}
}
//symbol of Legandr
int Le(long q, long p)
{
if (q != 2)
return (int)a_mod_m((long)Math.Pow(q, ((double)p - 1) / 2), p);
return (int)Math.Pow(-1,(p*p-1)/8);
}
//module function
long a_mod_m(long a, long m)
{
if (m > 0)
return a - (long)Math.Floor((double)a / m) * m;
else
{
Console.Error.WriteLine("Bad input in 'mod' method");
return 0;
}
}
}
}
Насколько верно у меня получилось?
Просьба помочь и с другими 2 задачами, особенно с реализацией на языках программирования. Я же девушка, мне тяжело...
А то с программной реализацией совсем туго - мне 2 мальчика помогали в программный язык переводить по моим алгоритмам! Воть!
−3.
), сама посмотрела, почитала - вроде лучше реализовывать на Яве, т.к. там есть встроеный класс больших чисел, в отличие от С++(время работы соответсвующих языков програмирования с большими числами существенно отличается - из опыта 
). А по поводу самих тестов Яндекс нашел 0 стр. 
А по тесту Ферма даже Гугл ничего не нашел 
, 
и т. д., прикидываете, как это время бутеь расти