Re: [其他] 這應該算數位加密

[Desperato (Farewell)]

※ 引述《dotonbot (red)》之銘言：
: c=g^(t+j)^g^(t+j)
: 老王知道 c,g,t
: 老王是否能解出 g^j^g^j ?
: 解得出來可以去領一萬多的獎金
: https://twitter.com/NavCoin_Global/status/1064661972703154178


Note: a^b^c means a^(b^c), not (a^b)^c


Assume exp, log and real powers are computable

then by taking log_g and ^(1/g^t)

the question is equivalent to

Given g, t and d = (t+j)^(g^j), want j^(g^j)


For continuous case, if g > 1, t > 0 then

f(x) = (t+x)^(g^x) is an increasing funciton on x > 0

thus j = f^(-1)(d) and also j^(g^j) using method of finding root.



================================================================

Now we assume g, t and even j are all positive integers


log log f(x) = log (g^x log (t+x))
             = x log g + log log (t+x)

hence log log d = j log g + log log (t+j) >= j log g

and M = log log d / log g is an upper bound of j.


Find a prime p divide d, maybe try and error(?)

Write p^r || d, if p^r | d but p^(r+1) not | d.

Therefore d = (t+j)^(g^j) would have a large p-power divisor

say, p^r | d but p^(r+1) not | d

r can be found by dividing p many times.


since r = g^j ord_p(t+j) <= g^j log_p(t+j) <= g^j log_p(t+M)

thus log_g r - log_g log_p (t+M) <= j <= log_g r

log_g log_p (t+M) is not big, j has few possibilities, just try them all.

(actually r = g^j ord_p(t+j) can remove many invalid j)


這個做法的問題是，要是 t+j 好死不死質因數太大，或根本質數，那就QQ了

不過由於 g^j 肯定不小，比起 d 來說 t+j 應該沒那麼怪物就是


想超久結果找個質因數就解決了乾



--

嗯嗯ow o

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.7.188
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1542799195.A.DA3.html
推 arthurduh1  : 加密的題目, 考慮的如果是 discrete log
→ arthurduh1  : 一般來說是很難算的 (無法在多項式時間內算出)
原來如此，看來不能隨便取 log 或至少要直接幹實數 log XD
我看看要怎麼規避，其實我很多地方都沒考慮多項式時間啊orz
→ arthurduh1  : 其實題目不一定是 discrete log 啦, 但不管怎樣
→ arthurduh1  : 計算時間還是要考慮的
我覺得 mod 大有可為可是想不出來qw q
像上面那個找質數的計算時間真心很懸
都不整除可能可以上反元素，但沒想到做法
hensel lemma只能多項式超難過
計算時間不想好的話 說不定勘根四捨五入都比較快(?)
※ 編輯: Desperato (140.112.7.188), 11/21/2018 21:58:39
推 wohtp       : 可是他問的只是「能不能」…
→ wohtp       : 如果都是整數的話，窮舉法一定可以找到整數解，結案
→ wohtp       : *j的整數解
→ wohtp       : 當然原問題想問的肯定是有沒有好方法，然後他也其實
→ wohtp       : 沒限制整數，只能題目敘述太不用心了
→ Ricestone   : 他會想賭這個，就是覺得跟dlp等價吧...這作者還會想
→ Ricestone   : 聯絡說出不行的人
推 dotonbot    : 原問題後來補充說限制整數 他基本上就是想提供獎金
→ dotonbot    : 給提出好的解法的人