Mustafa's profile - activity

Thank you very much - I did lots of mistakes (Im beginner in Sage/Python and not much experience in programming in general, so that comment helps!). I experiment with my implementations of modern integer-factoring algorithm, so the integers have usually >>20 digits - so theres no straight-forward way to speed up with Cython I guess?

I have made two files, first named "speedtest.sage", second "speedtest_compiled.spyx"

speedtest.sage:

def speedtest(n):
 f = 1
 for i in range(0,n):
    f=17*f^2 % 1234565432134567898765456787654323456787654345678765456787654321

speedtest.spyx:

def speedtest_compiled(n):
 f = 1
 for i in range(0,n):
    f=17*f^2 % 1234565432134567898765456787654323456787654345678765456787654321

They are equal (modulo names of the speedtest-function). I have this output on my notebook:

sage: load speedtest.sage
sage: load speedtest.spyx
Compiling speedtest.spyx...

sage: time speedtest(10^4)
CPU times: user 0.02 s, sys: 0.00 s, total: 0.02 s
Wall time: 0.02 s

sage: time speedtest(10^5)
CPU times: user 0.14 s, sys: 0.02 s, total: 0.16 s
Wall time: 0.16 s

sage: time speedtest(10^6)
CPU times: user 1.39 s, sys: 0.10 s, total: 1.49 s
Wall time: 1.50 s

sage: time speedtest_compiled(10^4)
CPU times: user 0.08 s, sys: 0.00 s, total: 0.08 s
Wall time: 0.08 s

sage: time speedtest_compiled(10^5)
CPU times: user 7.87 s, sys: 0.00 s, total: 7.87 s
Wall time: 7.87 s

The interpretated Python-Code of speedtest() behaves absolutely normal, as you can see - BUT the compiled Cython-Code behaves strange, not only that it is so extremely slow, its consumed time is not even close to linear in n (notice that I could not evaluate speedtest_compiled(10^6), it took too long. What is the explanation for this - and how to compile correctly to gain the 10-1000x speedup I've read about?

Ok, thank you, perhaps it will be implemented in coming versions.

First didn't change the speed, probably it uses the same algorithm with sparse=True?! Did not find one of the algorithm, Im a bit surprised about that, they should be of general interest, but Im new to sage, maybe I just didnt see it. Yes, implementation is always possible, but I hoped for done work :)

To compute the kernel of a sparse GF(2) matrix A I simply do

A.kernel()

But for (highly) sparse GF(2) matrices there are (many) much faster algorithm to compute the kernel, surely some of them are implemented in sage, but by which command I apply them? (Tutorial and online help could'nt answer that)

That is it! Thank you.

(Showing my work).

The first thing I tried was the obvious:

sage: vectors = [[1,0,1],[1,0,1],[1,1,0]]
sage: A = matrix(GF(2),vectors)
sage: B = A.kernel()
sage: matrix(B)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
[...]
ValueError: Invalid matrix constructor.  Type matrix? for help

which didn't work. So looked at B:

sage: B
Vector space of degree 3 and dimension 1 over Finite Field of size 2
Basis matrix:
[1 1 0]

and saw that it clearly knows about the matrix I think you're looking for. In Sage, functionality often lives inside objects, so if you type help(B) or or type "B." and then tab, you can see the list of internal functions, and I found both .matrix and .basis_matrix. I think either should work here, so:

sage: M = B.basis_matrix()
sage: M
[1 1 0]
sage: type(M)
<type 'sage.matrix.matrix_mod2_dense.Matrix_mod2_dense'>
sage: M.nrows()
1

Is that what you were after?

I construct a matrix A and compute its kernel by

A = matrix(GF(2),vectors)
B = A.kernel()

Now I want to convert B to a matrix, such that I can use .nrows() and other matrix-methods, how to do that?

Yes, sorry, thank you Mike and DSM - it seems as if I intended to annoy people here with this. I did correct that in my posting, but didn't realize that this could be the mistake ... To be sure: On my machine theres absolutely no speed-up of the compiled version (its even a bit slower), whys that?

This is an implementation of the pollard-rho factorization-algorithm in sage (filename: exp.sage)

def pollard_rho(n):
    x = 2
    y = x
    t = 1

    while t == 1:
        x = mod(x,n)^2+1
        y = mod(mod(y,n)^2+1,n)^2+1
        t = gcd(x-y,n)

    if t<n:
       return(t)
    else:
       return 0

I load it with "load exp.sage" and it works.

But trying to compile

import sage.all

def pollard_rho(n):
    x = 2
    y = x
    t = 1

    while t == 1:
        x = sage.all.mod(x,n)**2+1
        y = sage.all.mod(sage.all.mod(y,n)**2+1,n)**2+1
        t = sage.all.gcd(x-y,n)

    if t<n:
       return(t)
    else:
       return 0

named as "exp.spyx" brings several errors, one of them (f.e.):

 13     while t == 1:
 14       x = sage.all.mod(x,n)**2+1
 ---> 15       y = sage.all.mod(sage.mod(y,n)**2+1,n)**2+1
 16       t = sage.all.gcd(x-y,n)
 17     

 AttributeError: 'module' object has no attribute 'mod'

What is wrong here? Probably many things - im totally new to Sage, coming from Pari-gp and work in console-mode - no experiences with C or Python. Thank you.