Факторизация действительно больших чисел в C - PullRequest
Новая
       47

Факторизация действительно больших чисел в C

0 голосов
/ 16 марта 2019

Я пишу статью о важности простых чисел в современной криптографии.Я хочу разработать небольшое приложение, показывающее, сколько времени потребуется программе, написанной на C (на низкоуровневом языке, по крайней мере для меня), чтобы разложить составное число в его основные множители.Я придумал простой алгоритм для этого, но столкнулся с проблемой:

Я бы хотел, чтобы пользователь мог печатать гигантские числа, например: 7777777777777777777777777772

Итак, компьютерпотребовалось бы несколько часов, чтобы обработать это, показывая, насколько хороша наша криптография на основе простых чисел.

Но в C самый большой тип данных, который я смог найти, был LONG , который достигает 2147483646.

Ребята, вы знаете, как я могу набрать и обработать большое число в C?

Заранее спасибо

Ответы [ 3 ]

1 голос
/ 16 марта 2019

Факторизация действительно больших чисел
Я бы хотел, чтобы пользователь мог печатать гигантские числа, например: 7777777777777777777777777772

Это 93-разрядное число, а не такое гигантскоеТаким образом, можно было бы упростить грубое форсирование этого.C действительно определяет 64-битные типы, но помимо этого вы сами по себе.

Эта скромная факторизация, которую я бы оценил, может занять несколько минут.

https://www.dcode.fr/prime-factors-decomposition сообщаетответ за секунды.

Конечно, много улучшения могут быть достигнуты. 

unsigned __int128 factor(unsigned __int128 x) {
  if (x <= 3) {
    return x;
  }
  if (x %2 == 0) return 2;
  for (unsigned __int128 i = 3; i <= x/i; i += 2) {
    static unsigned long n = 0;
    if (++n >= 100000000) {
      n = 0;
      printf(" %llu approx %.0f\n", (unsigned long long) i, (double)(x/i));
      fflush(stdout);
    }
    if (x%i == 0) {
      return i;
    }
  }
  return x;
}

void factors(unsigned __int128 x) {
  do {
    unsigned __int128 f = factor(x);
    printf("%llu approx %.0f\n", (unsigned long long) f, (double)x);
    fflush(stdout);
    x /= f;
  } while (x > 1);
}

void factors(unsigned __int128 x) {
  do {
    unsigned __int128 f = factor(x);
    printf("approx %0.f approx %.0f\n", (double) f, (double)x);
    fflush(stdout);
    x /= f;
  } while (x > 1);
}

Вывод 

approx 2 approx 7777777777777778308713283584
approx 2 approx 3888888888888889154356641792
approx 487 approx 1944444444444444577178320896
approx 2687 approx 3992699064567647864619008
 99996829 approx 14859790387308
 199996829 approx 7429777390798
 299996829 approx 4953158749339
 399996829 approx 3714859245385
 499996829 approx 2971882684351
 ...
 38399996829 approx 38696146902
 38499996829 approx 38595637421
approx 1485931918335559335936 approx 1485931918335559335936

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

0 голосов
/ 16 марта 2019

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

Я считаю, что это должно дать вам возможность получить где-то около 4294967295 (max_int) до степени хх, являющейся местами, которые вы определяете в структуре 

typedef struct big_number{
    int thousands;
    int millions;
    int billions;
}

//Then do some math
big_number add(big_number n1, big_number n2){
    int thousands = n1.thousands + n2.thousands; 
    int millions = n1.millions + n2.millions;
    //etc... (note each part of your struct will have a maximum value of 999
    if(thousands > 999){
         int r = thousands - 999;
         millions += r; //move the remainder up
    }
}
0 голосов
/ 16 марта 2019

Так же, как вы делаете это на бумаге. Вы разбиваете число на части и используете длинное деление, длинное сложение и длинное умножение.

Пожалуй, самый простой способ - сохранить число в виде базовой строки 10 и написать код для выполнения всех необходимых операций с этими строками. Вы будете делать сложение с переносками так же, как на бумаге. Умножение будет выполнено с умножением одной цифры в сочетании с сложением (которое вы бы уже использовали). И так далее.

Для этого существует множество библиотек, таких как библиотека MPZ libgmp и библиотека BN OpenSSL.

...