算法及時計算，但快速驗證計算結果

我想給用戶一個隨機密鑰，要求他在這個密鑰上執行算法。算法的計算成本很高。應該不存在已知的解決方法來減少所需的計算時間。而且我應該能夠以非常高的成本驗證計算值是從我給出的關鍵字計算出來的。算法及時計算，但快速驗證計算結果

有沒有適合這種用途的算法？

來源

2014-01-10 Ski

我想你正在描述* public-key cryptography *，其中大整數的因式分解扮演着你引用的算法的角色。我建議求助於你最喜歡的搜索引擎。 –

採取兩個大素數。乘以它們。給用戶結果並讓他找到兩個主要因素。 –

您正在尋找NP難題。非常粗略地說，那些很難解決但很容易驗證。（大多數需要的不僅僅是一個隨機密鑰作爲輸入，但你可以使用該密鑰來說，種子一個隨機數生成器，用於生成一個圖並解決NP-hard圖問題。） – borrible

哦，是的，有。比特幣例如使用這樣的東西，它被稱爲Proof-of-work system，也看Hashcash。

對不起，我不能幫你實際的代碼，但應該有大量的開源資料。對於比特幣，根據我的理解，有一個很小的機會來快速完成這個工作證明，但平均來說非常困難。使用普通的電腦將需要不止幾十年。

來源

2014-01-10 15:54:26 user2843099

密碼學在這裏浮現在腦海。取一個數據集A，使用密鑰K對它進行加密，結果爲B.給用戶A和B，要求他恢復K.當然，你必須選擇密鑰大小和算法，這樣才能使這個任務變得切實可行。
或者採取一個簡短的隨機字符串，如10或20個字符。計算SHA1哈希。給用戶散列，並要求他恢復原始字符串。
或分解。給用戶兩個大素數的產品，並要求他恢復這些因素。

來源

2014-01-10 15:35:22 pentadecagon

算法及時計算，但快速驗證計算結果

回答

相關問題