VPF::Нужен алгоритм проверки числа на простоту

HaronDDC

Дата 3.9.2004, 02:22 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

Придуман ли ТОЧНЫЙ и быстрый алгоритм проверки числа на простоту (Рабина-Миллера не приводить)?

podval

Дата 3.9.2004, 09:37 (ссылка)

(нет голосов)

Загрузка ...

Где я? Кто я?

Профиль
Группа: Экс. модератор
Сообщений: 3094
Регистрация: 25.3.2002
Где: СПб

Репутация: 18
Всего: 62

Lucas-Lehmer Test
Для ускорения используют FFT с иррациональным основанием при возведении в квадрат больших чисел.
Добавлено @ 09:46
Пользуемся Гуглом!

APR-CL (по фамилиям ученых - Adleman, Pomerance and Rumely; Cohen and Lenstra) - здесь реализация на Бейсике.

ECPP (Elliptic Curve Primality Test).

По времени выполнения они приблизительно одинаковые, но ECPP имеет то преимущество, что он создает некий сертификат, используя который можно в любой момент проверить, простое число или нет.

val

Дата 3.9.2004, 11:06 (ссылка)

(нет голосов)

Загрузка ...

Program developer

Профиль
Группа: Участник Клуба
Сообщений: 992
Регистрация: 14.1.2003
Где: г. Киев

Репутация: 1
Всего: 7

Просто интересно, в каких задачах можно встретиться с необходимостью проверки на простоту числа?

--------------------

Терпимость - величайшее благо человечества...
Ярчайший признак интеллекта – постоянно хорошее настроение…

maxim1000

Дата 3.9.2004, 11:08 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 33
Всего: 110

очень часто приходится этим заниматься в криптографии

--------------------

qqq

val

Дата 3.9.2004, 11:30 (ссылка)

(нет голосов)

Загрузка ...

Program developer

Профиль
Группа: Участник Клуба
Сообщений: 992
Регистрация: 14.1.2003
Где: г. Киев

Репутация: 1
Всего: 7

Цитата

очень часто приходится этим заниматься в криптографии

А можно маленький примерчик?

--------------------

Терпимость - величайшее благо человечества...
Ярчайший признак интеллекта – постоянно хорошее настроение…

maxim1000

Дата 3.9.2004, 11:56 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 33
Всего: 110

Стандарт цифровой подписи RSA
точно его не припомню, но принцип такой:
1. берется число (оно известно всем)
2. рассматривается множество остатков от деления на него

теперь - несколько вариантов:
1. если число простое - есть несложный алгоритм поиска обратного к любому элементу (кроме 0)
2. если число является произведением двух простых чисел (и известно каких), тоже есть простой алгоритм
3. если число является произведением двух простых чисел, но никто не знает, каких, то найти обратный становится проблематично

таким образом 2й и 3й варианты отличаются только тем, знают ли разложение числа на множители или нет

при этом проверить, правильно ли определен обратный элемент - проще простого

таким образом, подписать (найти обратный к некоторому элементу) может только тот, кто знает два простых числа
а проверить может любой

--------------------

qqq

val

Дата 3.9.2004, 14:17 (ссылка)

(нет голосов)

Загрузка ...

Program developer

Профиль
Группа: Участник Клуба
Сообщений: 992
Регистрация: 14.1.2003
Где: г. Киев

Репутация: 1
Всего: 7

maxim1000
Thanx...

--------------------

Терпимость - величайшее благо человечества...
Ярчайший признак интеллекта – постоянно хорошее настроение…

Diesel Draft

Дата 9.7.2006, 15:00 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 876
Регистрация: 18.1.2005
Где: Lviv, Ukraine

Репутация: -1
Всего: 5

О, тоже бюсь над етой проблемой
Дайте какой нибуть пример такого алгоритма

--------------------

НЕДОМА в маси

SoWa

Дата 9.7.2006, 17:12 (ссылка)

(нет голосов)

Загрузка ...

Харекришна

Профиль
Группа: Комодератор
Сообщений: 2422
Регистрация: 18.10.2004

Репутация: 6
Всего: 74

Полином Мятисевича
Только я его не нашел. Говорят рульная вещь. Мгновенно проверяет на простоту.

--------------------

Всем добра smile

Rockie

Дата 13.7.2006, 14:36 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

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

Репутация: нет
Всего: 31

Цитата(Diesel Draft @ 9.7.2006, 15:00

)

О, тоже бюсь над етой проблемой
Дайте какой нибуть пример такого алгоритма

Код

//////////////////////////////////////////////////////////////////////////////
//    
//  Finding prime numbers    
//  (c) Johna Smith, 1996    
//    
//  Method description:    
//   We take a number and try to divide it. If we can divide it    
//   without remainder - this is not prime number.    
//   We can take into account only odd numbers, because we can    
//   divide all even number by 2. Also we can store all prime    
//   numbers that are already found in an array and try to divide    
//   all new numbers only by numbers from this array.    
//   If we want to find all prime numbers less than N the size of    
//   the array should be sqrt(N)/2    
//    
//////////////////////////////////////////////////////////////////////////////    
#include <stdio.h>    
#define N   160  // so we can find all prime numbers that are less than 100000    
#define M   25   // check all numbers less than 250    
int Simple[N];    
int k=0;    
enum {yes,no} simple;    
void main(void)    
{    
  // it's easy: 2 and 3 are prime    
  if (M>=2) printf("2\n"); // 2 is simple 'cause we can divide it only by itself and 1    
  Simple[k++]=2;    
  if (M>=3) printf("3\n");    
  Simple[k++]=3;    
  // but what we can say about other numbers:    
  for(int i=5;i<=M;i+=2)    
  {    
    simple=yes;    
    for(int j=0;j<k;j++)    
    {    
      if (Simple[j]*Simple[j]>i) break; // other Simple[j] is too big for i    
      if ((i%Simple[j])==0) simple=no; // there's no remainder - not prime    
    }    
    if (simple==yes)    
    {    
      printf("%d\n",i);    
      Simple[k++]=i;    
    }    
  }    
}

--------------------

Чтобы иметь большой гардероб - надо иметь большой гардероб.

anatox91

Дата 18.1.2008, 21:08 (ссылка)

(нет голосов)

Загрузка ...

программист-самоучка

Профиль
Группа: Участник
Сообщений: 699
Регистрация: 12.1.2008
Где: ++Украина.Крым++

Репутация: нет
Всего: 13

можно вроде еще так:

Код


#include <iostream>
#include <math.h>
using namespace std;

int main() {
    int n;
    int i;
    bool is_prime;
    
    is_prime=true;
    
    cout << "Enter a number and press ENTER: ";
    cin >> n;
    cin.ignore();
    double sqrt_n = sqrt(static_cast<double>(n));
    for (i=2; i <= sqrt_n; i++) {
        if (n % i == 0) {
              is_prime = false;
              break;
              }
        }
        if (is_prime)
              cout << "Number is prime.";
        else
              cout << "Number is not prime.";
    cin.get();
    return 0;
}

--------------------

Sony VAIO VGN-FW480J

user posted image

stab

Дата 18.1.2008, 22:07 (ссылка)

(голосов:1)

Загрузка ...

Эксперт

Профиль
Группа: Экс. модератор
Сообщений: 1839
Регистрация: 1.1.2003

Репутация: нет
Всего: 48

anatox91, можно-то оно конечно можно, только числа влезающие в int никакого интереса не представляют уже несколько веков..

--------------------

6, 6, 6 - the number of the beast.

Iosif1

Дата 23.3.2009, 20:54 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 26
Регистрация: 23.3.2009
Где: г. Донецк, Украин а

Репутация: нет
Всего: нет

Цитата(HaronDDC @ 3.9.2004, 02:22)

Придуман ли ТОЧНЫЙ и быстрый алгоритм проверки числа на простоту (Рабина-Миллера не приводить)?

Мною разработан детерминированный алгоритм  определения числа на простоту.
Я уже ввёл эту информацию на вашем форуме, как сообщение для программистов.
Мне не удаётся самостоятельно завершить программу.
Мною самостоятельно составлены, названные мной, подпрограммы (16)  в таблицах Эксель.
Необходимо совершить объединение, разводки, с вводом проверяемых чисел и фиксацией простых чисел, например, в выделенном файле. Или написать от начала до конца.
Я предпочитаю,именно, сотрудничество. Чтобы после завершения, например, простые большие числа поискали вместе.
Я обратился на Ваш форум с вопросом: Возможно ли сотрудничество  форума или какого-нибудь участника со мной для написания программы.
Удивительно, но мне уже долго не удаётся найти программиста "вычислителя".
Все, почему-то узконаправленные.
Я понимаю, что различные отрасли и промышленности, и науки требуют таких программистов, но мне от этого не легче.
Конечно, хотелось бы, чтобы обеспечивался визуальный контакт. (г.Донецк, Украина)
Начало алгоритма опубликовано в Интернете.
Если будут ответы, дам ссылки, а то даю в пустоту - Обидно, понимаешь!

Это сообщение отредактировал(а) Iosif1 - 25.3.2009, 21:25

Soah

Дата 23.3.2009, 23:03 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 512
Регистрация: 18.2.2009

Репутация: 5
Всего: 54

Цитата(Iosif1 @ 23.3.2009, 20:54

)

Мною разработан детерминированный алгоритм определения числа на простоту.

до какого числа проверяли?

Цитата(Iosif1 @ 23.3.2009, 20:54

)

простые большие числа поискали

есть алгоритм который формирует ооочень большое простое число, даже оперативки не хватит.

Цитата(Iosif1 @ 23.3.2009, 20:54

)

Начало алгоритма опубликовано в Интернете.

давайте посмотрим что за алгоритм.

Iosif1

Дата 24.3.2009, 02:42 (ссылка)

(нет голосов)

Загрузка ...

Цитата(Soah @ 23.3.2009, 23:03

)

до какого числа проверяли?

Проверка ограничивалась возможностями таблиц Эксель.
Проверка строилась на анализе (опознавании) - простое или нет данное число.
Простое (по под алгоритму) - отвергается, составное - требует перехода к следующему числу. максимальное количество таких проверок для конкретного числа - четыре.

Цитата(Soah @ 23.3.2009, 23:03

)

есть алгоритм который формирует ооочень большое простое число, даже оперативки не хватит.

Но число можно показывать в формализованном виде.

Цитата(Soah @ 23.3.2009, 23:03

)

давайте посмотрим что за алгоритм.

Начнём с начала: Прикрепляю файл к данному сообщению.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »