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

看板Math作者Desperato (Farewell)時間7年前 (2018/11/21 19:19)推噓3(3推 0噓 10→)

留言13則, 4人參與討論串2/2 (看更多)

※ 引述《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

11/21 20:10, 7年前 , 1^F

11/21 20:10, 1^F

→

arthurduh1

11/21 20:10, 7年前 , 2^F

11/21 20:10, 2^F

原來如此，看來不能隨便取 log 或至少要直接幹實數 log XD 我看看要怎麼規避，其實我很多地方都沒考慮多項式時間啊orz

→

arthurduh1

11/21 21:49, 7年前 , 3^F

11/21 21:49, 3^F

→

arthurduh1

11/21 21:50, 7年前 , 4^F

11/21 21:50, 4^F

我覺得 mod 大有可為可是想不出來qw q 像上面那個找質數的計算時間真心很懸都不整除可能可以上反元素，但沒想到做法 hensel lemma只能多項式超難過計算時間不想好的話說不定勘根四捨五入都比較快(?) ※ 編輯: Desperato (140.112.7.188), 11/21/2018 21:58:39

推

wohtp

11/21 23:53, 7年前 , 5^F

11/21 23:53, 5^F

→

wohtp

11/21 23:55, 7年前 , 6^F

11/21 23:55, 6^F

→

wohtp

11/21 23:55, 7年前 , 7^F

11/21 23:55, 7^F