-- (1451AFBx - 1A7D575) ^ (-1C6B438x + i)
-- y = ( Ax + B )^( Cx + D )
-- x0 = B0 ^ D0 ^ y0
math.randomseed( os.time( ) );
local UINT32_MAX = 2^32 - 1;
local A = 0x1451AFB
local B = -0x1A7D575;
local C = -0x1C6B438;
local D = math.random( 0, UINT32_MAX );
local x = math.random( 0, UINT32_MAX );
local y = bit32.bxor( A * x + B, C * x + D );
x = { };
local function printf( msg, ... )
print( string.format( msg, ... ) );
end
local function getBit( n, i )
return ( ( n & ( 1 << ( i - 1 ) ) ) > 0 ) and 1 or 0;
end
for i = 1, 32 do
table.insert( x, 1, math.floor( bit32.bxor( getBit( B, i ), getBit( D, i ), getBit( y, i ) ) ) );
end
x = tonumber( table.concat( x ), 2 );
local y2 = bit32.bxor( A * x + B, C * x + D );
assert( y == y2, string.format( 'Invalid solution: %u ~= %u', y, y2 ) );
printf( 'x = %u', x );
来自this的输出Lua解释器:
input:33: Invalid solution: 3996422455 ~= 2979830783
上述算法是基于我收到的答案here在数学 StackExchange 上。在我向答案授予赏金之前,我想确保他描述的算法确实有效。然而,我的主张似乎总是失败。是他的算法错误还是我的代码错误?
最佳答案
我刚刚意识到犯了一个愚蠢的错误。
该算法:
for i = 1, 32 do
table.insert( x, 1, math.floor( bit32.bxor( getBit( B, i ), getBit( D, i ), getBit( y, i ) ) ) );
end
本质上是混淆了:
x = bit32.xor( B, D, y );
但这显然不是他的本意。
上述 for 循环片段的实际代码如下:
local b = B;
local d = D;
for i = 1, 32 do
table.insert( x, 1, math.floor( bit32.bxor( getBit( b, 1 ), getBit( d, 1 ), getBit( y, i ) ) ) );
b = ( A * x[1] + b ) // 2;
d = ( C * x[1] + d ) // 2;
end
代码现在通过了断言。
关于algorithm - 我在 Lua 5.3 中正确实现了这个算法吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38885548/