Excessive memory consumption when using powermod() with BigInt

General Usage
1

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.((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.((1:2^24), e, n)
end

Output of @time:

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

Apparently, the powermod() function requires quite a bit of memory when used with BigInt as modulo. Why is this memory not freed up after the value has been returned? Or am I doing something wrong?

2

@time shows cumulative memory allocation during the execution of your code, so even if all memory is freed, it will show in the allocations count.

1 Like
3

Now I understand… Thanks again!