Julia Vector: Excessive Memory Usage

Question

I want to brute force an 64-bit RSA encrypted text using a meet-in-the-middle attack (This is for university, nothing malicious).

To do this, I essentially created a Julia vector with 2^34 BigInt values and broadcasted the powermod() method on it to replace the values with the results.

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

n in this case is 1024-bits long which should theoretically result in a vector of 2^34 * 1024 bits size plus overhead. However, if I try to create a smaller vector (E.g., 2^20) it will already allocate 4GB of memory.

const e = 65537
const n = 146524179203462820907751077702895222709717245613911342138636679265720963659264803540209990978140003809112749926543448691815554807130673470903067642157383639213843567573216381956709789503739105865173848988830139432801516289108538638198344024523424071181688467967187076534718264943427915623567859427045475866239

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

Output of @time:

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

Not sure what and if I am doing something wrong here. Any help would be appreciated..

Answer 1

I don't think you're doing anything wrong, when you're using a BigInt you're using a different method of powermod which isn't allocation free:

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

so you're not just allocating the result vector, but also during intermediate calculations. There's quite a few discussions on the Julia Discourse around the performance limitations of BigInts, but I've never really worked with them so unfortunately don't have any advice on how to speed things up here!