big integer speed (VPI and symbolic)

I am doing integer exponentiation modulo a prime, with large integers. This just out of curiosity (crypto), I am a real novice in all this. What I am doing, is the following: take a big integer 'g', and subsequently multiply it by itself to create the exponentiation (g^1, g^2, g^3 ...). All of this modulo a big prime 'p'. When I run the following code in Matlab, it takes 1.4 seconds for a table of 1000 exponentiations. This is on a core i5, Matlab 2013b. Inspection with the profiler showed that the biggest chunk of time is due to the mod() line.

====================================

p = sym('13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171')

g = sym('11717829880366207009516117596335367088558084999998952205599979459063929499736583746670572176471460312928594829675428279466566527115212748467589894601965568')

nr = 1000  
gv = cell(nr,1);  
gv{1} = g;  
gt = 1;  
for ii = 2:nr  
    gt = mod(gt*g,p);  
    gv{ii} = gt;  
end
t = toc

====================================

I want to create a table of around 1000000 entries, so 1000 times as big as this one. Because this would take a lot of time, I also tried something in iPython (I'm also a novice in iPython):

====================================

t0 = time.time()

p = mpz('13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171')

g = mpz('11717829880366207009516117596335367088558084999998952205599979459063929499736583746670572176471460312928594829675428279466566527115212748467589894601965568')

nr = 1000000  
table = {}  
gv = 1  
for ii in range (0,nr):  
    gv = gmpy2.f_mod(gv*g,p)  
    table[ii] = gv  
print(time.time()-t0)

====================================

This only took 1.5 seconds for all 1000000 entries. I can not explain this huge difference in speed. I also tried the VPI tool: VPI But that is even slower than the symbolic toolbox.

Can anyone give some insight on this? Am I doing something wrong here or is Python just faster in this case?

Kind regards, Bart

Answer 1

[John D'Errico]

There are several issues here.

First of all, I do have a replacement for VPI in the works that tends to be an order of magnitude faster (VPIJ). I can send it out to those who might desire it. I think the only thing remaining to do was to clean up a couple of functions, and to rewrite the factor tool to use a better algorithm.

The fact is though, VPI is written in MATLAB itself. It is not as fast as I want it to be, but then nothing is as fast as we would want. The multiplies are done in VPI using calls to CONV, so they are not as fast as I'd like either. In VPI, mods are done as a divide with remainder. Again, all of this is much better in VPIJ, but you will still not find it as fast as a GMP based tool, something to which I lack access.

So if you really need blazing speed, then in this respect, it looks like Python, with what appears to be a wrapper around GMP calls, will be fastest.

[Bart]

Thanks for the answer, nice to know that you are working on VPIJ!

Like I said, I'm a noob in this regard, so I had never heard of GMP. A quick search gives this: Matlab gmp toolox

Could be useful, but I haven't tried it.

[Yair Altman]

@John - VPIJ would be most appreciated. Note that the built-in conv function could be replaced with a much faster invocation of the convolution theorem:

% Prepare the input vectors (1M elements each)
x = rand(1e6,1);
y = rand(1e6,1);

% Compute the comnvolution using the builtin conv()
z1 = conv(x,y);
=>  Elapsed time is 360.521187 seconds.

% Now compute the convolution using fft/ifft: 780x faster!
n = length(x) + length(y) - 1;  % we need to zero-pad
z2 = ifft(fft(x,n).*fft(y,n));
=>  Elapsed time is 0.463169 seconds.

% Compare the relative accuracy
>> max(abs(z1-z2)./abs(z1))
ans =
      2.75200348450538e-10

Bruno Luong's implementation of efficient convolution uses this idea and was made even more efficient by using MEX for in-place data manipulation.

[John D'Errico]

Yair - I know about the use of fft to replace conv, but did not look deeply at it because I need to know if it will yield exact integer results, when applied to big vectors of integers. I assume it is possible, as I believe some tools (specifically GMP) do use fft for multiplication as you suggest.

[Mohsin Shah]

Hello John D'Errico I need the faster version of VPI (VPIJ). Please share it with me.

Answer 2

[Yair Altman]

@Bart - you might also try the following alternatives:

• Advanpix Multi-Precision Computing Toolbox (MCT). Commercial. Reportedly 40-200x faster than Symbolic Toolbox's vpa. It uses GMP and MPFR, among others.
• Ben Barrowes' Multiple Precision Toolbox (MPT). FEX open-source. This toolbox also relies on GMP and MPFR, however it appears not to have updated since 2006 whereas MCT is fully up-to-date.

Answer 3

[Akram Choukri]

how to convert str to vpi ??