Обработка 3.3.7 Функция Кармайкла - PullRequest
Новая
       5

Обработка 3.3.7 Функция Кармайкла

0 голосов
/ 04 ноября 2018

Итак, я пытаюсь создать функцию carmichael для обработки некоторых вещей, связанных с шифрованием RSA, с которыми я играю, но функция modulo, похоже, дает много неправильных ответов. вот мой код: 

int carmichael(int n) {
  int checkIndex = 0;
  int m = 1;
  ArrayList<Integer> coprimes = findCoprimesLessThan(n);

  println(coprimes);

  for(m = 1; m < 50; m++){
    for(checkIndex = 0; checkIndex < coprimes.size(); checkIndex++){
      int a = coprimes.get(checkIndex);
      float mod = pow(a, m) % n;

      println(a, m, n, mod, pow(a, m), pow(a, m) % n);

      if (mod == 1) {
        continue;
      }
      if (mod != 1){
        break;
      }
      return m;
    }
  }
  return 1;
}

И для ввода, скажем, 31, он зацикливается навсегда (у меня он останавливается на 100 только по этой причине, поэтому он просто выводит 1, если он проходит через все 100 и ничего не находит), когда он должен давать 30. Я полагаю, что я сузил это до операции по модулю, не работающей с большими числами, поскольку это, кажется, проблема, например: когда a = 3, m = 30 и n = 31, мой оператор println дает следующее: 

3 30 31 18.0 2.05891136E14 18.0

и все это правильно за исключением по модулю, оно дает 18,0, когда должно быть 1,0. В любом случае, я не уверен, что смогу обойти это, даже выполняя «ручной модуль»: 

while(mod >= n){
  mod-= n;
}

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

1 Ответ

0 голосов
/ 05 ноября 2018

Полагаю, вы достигли предела точности с плавающей точкой.

Значения с плавающей точкой могут отслеживать только определенную точность. Попробуйте запустить этот пример программы: 

float one = 123456789;
float two = one + 1;
println(one == two);

Можно ожидать, что это напечатает false, но если вы запустите его, вы увидите, что вместо него будет напечатано true. Это потому, что мы находимся за пределами точности.

Чтобы обойти это, вы можете перейти на тип double. Двойные значения имеют ту же проблему, но с более высоким уровнем точности. 

double one = 123456789;
double two = one + 1;
println(one == two);

Возвращаясь к вашему коду, по умолчанию Обработка обрабатывает все как значение float. Это хорошо для большинства случаев, но если вам нужна большая точность, вам лучше переключиться на значение double. 

int a = 3;
int m = 30;
int n = 31;

double p = Math.pow(a, m);
println(p);

double mod = p % n;

println(mod);

Обратите внимание, что я использую Math.pow() вместо pow(). Функция Math.pow() происходит из Java и принимает и возвращает double значения вместо float значений.

(Кстати, это пример программы, о которой я говорил в комментариях.)

...