arrays - Julia 矢量 : Excessive Memory Usage

Question

我想使用中间相遇攻击来暴力破解 64 位 RSA 加密文本(这适用于大学，没有恶意)。

为此，我基本上创建了一个具有 2^34 个 BigInt 值的 Julia 向量，并在其上广播了 powermod() 方法以用结果替换这些值。

v = powermod.(collect(1:2^34), e, n)

n 在这种情况下是 1024 位长，理论上应产生 2^34 * 1024 位大小加上开销的向量。但是，如果我尝试创建一个更小的向量(例如 2^20)，它已经分配了 4GB 的内存。

const e = 65537
const n = 146524179203462820907751077702895222709717245613911342138636679265720963659264803540209990978140003809112749926543448691815554807130673470903067642157383639213843567573216381956709789503739105865173848988830139432801516289108538638198344024523424071181688467967187076534718264943427915623567859427045475866239

@time begin
    v = (powermod.(collect(1:2^24), e, n))
end

@time 的输出:

125.598926 seconds (117.44 M allocations: 4.000 GiB, 5.35% gc time)

不确定我是否做错了什么。任何帮助将不胜感激..

Answer 1

我不认为你做错了什么，当你使用 BigInt 时，你使用的是 powermod 的不同方法，这不是分配免费:

julia> @btime powermod(1000, e, 100);
  370.048 ns (0 allocations: 0 bytes)

julia> @btime powermod(1000, e, n);
  6.320 μs (9 allocations: 280 bytes)

julia> @which powermod(1000, e, 100)
powermod(x::Integer, p::Integer, m::T) where T<:Integer in Base at intfuncs.jl:358

julia> @which powermod(1000, e, n)
powermod(x::Integer, p::Integer, m::BigInt) in Base.GMP at gmp.jl:615

因此您不仅在分配结果向量，还在中间计算期间分配。在 Julia Discourse 上有很多关于 BigInt 的性能限制的讨论，但我从来没有真正使用过它们，所以不幸的是没有关于如何在这里加快速度的任何建议!