在 Lua 5.3 中,我是否正确实现了这个算法?

-- (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( '无效的解:%u ~= %u', y, y2 ) );
printf( 'x = %u', x );

Lua 解释器的输出结果:

input:33: 无效的解:3996422455 ~= 2979830783

上述算法是基于我在数学 StackExchange 这里 收到的答案。在授予回答悬赏之前,我想确保他描述的算法确实有效。然而,似乎我的断言总是失败。是他的算法有误还是我的代码有误呢?

点赞
用户4096902
用户4096902

我刚刚意识到我犯了一个愚蠢的错误。

这个算法:

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 );

但是显然这不是他想要的。

应该将上述循环代码段替换为以下代码:

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

现在代码通过了断言。

2016-08-11 05:01:41