A
Длинна полупростого числа
Size: a a a
2021 January 16
A
Я подразумеваю, что мне достаточно найти только 1 из множителей полупростого числа
A
Второй находится делением полупростого на результат алгоритма
A
И первый множитель находится в промежутке от 1 до логарифма Н
A
Это точно
DP
почему log а не sqrt?
A
Да, точно
A
Корень
A
Внимание пропадает
A
N < sqrt(длинны входного числа)
A
Можно доказать, что брейнфак не покрывает промежуток от 1 до N за f(n, m).
Где f - функция сложности,
m - затрачиваемая асимптотика памяти,
n - затрачиваемая асимптотика ресурсов процессора (количество тактов)
Где f - функция сложности,
m - затрачиваемая асимптотика памяти,
n - затрачиваемая асимптотика ресурсов процессора (количество тактов)
DP
попытаюсь собрать твою идею
"я хочу узнать можно ли искать множители числа если оно составлено из перемножения двух простых чисел, используя программу на брейнфако-подобном языке с линейным кодом, и как зависит максимальное число которое можно разложить используя програму определенной длины линейного кода"
"я хочу узнать можно ли искать множители числа если оно составлено из перемножения двух простых чисел, используя программу на брейнфако-подобном языке с линейным кодом, и как зависит максимальное число которое можно разложить используя програму определенной длины линейного кода"
DP
Aycon
Можно доказать, что брейнфак не покрывает промежуток от 1 до N за f(n, m).
Где f - функция сложности,
m - затрачиваемая асимптотика памяти,
n - затрачиваемая асимптотика ресурсов процессора (количество тактов)
Где f - функция сложности,
m - затрачиваемая асимптотика памяти,
n - затрачиваемая асимптотика ресурсов процессора (количество тактов)
все это упрощается если код линейный. тогда и память занимаемая ограничена тем же значением
A
Пусть m = const, тогда нужно доказать, что существует достаточно большое входное число, что область значений алгоритма покрывается не меньше, чем за время, сопостовимое с факторизацией брутфорсом.
A
Но я бы предпочёл найти такой алгоритм, для которого это неверно
A
Т. е. найти алгоритм факторизации приемлемой сложности для разложения чисел от 1024 бит и больше на обыкновенном компьютере
A
Кароч я спать, кому интересно - пишите или в лс или ответом, а то у меня уведомления отключены
A
На самом деле это будет всё ещё не строгое доказательство ибо алгоритм должен покрывать гораздо меньшую область чем корень из полупростого числа
DP
Aycon
Пусть m = const, тогда нужно доказать, что существует достаточно большое входное число, что область значений алгоритма покрывается не меньше, чем за время, сопостовимое с факторизацией брутфорсом.
лучшее что ты можешь сделать - эмпирически найти закономерность.
типа если число N бит, то программу короче K бит его не раскладывает.
и нарисовать график и предположить как он будет вести себя дальше.
реально ты можешь решить ситуации для 30-60 бит всего лишь. никаких 1кб.
типа если число N бит, то программу короче K бит его не раскладывает.
и нарисовать график и предположить как он будет вести себя дальше.
реально ты можешь решить ситуации для 30-60 бит всего лишь. никаких 1кб.
A
Хотя бы потому, что он должен давать только простое число на выходе