Существует ли лучшая нижняя граница для факторинга и дискретного логарифмирования?

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

В частности, имеет ли какая-либо из этих проблем более нижнюю границу линейной сложности?

@Suresh: следуя твоему совету, вот мой «ответ». Состояние нижних границ контура довольно удручающее. Вот «текущие записи»:

• $4n-4$$\{\land,\lor,\neg\}$$7n-7$$\{\land,\neg\}$$\{\lor,\neg\}$$\oplus_n(x)=x_1\oplus x_2\oplus\cdots\oplus x_n$
• $5n-o(n)$
• $3n-o(n)$$(7/3)n-o(1)$$3n-o(1)$
• $n^{3-o(1)}$$\{\land,\lor,\neg\}$
• $\Omega(n^2/\log n)$$2$$\Omega(n^2/\log^2 n)$$\Omega(n^{3/2}/\log n)$

Итак, ваш вопрос "В частности, есть ли у какой-либо из этих проблем более нижняя граница линейной сложности?" остается широко открытым (в случае цепей). Мой призыв ко всем молодым исследователям: вперед, эти «барьеры» не преодолимы! Но попробуйте мыслить «неестественно», в смысле Разборова и Рудича.