2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 4 Задачи
Сообщение05.03.2010, 13:24 
Аватара пользователя
Здраствуйте.
Мне нужна помошь в реализации четырех программ:
Преподаватель сказал реализовать на любом языке, а дополнительную информацию мол найдем в Интернете. :?
1. Реализуйте тесты Ферма и Миллера-Рабина и найдите с их помощью
свидетелей делимости числа $2 ^ 1 ^0 ^2 ^4$−3.
По этой задаче не допонимаю, какие точно тесты имеются ввиду (слова преподавателя по этому поводу см. выше 8-) ), сама посмотрела, почитала - вроде лучше реализовывать на Яве, т.к. там есть встроеный класс больших чисел, в отличие от С++(время работы соответсвующих языков програмирования с большими числами существенно отличается - из опыта :D ). А по поводу самих тестов Яндекс нашел 0 стр. :cry: А по тесту Ферма даже Гугл ничего не нашел :cry:
2. Напишите программу для (P −1) -метода факторизации. Насколько
большие составные числа Ваша программа сможет разложить на
множители?
Ладно с программой, а как на второй вопрос ответить???
3. Реализуйте ρ -метод Полларда и поэкспериментируйте с разными
определениями детерминированных случайных блужданий. Какой из
них наиболее эффективен? (Эффективность здесь означает более
быстрое в среднем решение задачи о дискретных логарифмах).
4. Разработайте программу для параллельного метода Полларда решения
задачи дискретного логарифмирования в конечных полях. Насколько
сложную задачу дискретного логарифмирования Вы сможете решить с
помощью этой программы в течение 24 часов?
Вотъ на последний вопрос как ответить?))
Заранее благодарна за любую помощь. :roll:

 
 
 
 Re: 4 Задачи
Сообщение05.03.2010, 14:39 
Аватара пользователя
Antonina в сообщении #294786 писал(а):
А по поводу самих тестов Яндекс нашел 0 стр. А по тесту Ферма даже Гугл ничего не нашел

Зря на гугл наговариваете, он мне четвертой ссылкой выдал вот эту страницу: http://rain.ifmo.ru/cat/view.php/theory ... heory-2005
Antonina в сообщении #294786 писал(а):
Ладно с программой, а как на второй вопрос ответить???

Опытным путем :)

 
 
 
 Re: 4 Задачи
Сообщение06.03.2010, 10:40 
Аватара пользователя
Спасибо, можно считать - первая задача решена))
А с остальными как быть?
И по поводу непосредственно программирования, правильно ли я думаю, что: 1) лучше использовать Яву, т.к. там есть класс встроенных больших чисел; 2) Лучше всего использовать массивы.

 
 
 
 Re: 4 Задачи
Сообщение06.03.2010, 13:34 
Аватара пользователя
P-1-метод: http://algolist.manual.ru/maths/teornum/factor/p-1.php
описания ро-метода применительно к дискретному логарифму не нашел на русском, на английском краткое описание есть в http://www.cs.toronto.edu/~cvs/dlog/research_paper.pdf, пункт 2.2. Если непонятно - напишите, я попробую объяснить.

-- Сб мар 06, 2010 13:39:22 --

Antonina в сообщении #295089 писал(а):
И по поводу непосредственно программирования, правильно ли я думаю, что: 1) лучше использовать Яву, т.к. там есть класс встроенных больших чисел; 2) Лучше всего использовать массивы.

Лучше использовать то, что знаете. Библиотека больших чисел для C/C++ назыается GMP: http://gmplib.org. Еще есть классы NTL: http://www.shoup.net/ntl/

 
 
 
 Re: 4 Задачи
Сообщение07.03.2010, 06:26 
Аватара пользователя
В общих чертах первые три задачи ясны. Будемс пробовать реализовывать программно))
А вот с четвертой задачей как быть?
Цитата:
4. Разработайте программу для параллельного метода Полларда решения
задачи дискретного логарифмирования в конечных полях. Насколько
сложную задачу дискретного логарифмирования Вы сможете решить с
помощью этой программы в течение 24 часов?

 
 
 
 Re: 4 Задачи
Сообщение07.03.2010, 13:32 
Аватара пользователя
По поводу параллельной версии ро-метода Поллард на своей домашней странице дает ссылку на P.C. van Orschot and M.J. Wiener, Parallel collision search with cryptanalytic applications, (J. Crypt., 12 (1999), 1-28).
Онлайн доступно тут: http://cr.yp.to/bib/1999/vanoorschot.pdf

Насчет 24 часов - пробуете, за какое время решаются задачи размера $2^8$, $2^9$ и т. д., прикидываете, как это время бутеь расти

 
 
 
 Re: 4 Задачи
Сообщение18.04.2010, 06:51 
Аватара пользователя
Эти задачи - упражнения из книги Н.Смарт "Криптография".
Вот что у меня получилось по первым двум:
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 задачами, особенно с реализацией на языках программирования. Я же девушка, мне тяжело... :roll:
А то с программной реализацией совсем туго - мне 2 мальчика помогали в программный язык переводить по моим алгоритмам! Воть! :roll: :oops:

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group