Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 16.05.2016, 23:04   #1
Вероника99
Форумчанин
 
Регистрация: 15.12.2013
Сообщений: 414
По умолчанию Псевдопростые числа Эйлера

Добрый день.Возник вопрос по поводу псевдопростых чисел Эйлера. Растолкуйте,пожалуйста,понятие конгруэнтности чисел, ибо мои вычислениям не совпадают с тем,что написано в Википедии. Например n=121 с основанием 3.
Подставляю:
1)3(121-1)/2 = (3/121)
2)(3(121-1)/2 )mod 121 =1
3)(3/121) mod 121=0.024..
Я думала,что выражение 2) в итоге должно быть равно выражению 3).Но они никак не равны. Что я не так понимаю,подскажите пожалуйста. Спасибо
Изображения
Тип файла: jpg 56.JPG (75.2 Кб, 123 просмотров)
Вероника99 вне форума Ответить с цитированием
Старый 17.05.2016, 06:48   #2
p51x
Старожил
 
Регистрация: 15.02.2010
Сообщений: 15,695
По умолчанию

ну вы формулу то дочитайте, особенно после слова "где"
p51x вне форума Ответить с цитированием
Старый 17.05.2016, 15:20   #3
Вероника99
Форумчанин
 
Регистрация: 15.12.2013
Сообщений: 414
По умолчанию

Я не правильно поняла понятие символа Якоби,объясните пожалуйста,почему тогда в последовательности например не указано n=341,a=2,ведь мода при таких параметрах будет равна 1? если символ Якоби это {-1,0,1}
Вероника99 вне форума Ответить с цитированием
Старый 17.05.2016, 16:01   #4
p51x
Старожил
 
Регистрация: 15.02.2010
Сообщений: 15,695
По умолчанию

Цитата:
ведь мода при таких параметрах будет равна 1?
Как раз и неть.
(2/341) = (-1) ^ ((341*341 -1)/8) = (-1) ^ 14535 = -1
p51x вне форума Ответить с цитированием
Старый 17.05.2016, 16:42   #5
Вероника99
Форумчанин
 
Регистрация: 15.12.2013
Сообщений: 414
По умолчанию

Поняла.Посмотрите пожалуйста, делала по этому алгоритму http://neerc.ifmo.ru/wiki/index.php?...BE%D0%B1%D0%B8
при передаче параметров (3,121) выдает результат 40, а должен я так понимаю 1.В чем может быть причина?
C#
Код:
static double Yakobi(int a,int n)
        {
            double res;
            if (a < 0)
            {
                res = (-a / n) * (Math.Pow(-1, (n - 1) / 2));
                return res;
            }
            else if (a % 2 == 0)
            {
                res = ((a / 2) / n) * (Math.Pow(-1, (n*n - 1) / 8));
                return res;
            }
            else if (a == 1)
            {
                res = 1;
                return res;
            }
            else if (a < n)
            {
                res = (n / a) *(Math.Pow(-1, (((a - 1) / 2)*((n-1)/2)))); 
                return res;
            }
            else
            {
                res = ((a % n) / n);
                return res;
            }

           
        }
Вероника99 вне форума Ответить с цитированием
Старый 17.05.2016, 16:55   #6
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

А зачем -1 так в степень возводить? Для четного показателя степени всегда +1, для нечетного -1 без всякого Pow
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 17.05.2016, 16:56   #7
p51x
Старожил
 
Регистрация: 15.02.2010
Сообщений: 15,695
По умолчанию

Ошибка простая: справа в формуле тоже стоит символ Якоби, а не просто скобки
p51x вне форума Ответить с цитированием
Старый 17.05.2016, 17:09   #8
Вероника99
Форумчанин
 
Регистрация: 15.12.2013
Сообщений: 414
По умолчанию

А как тогда правильно реализовать программно?
Код:
  static double Yakobi(int a, int n)
        {
            double res;
            if (a < 0)
            {
                res = -a  ;
                return res;
            }
            else if (a % 2 == 0)
            {
                res = (a / 2);
                return res;
            }
            else if (a == 1)
            {
                res = 1;
                return res;
            }
            else if (a < n)
            {
                res = (n / a) ; //Что здесь тогда
                return res;
            }
            else
            {
                res = ((a % n) );
                return res;
            }


        }
И подскажите еще, почему в результате выдает 93? при а=3,n=121. Должно ведь выдавать 1
Код:
 double res2 =Math.Pow(a, (n - 1) / 2);
                     double  r=res2%n;
                      Console.WriteLine("res2  = {0}" , r);

Последний раз редактировалось Вероника99; 17.05.2016 в 17:55.
Вероника99 вне форума Ответить с цитированием
Старый 17.05.2016, 18:13   #9
p51x
Старожил
 
Регистрация: 15.02.2010
Сообщений: 15,695
По умолчанию

Все по той же причине. Не (n/a), а Yakobi(n, a)
p51x вне форума Ответить с цитированием
Старый 17.05.2016, 18:36   #10
Вероника99
Форумчанин
 
Регистрация: 15.12.2013
Сообщений: 414
По умолчанию

Цикл перебирает n, в теле цикла проверяется n на нечетность и составное ли n,тогда вызывается функция Yakobi
Код:
static int Yakobi(int a, int n)
        {
            if (a < 0)
            {
                int res = Yakobi(-a, n) * (int)Math.Pow(-1, (n - 1) / 2);
                return res;
            }
            else if (a % 2 == 0)
            {
                int res = Yakobi(a / 2, n) * (int)Math.Pow(-1, (n * n - 1) / 8);
                return res;
            }
            else if (a == 1)
            {
                int res = 1;
                return res;
            }
            else if (a < n)
            {
                int res = Yakobi(n, a) * (int)(Math.Pow(-1, (((a - 1) / 2) * ((n - 1) / 2))));
                return res;
            }
            else
            {
                int res = Yakobi(a % n, n);
                return res;
            }
        }
Как все таки правильно осуществить проверку левого выражения?
Код:
for (int n = 120; n < 125; n++)
            {
             
                if (n % 2 != 0) 
                {
                    if (simple(n) == 0) 
                    {
 
                       Console.WriteLine("Number  = {0}", ((Math.Pow(x, (n - 1) / 2))) % n);
...
                    }
                }
             
          }

Последний раз редактировалось Вероника99; 17.05.2016 в 22:41.
Вероника99 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Метод Эйлера Anubys Общие вопросы C/C++ 2 17.05.2011 16:51
Метод Эйлера RoKSport Паскаль, Turbo Pascal, PascalABC.NET 5 12.02.2011 12:45
Формула Эйлера Европеец Общие вопросы C/C++ 2 13.11.2009 12:07
Круги Эйлера NecRomant Общие вопросы Delphi 2 17.12.2008 15:07