Модераторы: LSD, AntonSaburov
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Метод работает неправильно, проверка числа на простоту Рабин-Миллер 
:(
    Опции темы
Nodir
Дата 29.3.2007, 17:18 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 48
Регистрация: 9.5.2006
Где: Bukhara --> T ashkent --> Seoul

Репутация: нет
Всего: нет
Доброго дня всем. Я хотел проверить число на простату с алгоритмом Рабин-Миллера и реализавал этот алгоритм из книги Брюса Шнайера  "Прикладная криптография" Глава 11.5 
Цитата

Выберите для проверки случайное число р. Вычислите b - число делений p - 1 на 2 (т.е., 2^b - это наибольшая степень числа 2, на которое делится p - 1). Затем вычислите n, такое что p = 1 + 2^b
(1)    Выберите случайное число а, меньшее p.
(2)    Установите j = 0 и z = am mod p.
(3)    Если z = 1 или если z =p - 1, то p проходит проверку и может быть простым числом.
(4)    Если j >0 и z = 1, то p не является простым числом.
(5)    Установите j = j + 1. Если j < b и z<p - 1, установите z = z^2 mod p и вернитесь на этап (4). Если z =p - 1, то p проходит проверку и может быть простым числом.
(6)    Если у = b и z !=p - 1, то p не является простым числом.


Помогите с реализацией  smile  вот здесь само программа
Код

boolean isPrimeRabin(long p){
     int min=1000;
     int b=0,  loop=0, j=0, enough=5, certainly=0;
     long m, a, temp=0l, z;
     boolean result = false, notPrime=false;
     temp = p-1; 
     while (temp%2 == 0){
         b++; temp /= 2;
     }
     m=temp; notPrime=false;

     while ((loop<enough)&&(!notPrime)){
         a = Double.valueOf(Math.random()*min).longValue();
         j=0; z=(a*m)%p;
         System.out.println("a = "+a+"\tm = "+m+"\tz = "+z+"\tp = "+p);
         if ((z==1)||(z==p-1)){} else {
             System.out.println("breaking from 1");
             break;
         }
         
         if ((j>0)&&(z==1)){    
             System.out.println("breaking from 2");
             break; 
         }
         j++;
         //while (j<b){
         while ((j<b)&&(z<p-1)) {
             z=KichikSon.modPow(z, 2, p);
             
             if ((j>0)&&(z==1)){
                 notPrime=true;    
                 System.out.println("breaking from 3");
                 break; }    
             j++;
         } 
         
         if (z==p-1){
             loop++;
             result=true;
             if (loop==enough-1){ result=true; break; }
         }
         
         if ((j==b)&&(z!=p-1)){
             notPrime=true;
             result = false;
             System.out.println("breaking from 4");
             break;
         }
     }
     System.out.println("returning ==> "+result);
     return result;
    }



Добавлено через 3 минуты и 14 секунд
Сделал проверку с простым числом p=124739, результат
Цитата
breaking from 1
PM MAIL   Вверх
AntonSaburov
Дата 29.3.2007, 17:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Штурман
****


Профиль
Группа: Модератор
Сообщений: 5658
Регистрация: 2.7.2002
Где: Санкт-Петербург

Репутация: 51
Всего: 118
Может тебе самом проще будет дебагером пройтись по шагам ?

Потому как разбираться в чухой реализации бывает даже сложнее, чем написать свою. Если конечно кто-то это не делал раньше.

Хотя кто знает - может найдется добрый человек. Подожди немного.


--------------------
Мои проекты для Винграда
PM MAIL WWW ICQ   Вверх
nornad
Дата 29.3.2007, 18:55 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1079
Регистрация: 16.2.2007
Где: в Караганде

Репутация: 16
Всего: 31
Если исправишь ошибки в описании алгоритма, то можно и код нормальный сделать.
Например:
Цитата(Nodir @  29.3.2007,  20:18 Найти цитируемый пост)
Затем вычислите n, такое что p = 1 + 2^b

Это как? Как n связана с p или b?

Добавлено через 2 минуты и 22 секунды
Да и непонятно, для чего эта n вообще нужна - больше она нигде не упоминается.

Добавлено через 6 минут и 42 секунды
Если n <==> m, то у тебя код неверен.
Цитата(Nodir @  29.3.2007,  20:18 Найти цитируемый пост)
Затем вычислите n, такое что p = 1 + 2^b

явно не то же самое, что
Код

     while (temp%2 == 0){
         b++; temp /= 2;
     }
     m=temp;

Посмотри дебагером, что будет в m, если просто подумав не определяешь.


--------------------
Три достоинства программиста: Леность, Нетерпение и Гордость
Ларри Уолл
PM MAIL WWW ICQ Skype MSN   Вверх
Nodir
Дата 30.3.2007, 05:07 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 48
Регистрация: 9.5.2006
Где: Bukhara --> T ashkent --> Seoul

Репутация: нет
Всего: нет
Sorry, не обращал внимании на написание алгоритма там надо исправить
Цитата

Выберите для проверки случайное число р. Вычислите b - число делений p - 1 на 2 (т.е., 2^b - это наибольшая степень числа 2, на которое делится p - 1). Затем вычислите m, такое что p=1 + 2^b*m
(1)    Выберите случайное число а, меньшее p.
(2)    Установите j = 0 и z = am mod p.
(3)    Если z = 1 или если z =p - 1, то p проходит проверку и может быть простым числом.
(4)    Если j >0 и z = 1, то p не является простым числом.
(5)    Установите j = j + 1. Если j < b и z<p - 1, установите z = z^2 mod p и вернитесь на этап (4). Если z =p - 1, то p проходит проверку и может быть простым числом.
(6)    Если у = b и z !=p - 1, то p не является простым числом.
PM MAIL   Вверх
nornad
Дата 30.3.2007, 06:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1079
Регистрация: 16.2.2007
Где: в Караганде

Репутация: 16
Всего: 31
Всё равно в алгоритме ошибка. Проверяем:
р = 23  =>  b = 1  =>  m = 11
a = 3  =>  j = 0  =>  z = 10
проверка не проходит, значит не простое. Но что-то мне подсказывает, что 23 всё же простое число  smile

Добавлено через 1 минуту и 13 секунд
Хорошенько проверь описание всего алгоритма, т.к. там есть ещё немало ошибок, похоже.


--------------------
Три достоинства программиста: Леность, Нетерпение и Гордость
Ларри Уолл
PM MAIL WWW ICQ Skype MSN   Вверх
Nodir
Дата 30.3.2007, 17:23 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 48
Регистрация: 9.5.2006
Где: Bukhara --> T ashkent --> Seoul

Репутация: нет
Всего: нет
Я тоже так думал, но в книге написана точна такое.
Цитата
Брюса Шнайера  "Прикладная криптография" Глава 11.5

 Если у вас есть какой нибуть другой источник по тесту Rabina-Miller'а дайте  smile 
PM MAIL   Вверх
LSD
Дата 30.3.2007, 18:10 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Leprechaun Software Developer
****


Профиль
Группа: Модератор
Сообщений: 15718
Регистрация: 24.3.2004
Где: Dublin

Репутация: 210
Всего: 538
В Java есть стандартные методы, генерация больших простых чисел:
Код
BigInteger integer = BigInteger.probablePrime(1024, new SecureRandom());

проверка на простоту:
Код
integer.isProbablePrime(10);



--------------------
Disclaimer: this post contains explicit depictions of personal opinion. So, if it sounds sarcastic, don't take it seriously. If it sounds dangerous, do not try this at home or at all. And if it offends you, just don't read it.
PM MAIL WWW   Вверх
nornad
Дата 30.3.2007, 19:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1079
Регистрация: 16.2.2007
Где: в Караганде

Репутация: 16
Всего: 31
Судя по краткому описанию тут приведённое в книге описание сделано очень некачественно. Могу рекомендовать лишь выбросить эту книгу подальше и больше не приобретать книги этого издательства и этого автора.
Нашёл ещё один вариант, где расписано получше, но тоже на английском. Ежели разберусь, то выложу что-нибудь (код или описание алгоритма).


--------------------
Три достоинства программиста: Леность, Нетерпение и Гордость
Ларри Уолл
PM MAIL WWW ICQ Skype MSN   Вверх
Nodir
Дата 30.3.2007, 20:53 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 48
Регистрация: 9.5.2006
Где: Bukhara --> T ashkent --> Seoul

Репутация: нет
Всего: нет
Цитата
Ежели разберусь, то выложу что-нибудь

Спасибо, буду ждать и искать сам smile 
PM MAIL   Вверх
nornad
Дата 1.4.2007, 07:55 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1079
Регистрация: 16.2.2007
Где: в Караганде

Репутация: 16
Всего: 31
М-да... не выходит пока что разобраться.
Было бы нормальное описание алгоритма на русском, да желательно без лишних математических знаков и терминов...


--------------------
Три достоинства программиста: Леность, Нетерпение и Гордость
Ларри Уолл
PM MAIL WWW ICQ Skype MSN   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Java"
LSD   AntonSaburov
powerOn   tux
javastic
  • Прежде, чем задать вопрос, прочтите это!
  • Книги по Java собираются здесь.
  • Документация и ресурсы по Java находятся здесь.
  • Используйте теги [code=java][/code] для подсветки кода. Используйтe чекбокс "транслит", если у Вас нет русских шрифтов.
  • Помечайте свой вопрос как решённый, если на него получен ответ. Ссылка "Пометить как решённый" находится над первым постом.
  • Действия модераторов можно обсудить здесь.
  • FAQ раздела лежит здесь.

Если Вам помогли, и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, LSD, AntonSaburov, powerOn, tux, javastic.
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Java: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0774 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.