Перейти к содержимому


Фотография

RSA

асиметричное шифрование криптография

  • Авторизуйтесь для ответа в теме
Сообщений в теме: 32

#1 Оффлайн   HeroBrine1st

HeroBrine1st
  • Пользователи
  • Сообщений: 76
  • Уровень сигнала: 0%
  • В игре: 0 час. 0 мин.

Награды

        

Отправлено 24 Апрель 2018 - 20:12

Оптимизировал возведение в степень по модулю. Работает с большими числами очень быстро и хорошо, вероятность получения inf как результат степени и остатка от деления 0 минимальна.

От метачисел избавился, теперь - чистая Lua.

(Генератор ключей я взял с одного форума разработчиков, сам 2 часа бился над алгоритмом).

Код библиотеки:

local RSA = {}
local primes = { --таблица простых чисел до 1013
    2,      3,      5,      7,      11,     13,     17,     19,     23,     29,
    31,     37,     41,     43,     47,     53,     59,     61,     67,     71,
    73,     79,     83,     89,     97,     101,    103,    107,    109,    113,
    127,    131,    137,    139,    149,    151,    157,    163,    167,    173,
    179,    181,    191,    193,    197,    199,    211,    223,    227,    229,
    233,    239,    241,    251,    257,    263,    269,    271,    277,    281,
    283,    293,    307,    311,    313,    317,    331,    337,    347,    349,
    353,    359,    367,    373,    379,    383,    389,    397,    401,    409,
    419,    421,    431,    433,    439,    443,    449,    457,    461,    463,
    467,    479,    487,    491,    499,    503,    509,    521,    523,    541,
    547,    557,    563,    569,    571,    577,    587,    593,    599,    601,
    607,    613,    617,    619,    631,    641,    643,    647,    653,    659,
    661,    673,    677,    683,    691,    701,    709,    719,    727,    733,
    739,    743,    751,    757,    761,    769,    773,    787,    797,    809,
    811,    821,    823,    827,    829,    839,    853,    857,    859,    863,
    877,    881,    883,    887,    907,    911,    919,    929,    937,    941,
    947,    953,    967,    971,    977,    983,    991,    997,    1009,   1013,
}
local primes_start = 30 -- начальный индекс рандомизации rsa_p и rsa_q
local function modulePow(n1,n2,m) --возведение в степень по модулю
    local c = 1
    for i = 1, n2 do
        c = (c*n1)%m
    end
    return c
end

function RSA.getkey()
  rsa_e = 0

  rsa_p = primes[math.random(primes_start,#primes)]
  rsa_q = rsa_p

  while rsa_q == rsa_p do
      rsa_q = primes[math.random(primes_start,#primes)]
  end

  rsa_n = rsa_p*rsa_q
  rsa_phi = (rsa_p-1)*(rsa_q-1)

  while rsa_e == 0 do
      local prime = primes[math.random(1,#primes)]
      if rsa_phi%prime > 0 then
          rsa_e = prime
      end
  end

  for i = 2, rsa_phi/2 do
      if ((i*rsa_phi)+1)%rsa_e == 0 then
          rsa_d = ((i*rsa_phi)+1)/rsa_e
          break
      end
  end
  local public = {rsa_e,rsa_n}
  local private = {rsa_d,rsa_n}
  return private, public
end

function RSA.encrypt(number,pE,pN)
  return modulePow(number,pE,pN)
end

function RSA.decrypt(number,sD,sN)
  return modulePow(number,sD,sN)
end

return RSA

Методы:

 

RSA.getkey(): table,table - возвращает 2 таблицы с приватным (секретным) и публичным ключами.

Каждая таблица имеет 2 числа, в последующих функциях можно просто использовать table.unpack и вставлять нужную таблицу

 

RSA.encrypt(number:number, public_E, public_N): number - возвращает зашифрованное число, которое можно расшифровать только закрытым ключом

RSA.decrypt(cryptedNumber:number,secret_E,secret_N): number - возвращает дешифрованное число, которое можно использовать, например, как сеансовый ключ (для этого идеально подходит кодирование степени какого-либо числа) и шифровать с помощью, например, более производительной сети Фейстеля, выложенной ранее.

 

Кто-то скажет, что есть дата-карта, но в планшетах нет лишних слотов для нее.


Сообщение отредактировал HeroBrine1st: 25 Апрель 2018 - 17:02

  • Totoro, eu_tomat, ECS и еще 1 это нравится

#2 Оффлайн   Zer0Galaxy

Zer0Galaxy
  • Гуру
  • Сообщений: 1 228
  • Уровень сигнала: 0%
  • В игре: 0 час. 0 мин.

Награды

   5                              

Отправлено 25 Апрель 2018 - 15:22

Когда-то давным-давно, когда в майне были только компьютеркрафтовые компы, а метанума и в помине не было, реализовывал я RSA-подобный алгоритм похожим образом. Тогда помню была проблема не с TLWY, а с банальным переполнением, тем не менее ее как то удалось решить. Если в руинах старого хлама найду тот жесткий диск, выложу.



#3 Оффлайн   HeroBrine1st

HeroBrine1st
  • Автор темы
  • Пользователи
  • Сообщений: 76
  • Уровень сигнала: 0%
  • В игре: 0 час. 0 мин.

Награды

        

Отправлено 25 Апрель 2018 - 16:22

Оптимизировал алгоритм. Работает моментально, кодирует большие числа без намека на провисание.

Избавился от метачисел, теперь библиотека работает на чистом Lua.

Дополнил таблицу простых чисел.


Сообщение отредактировал HeroBrine1st: 25 Апрель 2018 - 16:22

  • Totoro это нравится

#4 Оффлайн   Zer0Galaxy

Zer0Galaxy
  • Гуру
  • Сообщений: 1 228
  • Уровень сигнала: 0%
  • В игре: 0 час. 0 мин.

Награды

   5                              

Отправлено 25 Апрель 2018 - 17:19

Я понимаю, что предложенный алгоритм учебно-тренировочный, но всё же хочу заметить: криптостойкость RSA-алгоритма основана на вычислительной сложности факторизации больших чисел. Другими словами, если взломщику удастся найти делитель числа rsa_n, которое входит в открытый ключ, то и секретный ключ вычислить не составит большого труда. В предложенном варианте реализации используются лишь первые несколько простых чисел, а значит и факторизация выполняется на раз-два. Рассмотри возможность нахождения очень больших простых чисел. Эту задачу мне в свое время не удалось решить.



#5 Оффлайн   HeroBrine1st

HeroBrine1st
  • Автор темы
  • Пользователи
  • Сообщений: 76
  • Уровень сигнала: 0%
  • В игре: 0 час. 0 мин.

Награды

        

Отправлено 25 Апрель 2018 - 18:33

Рассмотри возможность нахождения очень больших простых чисел.

Попытался решетом Эратосфена. Получил ошибку заполнения ОЗУ для n = 10 000 000.



#6 Оффлайн   HeroBrine1st

HeroBrine1st
  • Автор темы
  • Пользователи
  • Сообщений: 76
  • Уровень сигнала: 0%
  • В игре: 0 час. 0 мин.

Награды

        

Отправлено 25 Апрель 2018 - 18:48

Попробовал от 990000 до 1000000 использовать простые числа. Шифровка - нормально, дешифровка - too long without yielding.

Поставил os.sleep(0) - получил зависнувший сервер (из опенкомпов, а не хост)

UPD: от 50000 до 100000 - все так же


Сообщение отредактировал HeroBrine1st: 25 Апрель 2018 - 19:01


#7 Онлайн   eu_tomat

eu_tomat
  • Хранители Кода
  • Сообщений: 875
  • Уровень сигнала: 6,53%
  • В игре: 45 час. 45 мин.

Награды

                          

Отправлено 25 Апрель 2018 - 19:02

Попробовал от 990000 до 1000000 использовать простые числа. Шифровка - нормально, дешифровка - too long without yielding.

Что и неудивительно с такой реализацией:

local function modulePow(n1,n2,m) --возведение в степень по модулю
    local c = 1
    for i = 1, n2 do
        c = (c*n1)%m
    end
    return c
end

На помощь придут Алгоритмы быстрого возведения в степень

#8 Оффлайн   HeroBrine1st

HeroBrine1st
  • Автор темы
  • Пользователи
  • Сообщений: 76
  • Уровень сигнала: 0%
  • В игре: 0 час. 0 мин.

Награды

        

Отправлено 25 Апрель 2018 - 19:40

Немного погуглив, я заметил, что существуют онлайн-сервисы разложения числа на множители. Вставив туда число вида 42894984343598, разложило примерно за полминуты.

 

То есть можно просто записать сниффером все, включая обмен ключами (я для чего и пишу библиотеку - для коммуникации внутри сети Zn, отсеивая атаку man in-the-middle), а затем в таком сервисе разложить число, получить нужный множитель и найти секретный ключ.

И тут встает вопрос: потянет ли OC числа, которые не потянут такие сервисы? Нет.

 

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


Сообщение отредактировал HeroBrine1st: 25 Апрель 2018 - 19:40


#9 Онлайн   eu_tomat

eu_tomat
  • Хранители Кода
  • Сообщений: 875
  • Уровень сигнала: 6,53%
  • В игре: 45 час. 45 мин.

Награды

                          

Отправлено 25 Апрель 2018 - 20:02

На практике RSA используется в основном для передачи временных ключей симметричного шифрования. То есть, длительное декодирование выполняется лишь в начале сеанса, а дальше используются более скоростные алгоритмы. В этом случае на длинне ключа не экономят. Минута на взлом это очень мало даже по меркам Майнкрафта. Замена ключей хотя бы раз в день выглядит интереснее. Хотя, для стационарных систем замена должна быть не чаще раза в месяц.

Помня о трудностях генерации устойчивых к взлому ключей, я бы вообще избавился от генерации ключей своими силами. Наверное, проще будет воспользоваться стндартными генераторами, изучить формат файлов и вытащить из них ключи, а в OC сосредоточиться только на возведении в степень по модулю, и исключительно для передачи временных ключей более шустрых методов шифрования.

Что же касается сети Zn, то главная её проблема даже не в перехвате сообщений, а в возможности легко обрушить всю сеть обычным спамом.
  • ECS и davial это нравится

#10 Оффлайн   Totoro

Totoro
  • Хранители Кода
  • Сообщений: 1 734
  • Уровень сигнала: 0,32%
  • В игре: 2 час. 13 мин.

Награды

                                      

Отправлено 26 Апрель 2018 - 11:18

Что же касается сети Zn, то главная её проблема даже не в перехвате сообщений, а в возможности легко обрушить всю сеть обычным спамом.

 

Справедливости ради, спамом можно обрушить любую сеть в Майнкрафте.



#11 Оффлайн   NEO

NEO
  • Пользователи
  • Сообщений: 1 746
  • Уровень сигнала: 5,2%
  • В игре: 36 час. 25 мин.
  • ГородСолнце

Награды

3                           

Отправлено 26 Апрель 2018 - 22:40

Справедливости ради, спамом можно обрушить любую сеть в Майнкрафте.

справедливости ради, обычную вайфайку спамом не сломать

Zn слишком дырявая и не проработанная


Сообщение отредактировал NEO: 27 Апрель 2018 - 11:29


#12 Оффлайн   RccHD

RccHD
  • Пользователи
  • Сообщений: 169
  • Уровень сигнала: 18,51%
  • В игре: 129 час. 42 мин.

Награды

        

Отправлено 04 Май 2018 - 11:13

Раз уж ты взялся писать алгоритм RSA, то неплохо было бы сначала изучить другие более простые алгоритмы.

Я имею в виду алгоритм возведения в степень

Оптимизировал возведение в степень по модулю. Работает с большими числами очень быстро и хорошо


Твоя реализация работает очень медленно (за линейное время), что в итоге будет причиной зависаний компа на целые минуты, а то и часы.
Вот, смотри сам: https://ideone.com/v48E18

Считаю нужным предложить правильную реализацию, которая работает за логарифмическое время (в миллионы или даже в миллиарды раз быстрее)
Вот: https://ideone.com/RyGdbH


P.S. сравни время работы двух реализаций на ideone. (У меня показывает 0.71s VS 0.00s)

P.S.S. подробнее об алгоритме возведения в степень тут: http://e-maxx.ru/algo/binary_pow
 
  • Alex, Totoro, ECS и еще 1 это нравится

#13 Оффлайн   qwertyMAN

qwertyMAN
  • Пользователи
  • Сообщений: 1 427
  • Уровень сигнала: 0,15%
  • В игре: 1 час. 3 мин.
  • ГородCity17

Награды

                             

Отправлено 04 Май 2018 - 15:37

@HeroBrine1st а зачем тебе статичная таблица простых чисел, если можно легко написать генератор этих чисел? И будет у тебя сколько хочешь таких чисел. Генерация не займёт много времени.



#14 Оффлайн   ECS

ECS
  • Гуру
  • Сообщений: 200
  • Уровень сигнала: 0,59%
  • В игре: 4 час. 10 мин.
  • ГородСанкт-Петербург

Награды

10                     

Отправлено 05 Май 2018 - 10:43

Считаю нужным предложить правильную реализацию, которая работает за логарифмическое время (в миллионы или даже в миллиарды раз быстрее)


Вставлю свои пять копеек, чтобы правильность была еще более правильной. Ох уж эта правильность... В общем, так как время, затрачиваемое на вызов функций в Lua значительно превышает время осуществления иных операций, следует использовать итеративный метод расчетов вместо рекурсивного. Кроме того, как вполне грамотно заметил товарищ с e-maxx.ru, для определения четности числа имеет смысл заменить "n % 2 == 0" на "n & 1 == 0". В итоге времечко сократится еще втрое. Собсна, пруф: https://ideone.com/t9Yv5F

Сообщение отредактировал ECS: 05 Май 2018 - 11:03

  • Totoro это нравится

#15 Оффлайн   HeroBrine1st

HeroBrine1st
  • Автор темы
  • Пользователи
  • Сообщений: 76
  • Уровень сигнала: 0%
  • В игре: 0 час. 0 мин.

Награды

        

Отправлено 05 Май 2018 - 16:32

@HeroBrine1st а зачем тебе статичная таблица простых чисел, если можно легко написать генератор этих чисел? И будет у тебя сколько хочешь таких чисел. Генерация не займёт много времени.

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

На крайняк можно в /boot/ записать require("RSA") конечно, но это уже вмешательство в openos



#16 Оффлайн   HeroBrine1st

HeroBrine1st
  • Автор темы
  • Пользователи
  • Сообщений: 76
  • Уровень сигнала: 0%
  • В игре: 0 час. 0 мин.

Награды

        

Отправлено 05 Май 2018 - 17:03

Использовав третий метод в сравнении ECS (4й уже для lua 5.3) я нашел странную вещь - при больших числах выходное значение дешифрования отлично от входного значения шифрования.

 

Вот код:

Спойлер

 

И выход в opencomputers (lua 5.2) - http://prntscr.com/je2nnp

(после вызова команды первое число - зашифрованное число, второе - расшифрованное)

Шифровал я число 65536. А получил совершенно другие числа.

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

UPD: с вторым методом так же

UPD2: с простыми числами 3855000-3859999 все так же. При уменьшении до 1-1000 все становится нормально.


Сообщение отредактировал HeroBrine1st: 05 Май 2018 - 17:10


#17 Онлайн   eu_tomat

eu_tomat
  • Хранители Кода
  • Сообщений: 875
  • Уровень сигнала: 6,53%
  • В игре: 45 час. 45 мин.

Награды

                          

Отправлено 05 Май 2018 - 17:26

Вставлю свои пять копеек, чтобы правильность была еще более правильной. Ох уж эта правильность... В общем, так как время, затрачиваемое на вызов функций в Lua значительно превышает время осуществления иных операций, следует использовать итеративный метод расчетов вместо рекурсивного. Кроме того, как вполне грамотно заметил товарищ с e-maxx.ru, для определения четности числа имеет смысл заменить "n % 2 == 0" на "n & 1 == 0". В итоге времечко сократится еще втрое. Собсна, пруф: https://ideone.com/t9Yv5F

А я вставлю ещё копейку. Не знаю, как в текущей версии OpenComputers, но около года назад я проводил замеры, и не обнаружил разницы во времени исполнения разной арифметики типа + - * / % & | >> <<
Зато обращение к переменным, адресация в таблице, а особенно вызов функций обходились заметно дороже, подтверждаю.
 

@HeroBrine1st а зачем тебе статичная таблица простых чисел, если можно легко написать генератор этих чисел? И будет у тебя сколько хочешь таких чисел. Генерация не займёт много времени.

Очень спорно. Главная проблема текущей реализации в том, что простых чисел в имеющейся таблице мало, от чего криптоустойчивость ключей очень низкая. Диапазон чисел требуется сильно расширить и либо как-то хранить заранее вычисленные числа, тратя дисковое пространство, либо в нужный момент вычислять, тратя процессорное время. А вычисляться они будут долго. Особенно на Luа. Особенно, когда большие числа потребуют длинной арифметики. А они потребуют.

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

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

я нашел странную вещь - при больших числах выходное значение дешифрования отлично от входного значения шифрования.

Похоже на выход за пределы целых чисел. Арифметика с плавающими числами имеет ограниченнную точность и совершенно не подходит для шифрования RSA. Выход в использовании длинной арифметики. Нужны три операции: умножение, возведение в квадрат и взятие остатка от деления.

#18 Оффлайн   HeroBrine1st

HeroBrine1st
  • Автор темы
  • Пользователи
  • Сообщений: 76
  • Уровень сигнала: 0%
  • В игре: 0 час. 0 мин.

Награды

        

Отправлено 14 Май 2018 - 20:38

Длинную арифметику написать не смог. https://github.com/O...gint/bigint.lua не слушается.

Зато есть генератор простого числа на тесте Ферма. И у него сильно ограничен диапазон из-за отсутствия длинной арифметики.

Раскомментировав последние строки, получите код для проверки алгоритма.

Спойлер

Сообщение отредактировал HeroBrine1st: 14 Май 2018 - 20:38


#19 Оффлайн   Zer0Galaxy

Zer0Galaxy
  • Гуру
  • Сообщений: 1 228
  • Уровень сигнала: 0%
  • В игре: 0 час. 0 мин.

Награды

   5                              

Отправлено 15 Май 2018 - 12:39

Так может тебе помочь написать длинную арифметику? На подобии метачисел, только на основе таблиц, а не строк?



#20 Оффлайн   HeroBrine1st

HeroBrine1st
  • Автор темы
  • Пользователи
  • Сообщений: 76
  • Уровень сигнала: 0%
  • В игре: 0 час. 0 мин.

Награды

        

Отправлено 15 Май 2018 - 15:26

Так может тебе помочь написать длинную арифметику? На подобии метачисел, только на основе таблиц, а не строк?

Я бы не отказался



#21 Оффлайн   Zer0Galaxy

Zer0Galaxy
  • Гуру
  • Сообщений: 1 228
  • Уровень сигнала: 0%
  • В игре: 0 час. 0 мин.

Награды

   5                              

Отправлено 15 Май 2018 - 16:26

Это будет целочисленная арифметика. Какие нужны операции и нужны ли отрицательные числа?



#22 Оффлайн   HeroBrine1st

HeroBrine1st
  • Автор темы
  • Пользователи
  • Сообщений: 76
  • Уровень сигнала: 0%
  • В игре: 0 час. 0 мин.

Награды

        

Отправлено 16 Май 2018 - 21:10

Это будет целочисленная арифметика. Какие нужны операции и нужны ли отрицательные числа?

Нужны три операции: умножение, возведение в квадрат и взятие остатка от деления

Отрицательные числа не нужны.



#23 Оффлайн   jammer312

jammer312
  • Пользователи
  • Сообщений: 62
  • Уровень сигнала: 127,17%
  • В игре: 890 час. 55 мин.

Награды

           

Отправлено 16 Май 2018 - 23:16

Не уверен, насколько эффективно и верно предлагаемое, но оно весьма просто. Ну и я на практике не проверял, это просто на ходу придуманный вариант.
Сначала надо выяснить, какое максимальное целое число можно хранить в переменной в луа без потери точности, пусть это будет N, тогда n=sqrt(N) (округленное вниз).
Длинное число реализуем как индексированную таблицу произвольной длины, в которой в каждой ячейке хранится число от 0 до n, сие есть запись числа в позиционной системе счисления по основанию n+1. Тогда операции можно реализовать по аналогии с сложением/вычитанием/делением/умножением столбиком (с учетом того, что система счисления уже не десятичная, конечно же), при этом операции над разрядами - просто арифметические операторы луа. Выбор основания гарантирует, что при сложении, вычитании и умножении разрядов переполнения или потери точности не будет. Взятие остатка от деления можно реализовать через деление, умножение и вычитание (ессно целочисленное) (a%b = a-(a/b)*b).

 

P.S. Основание у системы счисления выбрано согласно двум соображениям: 1. оно должно быть как можно больше, чтобы кол-во разрядов, а следовательно - кол-во операций при умножении и делении, было как можно меньше; 2. оно должно быть таким, чтобы при самой "опасной" операции - умножении - не происходило потери точности (ну или переполнения, будь в луа целочисленная арифметика).
Ну и "какое максимальное целое число можно хранить в переменной в луа без потери точности" сформулировано немного некорректно, я имел ввиду такое число N, что все числа от 0 до N представимы в переменной. Скорее всего с этой оценкой я переосторожничал, но лучше недооценить, чем переоценить.


Сообщение отредактировал jammer312: 16 Май 2018 - 23:23


#24 Оффлайн   Zer0Galaxy

Zer0Galaxy
  • Гуру
  • Сообщений: 1 228
  • Уровень сигнала: 0%
  • В игре: 0 час. 0 мин.

Награды

   5                              

Отправлено 17 Май 2018 - 09:37

...

Опытным путем установил, что основание системы счисления должно быть порядка 10^7

В результате получилась вот такая либа. По сути она аналогична метачислам, только целочисленна.

Но есть одна проблемка: меня одолела лень и деление (а вместе с ним остаток от деления и возведение в степень по модулю) осталось нереализованным.

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

Пример вычисления факториала:

QKhFiwd.png

Кто не верит, может проверить на калькуляторе  :)

 

PS: вот думаю, нужна ли функция генерации случайного метачисла?


Сообщение отредактировал Zer0Galaxy: 17 Май 2018 - 10:03


#25 Оффлайн   Zer0Galaxy

Zer0Galaxy
  • Гуру
  • Сообщений: 1 228
  • Уровень сигнала: 0%
  • В игре: 0 час. 0 мин.

Награды

   5                              

Отправлено 17 Май 2018 - 12:45

Длинную арифметику написать не смог. https://github.com/O...gint/bigint.lua не слушается.

А что не так с bigint? По тестировал. Вроде всё нормально



#26 Оффлайн   HeroBrine1st

HeroBrine1st
  • Автор темы
  • Пользователи
  • Сообщений: 76
  • Уровень сигнала: 0%
  • В игре: 0 час. 0 мин.

Награды

        

Отправлено 17 Май 2018 - 13:10

А что не так с bigint? По тестировал. Вроде всё нормально

Жалуется на то, что получило значение, отличное от числа. Не знаю, как это фиксить, ибо я передаю число.


Сообщение отредактировал HeroBrine1st: 17 Май 2018 - 16:58


#27 Оффлайн   Zer0Galaxy

Zer0Galaxy
  • Гуру
  • Сообщений: 1 228
  • Уровень сигнала: 0%
  • В игре: 0 час. 0 мин.

Награды

   5                              

Отправлено 17 Май 2018 - 13:19

Пример кода можно?



#28 Оффлайн   HeroBrine1st

HeroBrine1st
  • Автор темы
  • Пользователи
  • Сообщений: 76
  • Уровень сигнала: 0%
  • В игре: 0 час. 0 мин.

Награды

        

Отправлено 17 Май 2018 - 17:02

Пример кода можно?

Кажется, я понял, в чем ошибка. Рекурсивный метод вызывает сам себя, а с ним вызывается и преобразование числа(уже таблицы) в bigint-таблицу. Вот тут и происходит ошибка.



#29 Оффлайн   HeroBrine1st

HeroBrine1st
  • Автор темы
  • Пользователи
  • Сообщений: 76
  • Уровень сигнала: 0%
  • В игре: 0 час. 0 мин.

Награды

        

Отправлено 17 Май 2018 - 17:07

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

Спойлер

 

И сама ошибка - http://prntscr.com/jj3jml

76 строка, затем 31 и ошибка происходит в рекурсивном методе method2.

Вот же ответ обычной арифметики (Удалил строки с 5й по 7ю) за ~0.3 секунды - http://prntscr.com/jj3kme


Сообщение отредактировал HeroBrine1st: 17 Май 2018 - 17:09


#30 Оффлайн   Zer0Galaxy

Zer0Galaxy
  • Гуру
  • Сообщений: 1 228
  • Уровень сигнала: 0%
  • В игре: 0 час. 0 мин.

Награды

   5                              

Отправлено 18 Май 2018 - 10:39

Так это банальный TLWY. Ясно, что длинная арифметика медленнее обычной, вот и не укладываешься в отведенные три секунды. Натыкай где можно sleep(0)







Темы с аналогичным тегами асиметричное шифрование, криптография

Количество пользователей, читающих эту тему: 0

0 пользователей, 0 гостей, 0 анонимных