2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 4 Задачи
Сообщение05.03.2010, 13:24 
Аватара пользователя


09/03/06
40
Владивосток
Здраствуйте.
Мне нужна помошь в реализации четырех программ:
Преподаватель сказал реализовать на любом языке, а дополнительную информацию мол найдем в Интернете. :?
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 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Antonina в сообщении #294786 писал(а):
А по поводу самих тестов Яндекс нашел 0 стр. А по тесту Ферма даже Гугл ничего не нашел

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

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

 Профиль  
                  
 
 Re: 4 Задачи
Сообщение06.03.2010, 10:40 
Аватара пользователя


09/03/06
40
Владивосток
Спасибо, можно считать - первая задача решена))
А с остальными как быть?
И по поводу непосредственно программирования, правильно ли я думаю, что: 1) лучше использовать Яву, т.к. там есть класс встроенных больших чисел; 2) Лучше всего использовать массивы.

 Профиль  
                  
 
 Re: 4 Задачи
Сообщение06.03.2010, 13:34 
Заслуженный участник
Аватара пользователя


06/10/08
6422
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 
Аватара пользователя


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

 Профиль  
                  
 
 Re: 4 Задачи
Сообщение07.03.2010, 13:32 
Заслуженный участник
Аватара пользователя


06/10/08
6422
По поводу параллельной версии ро-метода Поллард на своей домашней странице дает ссылку на 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 
Аватара пользователя


09/03/06
40
Владивосток
Эти задачи - упражнения из книги Н.Смарт "Криптография".
Вот что у меня получилось по первым двум:
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 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group