在$ \ mathbb {Z} _p $中查找小型生成器的相互离散对数的难度

假设您想选择一个质数$ p $来查找例如$ \ mathbb {Z} _p $中的$ \ log_2（3）$预期至少与$ \ mathbb {Z} _p $中的一般离散对数问题一样困难，或者至少两个不可行的问题，例如因为您要使用$ g = 2，h = 3，p $作为某些方案的域参数。 $ p $必须有多大？指数$ {（k_i）} _ {i = 0} ^ n $，这样，对于所有$ i = 0..n $，整数$ FE2I（g ^ {k_i} \ pmod p）$是$ B $-平滑（并且具有幂次幂，并且指数形成向量$ v_i $的指数不能表示为任何其他$ v_j $的线性组合等）。 {Z} _p $ hard，需要选择一个素数$ p $，这样，对于任何较小的素数$ B $，光滑的整数$ B $或整数$ \ pi（B）$小于$ B $的素数必须太大。给定一个近似值，一个小于$ p $的数字是$ B $-平滑的概率约为$ u ^ {-u} $，其中$ u = \ frac {\ ln（p）} {\ ln（B）} $，以及$ \ pi（B）\ approx \ frac {B} {\ ln（B）} $得到最高$ 2 ^ {-128} $的概率$ \ mathbb {Z} _p $中的随机元素是$ B $平滑的，或者您必须选择大于$ 2 ^的$ B $ {128} $：th素数，如果$ p \ approx 2 ^ {3645} $。

因此，假定3072位素数通常（超过）足以满足需要128位强DLP方案，对于依赖于为确定性地选择的小型发生器$ g $和$ h $计算$ \ log_g（h）$的难度的方案而言，4096位素数是否足够？ />
编辑：考虑到例如$ p = 2 ^ {4096}-3 ^ {2225} $是素数（表示$ \ log_2（3）= 4096（2225）^ {-1} \ bmod（p-1）$），并且是我的问题仅适用于可验证地随机生成的素数，$ \ log_2（3）$易于求解的素数有共同点吗？是否所有这类素数都以$ p = 2 ^ n-3 ^ m $的形式或其他易于检测的形式存在，或者是否有可能以保留$ \ log_2（3）$的知识的方式篡改这种素数


编辑2：考虑方程$ kp = 2 ^ n-3 ^ m $具有至少一个解$ k \ in \ mathbb {Z}，n，m \ in \ mathbb {Z} _ {p-1} $对于所有素数$ p> 3 $，关于篡改这些素数的问题是否可以表示为：是否可以计算$（2 ^ n-3 ^ m） / k $在$ \ mathbb {Z} $中的效率最高，因为$ 2 ^ n-3 ^ m $可能在$ \ mathbb {Z} _p $中计算，对于在适当范围内的任意$ k，n，m $？ 。

例如，将检查$ 2 ^ i3 ^ {-j} \ bmod p \ neq 1 $为$ 0 \ lt i，j \ le 2 ^ {48} $就足够了，还是可以为巨大的$ n，m $计算$（2 ^ n-3 ^ m）/ k $如果$ k $是另一个小素数的巨大力量？还有其他捷径吗？


编辑3：因为$ kp = 2 ^ n-3 ^ m $等于$ 1 + kp3 ^ {-m} = 2 ^ n3 ^ { -m} $，我们有$ n \ ln（2）-m \ ln（3）= \ ln（1 + kp3 ^ {-m}）$。如果$ kp $明显小于$ 3 ^ m $，我们将得到$ | n \ ln（2）-m \ ln（3）| \ lt \ epsilon $。但是，这将要求$ \ frac {\ ln（3）} {\ ln（2）} = \ frac {n} m + \ delta $和$ | \ delta | \ lt \ epsilon $，情况并非如此（因为$ \ epsilon $可以由$ -m $中的指数函数和$ \ frac {\ ln（3）} {\ ln（2）的分数展开来近似} $不是周期性的，其周期用$ \ phi（m）$划分为$ \大约m $个最高有效位）。

因此，如果$ 2 ^ {255} \ lt n \ lt 2 ^ {256} $，自然数没有解到$ kp = 2 ^ n-3 ^ m $，其中$ k $足够小，使得$ kp $小于$ 2 ^ {2 ^ {255 }} $。

接下来，假设$ C $是您可以在算术运算中表示的最大数字。如果$ k = \ prod_ {i = 0} ^ {l} p_i ^ {e_i} $每个$ p_i ^ {e_i} \ le \ frac {C} {p_i} $，则$的概率不可忽略通过从$ \ frac {（2 ^ n-3 ^ m）\ prod_ {j = 0，j \ neq i} ^ {l} p_j ^ {-e_j} \ pmod {p_i ^ {e_i + 1}} $ {p_i ^ {e_i}} $。但是，这仍然需要约束$ k \ lt C ^ {\ pi（C）} $，这仍然太小，不足以保证在给定$ p $的情况下可能不会计算$ n $和$ m $。 >